0
$\begingroup$

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?

$\endgroup$
  • 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$ – Sasho Nikolov Jul 23 '17 at 13:19
  • $\begingroup$ @SashoNikolov thank you. I will leave post as it could benefit other users. $\endgroup$ – Brout Jul 23 '17 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$ – Sasho Nikolov Jul 23 '17 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$ – Brout Jul 23 '17 at 18:58
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ what is $n$ here? $\endgroup$ – Brout Jul 23 '17 at 19:08
  • 1
    $\begingroup$ The number of vertices of $G$ $\endgroup$ – Sasho Nikolov Jul 23 '17 at 19:30

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.