What I call a graph here allows parallel edges. Is the following problem #P-hard:

INPUT: a 3-regular bipartite graph $G$

OUTPUT: the number of matchings of $G$.

It is known that counting matchings on 2-3-regular (even planar) graphs is #P-hard: in this paper it corresponds to the problem denoted $\#[1,1,0]|[1,1,0,0]$, which is hard according to the table page 10, and in that one it corresponds to the problem $\#$2-3-RBP-$\lambda$-Matchings with $\lambda = 1$, and it is also shown to be #P-hard. In that last paper it is also shown that counting matchings on $3$-regular planar graphs is hard (see page 122, second paragraph). But what I need is 3-regular bipartite graphs.

  • 2
    $\begingroup$ I'm leaving this as a comment rather than an answer because it's a different problem, but the #P-completeness of counting perfect matchings in 3-regular bipartite graphs is proved in P. Dagum and M. Luby. Approximating the permanent of graphs with large factors. Theoretical Computer Science 102(2):283–305, 1992, doi:10.1016/0304-3975(92)90234-7. $\endgroup$ Jul 10 '19 at 9:33

Your Answer

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

Browse other questions tagged or ask your own question.