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

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

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

CC BY-SA 3.0
2013-04-28T14:13:57.030Z
The number of perfect matchings of a planar graph can be computed in polynomial time.
Yoshio Okamoto
CC BY-SA 3.0
2013-04-28T20:12:25.143Z
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.
chazisop
CC BY-SA 3.0
2013-04-27T09:17:50.217Z
2013-04-28T20:14:36.920Z
2013-04-28T20:14:36.920Z
chazisop
<p>The description from <a href="http://en.wikipedia.org/wiki/Hosoya_index" rel="nofollow">Wikipedia</a> mentions that it is #P-Complete to compute, but there are methods.  What is a layman's explanation to this?</p>

CC BY-SA 3.0
2013-04-27T07:30:47.777Z
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...
J.y B.y
CC BY-SA 3.0
2013-04-27T21:38:17.497Z
Tim, are you asking what it means for a problem to be #P-complete?
Tyson Williams
CC BY-SA 3.0
2013-04-28T20:18:05.633Z
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 [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-04-28T20:18:45.980Z
A problem being #P-completeness does not mean it is not computable.
Kaveh
<time-complexity><counting-complexity>
#P-Completeness of the Hosoya Index
Tim
# #P-Completeness of the Hosoya Index

(Asked by: username_0 on 2013-04-27)

The description from [Wikipedia](http://en.wikipedia.org/wiki/Hosoya_index) mentions that it is #P-Complete to compute, but there are methods. What is a layman's explanation to this?

**Tags:** time-complexity, counting-complexity
> **Comments:**
> **username_1**: 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...  
> **username_2**: Tim, are you asking what it means for a problem to be #P-complete?  
> **username_3**: 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 [cs.se] which has a broader scope.  
> **username_3**: A problem being #P-completeness does not mean it is not computable.  

---

## 1 answers

### Answer by username_4 on 2013-04-27. Score: 1

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).

> **Comments:**
> **username_5**: The number of perfect matchings of a planar graph can be computed in polynomial time.  
> **username_4**: 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.  

---

