The description from Wikipedia mentions that it is #P-Complete to compute, but there are methods. What is a layman's explanation to this?

  • 2
    $\begingroup$ I added a link to the wikipedia article you are refering too in order to help people answering your question. You might as well summarize the "methods" you are refering to... $\endgroup$
    – Jeremy
    Apr 27 '13 at 7:30
  • 1
    $\begingroup$ Tim, are you asking what it means for a problem to be #P-complete? $\endgroup$ Apr 27 '13 at 21:38
  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope. $\endgroup$
    – Kaveh
    Apr 28 '13 at 20:18
  • $\begingroup$ A problem being #P-completeness does not mean it is not computable. $\endgroup$
    – Kaveh
    Apr 28 '13 at 20:18

A matching $M$ is called perfect for a graph $G$ when all vertices of a graph are matched in $M$.

Computing the number of perfect matchings is a well-known #P-complete problem and shown to be equivalent to computing the permanent of the biadjacency matrix of the graph. Now note that each perfect matching, by removing edges produces $2^{n}-1$ different matchings (consider each subset of edges, which is a smaller matching, we do not consider the empty set). Also, each perfect matching prohibits exactly $\binom{n}{k}$ matchings of size $k$ from being maximal but non-perfect, since they are subsets of this perfect matching. Given those kinds of restrictions, one can certainly upper bound the number of perfect matchings given the number of matchings and perhaps it is also to use additional information to do a precise calculation.

Perhaps you should take a look at the paper "Two-dimensional monomer-dimer systems are computationally intractable" (reference 5 in the wikipedia article). It seems to rely on the fact that counting matchings (all of them, see the comments) remains #P-complete for planar graphs. Interestingly enough, counting perfect matchings for planar graphs in in $P$, i.e. can be computed in polynomial time (in a deterministic way).

  • 3
    $\begingroup$ The number of perfect matchings of a planar graph can be computed in polynomial time. $\endgroup$ Apr 28 '13 at 14:13
  • $\begingroup$ You're right, I misread the statement in the reference. It actually refers to the number of all matchings, not just perfect ones. Making the necessary edits. $\endgroup$
    – chazisop
    Apr 28 '13 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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