7
$\begingroup$

I need to count the number of perfect matchings of a certain family of graphs. This family of graph is non planar and a type of snark. For the initial cases, it seems that this number is growing exponentially. My request is different from the one here because right now, I have no interest in knowing what these perfect matchings are.

The FKT algorithm gives a polynomial time algorithm for a planar graph and I am wondering if there is anything similar for non planar graphs. Does anyone have any ideas?

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm not aware of anything faster than counting for graphs like yours (I'm assuming that snark $\implies$ cubic and not bipartite). It might be possible to exploit symmetries if there are any. $\endgroup$
    – Brendan McKay
    Commented Nov 23, 2015 at 1:33
  • $\begingroup$ @BrendanMcKay: There are considerable symmetries. What can we say if there are a lot of symmetries? Is it worth posting a new topic about? $\endgroup$
    – Sandeep Silwal
    Commented Nov 23, 2015 at 1:51
  • $\begingroup$ The automorphism group acts as a permutation group on the set of perfect matchings, so instead of counting individual matchings you can find the orbits of the action. However this can be hard to do in practice. If you post it as a question you should define your graphs and say what their symmetries are. $\endgroup$
    – Brendan McKay
    Commented Nov 23, 2015 at 6:47

1 Answer 1

Reset to default
8
$\begingroup$

Counting the number of perfect matchings in arbitrary graphs (i.e. non planar, non bipartite...) seems to be quite more difficult than the restricted cases that FKT-type algorithms can handle.

In particular, Valiant proved that the problem is in $\mathrm{\text{#}P}$.

With that in mind, you can find information on approximation algorithms, see for example:

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! Quick question, what does the notation $\mathrm{\text{#}P}$ mean? $\endgroup$
    – Sandeep Silwal
    Commented Nov 23, 2015 at 3:05
  • $\begingroup$ @SandeepSilwal Happy to help. It is a complexity class, esentially "the counting version of NP". See here for example $\endgroup$
    – Myshkin
    Commented Nov 23, 2015 at 3:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .