9
$\begingroup$

Recently i've been dealing with a problem that led me to the following questions:

  • Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph?
  • Is there a good algorithm for finding all maximum/perfect matchings in a general graph?
  • Are these two problems equivalent in their complexity?

I've stumbled upon the following references:

Both algorithms' complexity depend on the number of perfect matchings in the graph (meaning exponential running time in the worst case).

Moreover, both articles deal with bipartite graphs, I couldn't find similar articles dealing with the same problem in general graphs.

I'd appreciate information and references about the above problems.

Improve this question
$\endgroup$
1
  • $\begingroup$ As your question is also about finding all perfect matchings in a general graph: Have you found additional references or implementations on this? $\endgroup$ – bonanza May 1 '15 at 11:59
7
$\begingroup$

Counting the number of perfect matchings in bipartite graphs amounts to computing the permanent of 0–1 matrices, which is $\# P$-complete. It follows that there is a reduction from all the other counting problems you mention (which are all in $\# P$) to this problem. You can compute the number of perfect matchings in planar bipartite graphs, and you can approximate the number of perfect matchings in general bipartite graphs. See for example this survey. Approximating the number of perfect matchings in general graphs is apparently more difficult, see for example this paper or that paper. Both papers mention that their algorithms seem to perform well on random graphs, but not necessarily that well in the worst case.

The problems of counting and of enumerating matchings in graphs are of different kinds, so it's hard to say whether they are "equivalent". Note, however, that if you could enumerate matchings then you could count them. This shows that, in some sense, enumerating is harder than counting. For the case of perfect matchings in bipartite graphs, there appears to be a difference, since you can approximate the number of perfect matchings, but computing them exactly is $\# P$-hard.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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