<p>This is obviously a comment and not an answer, but I don't have any reputation points here yet, so sorry about that.</p>

<p>For non-bipartite cubic bridgeless graphs, there are exponentially many perfect matchings, as Lovàsz and Plummer conjectured in the 70s.  The paper is in preparation.  This may be very relevant to your question, or maybe not at all.</p>

CC BY-SA 2.5
2010-11-23T20:29:14.937Z
2010-11-23T20:29:14.937Z
Andrew D. King
<p>I would say that a "simple" reduction to bipartite matching is highly unlikely. Firstly, it would give an algorithm for finding a perfect matching in a general graph using the Hungarian method. Hence, the reduction should contain all the complexity of the Edmond's blossom algorithm. 
Secondly, it will give a compact LP for perfect matching polytope and hence the reduction should not be symmetric (which are ruled out by a result of Yannakakis) and inherently very complicated. </p>

CC BY-SA 3.0
2017-12-23T11:10:41.633Z
@MohitSingh Could you please elaborate 'non-existence of hungarian method for non-bipartite graphs', 'what does containing all the complexity of blossom algorithm' and why would this give 'compact LP for perfect matching and so should be not-symmetric'?
Turbo
CC BY-SA 2.5
2010-11-29T18:05:40.480Z
These are all good reasons why this is unlikely to exist.  I should have asked for refutations in the question.  I'll probably give some bounty to this answer, unless someone proves you wrong.
Derrick Stolee
CC BY-SA 2.5
2010-11-29T18:06:07.123Z
Despite it not being the answer I wanted, I found this a very satisfying answer.
Derrick Stolee
CC BY-SA 2.5
2010-11-29T16:34:08.093Z
2010-11-29T16:34:08.093Z
Mohit Singh
<p>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 <em>some</em> 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.</p>

<p>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. </p>

<p><strong>Updated:</strong> 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.</p>

CC BY-SA 3.0
2017-08-05T00:21:59.403Z
@JoshuaGrochow what is the VNP formula for perfect matchings?
Turbo
CC BY-SA 2.5
2010-11-23T03:05:22.353Z
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
CC BY-SA 2.5
2010-11-23T05:09:30.767Z
Good idea.  I didn't even think about that. Thanks.
Derrick Stolee
CC BY-SA 2.5
2010-11-23T16:17:36.003Z
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
CC BY-SA 2.5
2010-11-23T17:00:56.607Z
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
CC BY-SA 2.5
2010-11-23T17:30:10.650Z
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
CC BY-SA 2.5
2010-11-23T20:46:20.273Z
@Derrick: I do not get it.  I know that you are looking for a direct/natural reduction as opposed to the composition of Cook’s reduction and Valiant’s reduction, but what does it have to do with my previous comment?
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-23T21:39:36.693Z
Just nitpicking your nitpicking.  Feel free to ignore.
Derrick Stolee
<graph-theory><counting-complexity><reductions><permanent>
Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
Derrick Stolee
# Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?

(Asked by: username_0 on 2010-11-21)

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.

**Tags:** graph-theory, counting-complexity, reductions, permanent

> **Comments:**
> **username_2**: 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?"  
> **username_0**: Good idea.  I didn't even think about that. Thanks.  
> **username_3**: 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”  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_3**: @Derrick: I do not get it.  I know that you are looking for a direct/natural reduction as opposed to the composition of Cook’s reduction and Valiant’s reduction, but what does it have to do with my previous comment?  
> **username_0**: Just nitpicking your nitpicking.  Feel free to ignore.  
> **username_1**: @JoshuaGrochow what is the VNP formula for perfect matchings?  

---

## 2 answers

### Answer by username_5 on 2010-11-29. Score: 20 | Accepted answer

I would say that a "simple" reduction to bipartite matching is highly unlikely. Firstly, it would give an algorithm for finding a perfect matching in a general graph using the Hungarian method. Hence, the reduction should contain all the complexity of the Edmond's blossom algorithm.
Secondly, it will give a compact LP for perfect matching polytope and hence the reduction should not be symmetric (which are ruled out by a result of Yannakakis) and inherently very complicated.

> **Comments:**
> **username_0**: These are all good reasons why this is unlikely to exist.  I should have asked for refutations in the question.  I'll probably give some bounty to this answer, unless someone proves you wrong.  
> **username_0**: Despite it not being the answer I wanted, I found this a very satisfying answer.  
> **username_1**: @MohitSingh Could you please elaborate 'non-existence of hungarian method for non-bipartite graphs', 'what does containing all the complexity of blossom algorithm' and why would this give 'compact LP for perfect matching and so should be not-symmetric'?  

---

### Answer by username_4 on 2010-11-23. Score: 4

This is obviously a comment and not an answer, but I don't have any reputation points here yet, so sorry about that.

For non-bipartite cubic bridgeless graphs, there are exponentially many perfect matchings, as Lovàsz and Plummer conjectured in the 70s. The paper is in preparation. This may be very relevant to your question, or maybe not at all.


---

