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

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?

• 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. – Sasho Nikolov Jul 23 '17 at 13:19
• @SashoNikolov thank you. I will leave post as it could benefit other users. – 1.. Jul 23 '17 at 18:40
• If this answers your question I can post it as an answer. Unanswered questions keep being bumped up by the site. – Sasho Nikolov Jul 23 '17 at 18:57
• @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? – 1.. Jul 23 '17 at 18:58

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

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