9
$\begingroup$

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 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, but I didn't find anything about counting non-perfect matchings on bipartite graphs.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user3700810 Jul 14 '18 at 14:40
14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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: en.wikipedia.org/w/… Thanks again! $\endgroup$ – a3nm Feb 9 '16 at 16:56
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – mhum Feb 10 '16 at 2:10
  • $\begingroup$ 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. $\endgroup$ – gardenhead Feb 10 '16 at 2:52
  • 1
    $\begingroup$ @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. $\endgroup$ – a3nm Feb 10 '16 at 9:06
  • $\begingroup$ 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). $\endgroup$ – András Salamon May 1 '16 at 10:53
  • $\begingroup$ I figured out how to reduce #MONO-2SAT to #BIPARTITE PERFECT MATCHING, but the proof is not that simple :P. $\endgroup$ – user39044 May 15 '16 at 23:43

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.