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$](https://en.wikipedia.org/wiki/Sharp-P)). In particular, what is the scaling depending on the number of vertices $|V|$ and edges $|E|$?


[Randomized solutions](https://mathoverflow.net/questions/224296/algorithm-to-count-the-number-of-perfect-matchings-in-non-planar-graph) can be found in polynomial time; for bipartite graphs it corresponds to calculation of the permanent (which can be solved by [Ryser's formula](https://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_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.



Fastest algorithm for counting perfect matchings in a general graph
Have a look at: [approximating Hafnians](https://pdfs.semanticscholar.org/b5e0/7f9f783b951ad1f40249240d63a9cffe5744.pdf). 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.


