patternMinor
Counting and finding all perfect/maximum matchings in general graphs
Viewed 0 times
countingmaximumallperfectgraphsgeneralfindingandmatchings
Problem
Recently i've been dealing with a problem that led me to the following questions:
I've stumbled upon the following references:
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.
- 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.
Solution
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.
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.
Context
StackExchange Computer Science Q#19924, answer score: 8
Revisions (0)
No revisions yet.