24
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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?" $\endgroup$
    – Joshua Grochow
    Nov 23, 2010 at 3:05
  • $\begingroup$ Good idea. I didn't even think about that. Thanks. $\endgroup$
    – Derrick Stolee
    Nov 23, 2010 at 5:09
  • 1
    $\begingroup$ 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” $\endgroup$
    – Tsuyoshi Ito
    Nov 23, 2010 at 16:17
  • $\begingroup$ 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. $\endgroup$
    – Derrick Stolee
    Nov 23, 2010 at 17:00
  • 7
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Nov 23, 2010 at 17:30

2 Answers 2

Reset to default
20
+200
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Derrick Stolee
    Nov 29, 2010 at 18:05
  • $\begingroup$ Despite it not being the answer I wanted, I found this a very satisfying answer. $\endgroup$
    – Derrick Stolee
    Nov 29, 2010 at 18:06
  • $\begingroup$ @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'? $\endgroup$
    – Turbo
    Dec 23, 2017 at 11:10
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.