Fastest algorithm for counting perfect matchings in a general graph

Question

Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$ ). In particular, what is the scaling depending on the number of vertices $|V|$ and edges $|E|$ ?

Randomized solutions can be found in polynomial time; for bipartite graphs it corresponds to calculation of the permanent (which can be solved by Ryser's formula in $O(2^n n^2)$ ).

But for general undirected graphs I was not able to find any algorithm or it's scalings. Thank you.

Suvrit · Accepted Answer · 2017-04-19T15:26:40.113

8

Have a look at: approximating Hafnians. In particular, there are a several works on computing Hafnians, I can add them also in case you are unable to find them starting from the cited reference -- which also includes a short but good discussion about the complexity of the problem; in polynomial space, a Ryser like algorithm seems to be known, and thus $O(n^22^n)$ ; for non-polynomial space, the linked paper provides a $\tilde{O}(2^{n/2})$ method.

edited Apr 19 '17 at 15:26

answered Apr 19 '17 at 14:47

Suvrit

28,363

Thank you very much - that's exactly what I was searching for. I'm a bit surprised that it is independent of $|E|$ . – Mario Krenn Apr 20 '17 at 07:13

Fastest algorithm for counting perfect matchings in a general graph

1 Answers1

Linked