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
    Commented Apr 20, 2017 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .