We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$.

We also know there are degree $3$ bipartite graphs that are planar whose perfect matching count is in $P$.

  1. What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

  2. Is there a cutoff degree $\alpha\in[2,3]$ such that if max degree $3$ holds then counting perfect matching count is in $P$?

  3. Is there any relevant literature?

  • 5
    $\begingroup$ Can't you just take any degree 3 instance and take its disjoint union with a large cycle to make the average degree as close to 2 as you want? If you can approximate the number of perfect matchings in the union, you can also do it in the original graph. $\endgroup$ Jul 23, 2017 at 13:19
  • $\begingroup$ @SashoNikolov thank you. I will leave post as it could benefit other users. $\endgroup$
    – Turbo
    Jul 23, 2017 at 18:40
  • $\begingroup$ If this answers your question I can post it as an answer. Unanswered questions keep being bumped up by the site. $\endgroup$ Jul 23, 2017 at 18:57
  • $\begingroup$ @SashoNikolov my only concern is 'how large should the cycle be?'. if it is exponential in size it defeats the purpose. On other hand there is a FPRAS for 0/1PERMANENT and may be if the cycle is not large as well we can get a good approximation. what is the trade off that we need to understand? $\endgroup$
    – Turbo
    Jul 23, 2017 at 18:58

1 Answer 1


You can take any degree 3 bipartite graph $G$ and take its disjoint union $G'$ with a cycle $C$ of length 2m. The new graph $G'$ is bipartite, and has average degree $\frac{3n + 2m}{m+n} = 2 + \frac{n}{n+m}$. Also, the number of perfect matchings in $G'$ is exactly twice the number of perfect matchings in $G$, because the perfect matchings of $G'$ are the disjoint unions of a perfect matching of $G$ and a perfect matching of $C$, of which there are two. So, there is a polytime parsimonious reduction from counting perfect matchings in 3-regular bipartite graphs to counting perfect matchings in graphs with maximum degree 3 and average degree $2 + \frac{1}{\mathrm{poly}(n)}$.

  • $\begingroup$ what is $n$ here? $\endgroup$
    – Turbo
    Jul 23, 2017 at 19:08
  • 1
    $\begingroup$ The number of vertices of $G$ $\endgroup$ Jul 23, 2017 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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