8
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much - that's exactly what I was searching for. I'm a bit surprised that it is independent of $|E|$. $\endgroup$
    – Mario Krenn
    Apr 20, 2017 at 7:13

Your Answer

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

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