<p>One week in my complexity theory class in college, our sole homework problem was to prove that #2-SAT was #P-complete, by reducing from #BIPARTITE PERFECT MATCHING. No one could solve it, even when we eventually all banded together to work on it.</p>

<p>Next class, the professor was surprised at how difficult we had all found it and presented his proof. It was wrong. Luckily, one smart cookie was able to give the correct reduction, which was absolutely insane and disgustingly complicated. By the way, the professor has a Turing Award :)</p>

<p>Anyway, while I and my classmates couldn't solve that problem, we were able to solve the easier problem of reducing from #BIPARTITE MATCHING to #2-SAT, so here is the proof I came up with a few years back.</p>

<p><strong>Theorem.</strong> #BIPARTITE MATCHING $≤_p$ #2-SAT.</p>

<p><em>Proof</em>. Let $G = (V,E)$ be an instance of #BIPARTITE MATCHING. Let the partition sets be
$$A = \{a_i \mid i∈[n]\}, \quad B = \{b_i \mid i∈[m]\}$$
(so $|A|=n$ and $|B|=m$).</p>

<p>Now we reduce $G$ to a 2SAT formula $φ$, such that each satisfying assignment of $φ$ is a matching of $G$, and vice versa. To start, for each edge $a_ib_j ∈ E$ create a variable $x_{ij}$. The idea is that setting variable $x_{ij}$ to TRUE corresponds to edge $a_ib_j$ being in the matching. For each vertex $i$, create the 2SAT expressions
$$ A_i = \bigwedge_{j &lt; k} (¬x_{ij} ∨ ¬x_{ik}), \quad B_i := \bigwedge_{j&lt;k} (¬x_{ji} ∨ ¬x_{ki}) $$
For $A_i$ to be satisfied, all but at most one of $x_{ij}$ has to be false. To see this, assume both $x_{ij}$ and $x_{ik}$ are true. Then $(¬x_{ij} ∨ ¬x_{ik})$ is false, and so is $A_i$. The same holds for $B_i$. Letting
$$ C = \bigwedge_{i=1}^n A_i ∧ \bigwedge_{i=1}^m B_i $$
we have that $C$ is satisfied if and only if each vertex in $G$ is incident to at most one edge we
choose, and thus the edges form a matching.</p>

CC BY-SA 3.0
2016-02-10T02:10:35.060Z
I think I must be missing something here. This appears to show that an arbitrary instance of #BIPARTITE_MATCHING can be encoded as an instance of #2-SAT. But, I expected that you would be trying to show that an arbitrary instance of #2-SAT can be encoded as an instance of #BIPARTITE_MATCHING, no?
mhum
CC BY-SA 3.0
2016-02-10T02:52:29.840Z
Whoops, you're right. This was taken off an old homework problem and I didn't actually have the question written down, only my answer. The problem must have been to show that #2-SAT was #P-Complete, knowing that #BIPARTITE-PERFECT-MATCHING was #P-complete. I'll edit it.
gardenhead
CC BY-SA 3.0
2016-02-10T09:06:40.070Z
@gardenhead: Thanks for your answer! This is interesting but I don't think this is very related to my question, is it? This only shows that #BIPARTITE-MATCHING is in #P, which is not much of a surprise.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-05-01T10:53:14.363Z
The reduction in this answer seems to be correct, although it appears to be unrelated to the question.  However, I don't understand @a3nm's comment, nor do I follow the story in the preface of the answer (which rather muddles up three different reductions).
András Salamon
CC BY-SA 3.0
2016-02-09T23:49:23.613Z
2016-02-10T02:55:34.410Z
2016-02-10T02:55:34.410Z
gardenhead
<p>The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete.<br>
This has been proved by Les Valiant himself, on page 415 of the paper</p>

<blockquote>
  <p>Leslie G. Valiant<br>
  The Complexity of Enumeration and Reliability Problems<br>
  SIAM J. Comput., 8(3), 410–421</p>
</blockquote>

CC BY-SA 3.0
2016-02-09T16:56:43.780Z
Looks good, thanks! I don't know why this simple fact was not stated clearly on the Wikipedia page (or elsewhere on the Web apparenty). I improved Wikipedia accordingly: https://en.wikipedia.org/w/index.php?title=Matching_%28graph_theory%29&type=revision&diff=704113565&oldid=703048709 Thanks again!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2016-02-09T16:12:36.377Z
2016-02-09T16:12:36.377Z
Gamow
<p>I might be missing something obvious but I can't find references about the complexity of counting <em>matchings</em> (not perfect matchings) in bipartite graphs. Here is the formal problem:</p>

<ul>
<li>Input: a bipartite graph $G = (U, V, E)$ with $E \subseteq U \times V$</li>
<li>Output: the number of matchings of $G$, where a <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)">matchings</a> is a subset $F \subseteq E$ such that there is no $v \in U \sqcup V$ that occurs in two edges of $F$.</li>
</ul>

<p><strong>What is the complexity of this problem?</strong> Is it #P-hard?</p>

<p>It is well-known that counting <em>perfect</em> matchings on bipartite graphs is #P-hard, and it is known that counting matchings of <em>arbitrary</em> graphs (or even planar 3-regular graphs) is #P-hard by <a href="http://www.sciencedirect.com/science/article/pii/S0304397507004653">this paper</a>, but I didn't find anything about counting non-perfect matchings on bipartite graphs.</p>

CC BY-SA 4.0
2018-07-14T14:40:18.540Z
There seems to be a problem in this algorithm
there are cases in the result where not all nodes from the left or right side are included in the 2sat solution so therefore the exact counting algorithm doesn't work. Does anybody know an algorithm for single maximum bipartite matching solutions that was derived using a reduction to 2sat?
user3700810
<counting-complexity><matching><bipartite-graphs>
Complexity of counting matchings in a bipartite graph
Antoine Amarilli 'a3nm'
# Complexity of counting matchings in a bipartite graph

(Asked by: username_0 on 2016-02-09)

I might be missing something obvious but I can't find references about the complexity of counting *matchings* (not perfect matchings) in bipartite graphs. Here is the formal problem:

* Input: a bipartite graph $G = (U, V, E)$ with $E \subseteq U \times V$
* Output: the number of matchings of $G$, where a [matchings](https://en.wikipedia.org/wiki/Matching_(graph_theory)) is a subset $F \subseteq E$ such that there is no $v \in U \sqcup V$ that occurs in two edges of $F$.

**What is the complexity of this problem?** Is it #P-hard?

It is well-known that counting *perfect* matchings on bipartite graphs is #P-hard, and it is known that counting matchings of *arbitrary* graphs (or even planar 3-regular graphs) is #P-hard by [this paper](http://www.sciencedirect.com/science/article/pii/S0304397507004653), but I didn't find anything about counting non-perfect matchings on bipartite graphs.

**Tags:** counting-complexity, matching, bipartite-graphs
> **Comments:**
> **username_1**: There seems to be a problem in this algorithm there are cases in the result where not all nodes from the left or right side are included in the 2sat solution so therefore the exact counting algorithm doesn't work. Does anybody know an algorithm for single maximum bipartite matching solutions that was derived using a reduction to 2sat?  

---

## 2 answers

### Answer by username_5 on 2016-02-09. Score: 13 | Accepted answer

The problem of counting such "imperfect" matchings in bipartite graphs is #P-complete.  
This has been proved by Les Valiant himself, on page 415 of the paper

> Leslie G. Valiant  
> The Complexity of Enumeration and Reliability Problems  
> SIAM J. Comput., 8(3), 410–421

> **Comments:**
> **username_0**: Looks good, thanks! I don't know why this simple fact was not stated clearly on the Wikipedia page (or elsewhere on the Web apparenty). I improved Wikipedia accordingly: https://en.wikipedia.org/w/index.php?title=Matching_%28graph_theory%29&type=revision&diff=704113565&oldid=703048709 Thanks again!  

---

### Answer by username_2 on 2016-02-09. Score: 0

One week in my complexity theory class in college, our sole homework problem was to prove that #2-SAT was #P-complete, by reducing from #BIPARTITE PERFECT MATCHING. No one could solve it, even when we eventually all banded together to work on it.

Next class, the professor was surprised at how difficult we had all found it and presented his proof. It was wrong. Luckily, one smart cookie was able to give the correct reduction, which was absolutely insane and disgustingly complicated. By the way, the professor has a Turing Award :)

Anyway, while I and my classmates couldn't solve that problem, we were able to solve the easier problem of reducing from #BIPARTITE MATCHING to #2-SAT, so here is the proof I came up with a few years back.

**Theorem.** #BIPARTITE MATCHING $≤\_p$ #2-SAT.

*Proof*. Let $G = (V,E)$ be an instance of #BIPARTITE MATCHING. Let the partition sets be
$$A = \{a\_i \mid i∈[n]\}, \quad B = \{b\_i \mid i∈[m]\}$$
(so $|A|=n$ and $|B|=m$).

Now we reduce $G$ to a 2SAT formula $φ$, such that each satisfying assignment of $φ$ is a matching of $G$, and vice versa. To start, for each edge $a\_ib\_j ∈ E$ create a variable $x\_{ij}$. The idea is that setting variable $x\_{ij}$ to TRUE corresponds to edge $a\_ib\_j$ being in the matching. For each vertex $i$, create the 2SAT expressions
$$ A\_i = \bigwedge\_{j < k} (¬x\_{ij} ∨ ¬x\_{ik}), \quad B\_i := \bigwedge\_{j

> **Comments:**
> **username_3**: I think I must be missing something here. This appears to show that an arbitrary instance of #BIPARTITE_MATCHING can be encoded as an instance of #2-SAT. But, I expected that you would be trying to show that an arbitrary instance of #2-SAT can be encoded as an instance of #BIPARTITE_MATCHING, no?  
> **username_2**: Whoops, you're right. This was taken off an old homework problem and I didn't actually have the question written down, only my answer. The problem must have been to show that #2-SAT was #P-Complete, knowing that #BIPARTITE-PERFECT-MATCHING was #P-complete. I'll edit it.  
> **username_0**: @gardenhead: Thanks for your answer! This is interesting but I don't think this is very related to my question, is it? This only shows that #BIPARTITE-MATCHING is in #P, which is not much of a surprise.  
> **username_4**: The reduction in this answer seems to be correct, although it appears to be unrelated to the question.  However, I don't understand @a3nm's comment, nor do I follow the story in the preface of the answer (which rather muddles up three different reductions).  

---

