Counting the number of perfect matchings in a bipartite graph is known to be difficult, actually #P complete (see a nice math.SE question+answer here).
I was wondering what is known for other graphs? For instance, it is known that for complete graphs, the number of perfect matchings goes double factorial.
- Are there graphs where counting all perfect matchings is simple aswell?
- Are there graphs where counting all perfect matchings is even more difficult than for bipartite graphs?
Thank you!
Counting perfect matchings in an arbitrary graph is definitely in #P: it corresponds to the "Does this graph have a perfect matching?" problem, which is in NP because we can efficiently check that a set of edges is a perfect matching. So the problem can't get any more difficult than #P-complete for any class of graphs.
I wouldn't say that counting perfect matchings in a complete graph really fits into this framework; it's not a very large class of graphs, is it? We can write down a formula for the number of perfect matchings in a complete graph. There's also a well-known formula for the number of domino tilings of an $m \times n$ chessboard: $$T(m,n) = \prod_{j=1}^m \prod_{k=1}^n \sqrt{4 \cos^2 \frac{j\pi}{m+1} + 4 \cos^2 \frac{k \pi}{n+1}}.$$ This, of course, is also the number of perfect matchings in an $m \times n$ grid graph.
We do have larger classes of graphs for which the problem is easy (polynomial-time algorithms exist).
(Okamoto, Uehara, Uno 2009) provide citations for the examples above, and find polynomial-time algorithms for several other classes of graphs.