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?

$\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$ 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$ 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$ Nov 23, 2015 at 6:47

1 Answer 1

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:

$\endgroup$
2
  • $\begingroup$ Thanks! Quick question, what does the notation $\mathrm{\text{#}P}$ mean? $\endgroup$ 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
    Nov 23, 2015 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.