# Fastest algorithm for counting perfect matchings in a general graph

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.

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.
• Thank you very much - that's exactly what I was searching for. I'm a bit surprised that it is independent of $|E|$. Apr 20, 2017 at 7:13