Problem Detail: 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:
- Algorithms for Enumerating All Perfect Maximum and Maximal Matchings In Bipartite Graphs– Suggesting an algorithm for enumerating all maximum matchings in a bipartite graph.
- Finding All the Perfect Matchings in Bipartite Graphs– Suggesting an algorithm for finding all perfect matchings in bipartite graphs
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.
Asked By : Ron Teller
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19924
