# Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists some reduction from non-bipartite graphs to the permanent, but it may involve a nasty polynomial blowup by using Cook's reduction to SAT and then Valiant's theorem to reduce to the permanent.

An efficient and natural reduction $f$ from a non-bipartite graph $G$ to a matrix $A = f(G)$ where $\operatorname{perm}(A) = \Phi(G)$ would be useful for an actual implementation to count perfect matchings by using existing, heavily-optimized libraries that compute the permanent.

Updated: I added a bounty for an answer including an efficiently-computable function to take an arbitrary graph $G$ to a bipartite graph $H$ with the same number of perfect matchings and no more than $O(n^2)$ vertices.

• The current title sounds like a homework question, but the actual question is much more interesting than that. I almost didn't even open the question b/c I thought it was homework and would soon be closed, until I saw it already had 9 upvotes and got curious... Maybe change the title to something more along the lines of: "Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?" – Joshua Grochow Nov 23 '10 at 3:05
• Good idea. I didn't even think about that. Thanks. – Derrick Stolee Nov 23 '10 at 5:09
• Nitpicking: “Since finding a perfect matching in a non-bipartite graph is in NP” → “Since counting perfect matchings in a non-bipartite graph is in #P” – Tsuyoshi Ito Nov 23 '10 at 16:17
• Your nitpicking is correct, and I considered writing that, but the way I wrote it hints that the reduction applies Cook's THEN Valiant's reductions. I'm looking for a direct, efficient reduction. – Derrick Stolee Nov 23 '10 at 17:00
• There's a reducion that avoids Cook: first write a VNP formula for perfect matchings (I can think of one that is very similar to that for the permanent and which has size $\leq 4n^4$). Then, by the universality of the permanent, this can be written as the permanent of a matrix of size $4n^4 +1$. This uses the fact that a formula of size $S$ can be written as the permanent of a matrix of size $S+1$. More direct than going through Cook, but still not as direct/natural as the way perm counts perfect matchings in a bipartite graph. – Joshua Grochow Nov 23 '10 at 17:30