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

CC BY-SA 3.0
2017-07-23T19:08:13.107Z
what is $n$ here?
Turbo
CC BY-SA 3.0
2017-07-23T19:30:23.817Z
The number of vertices of $G$
Sasho Nikolov
CC BY-SA 3.0
2017-07-23T19:04:03.477Z
2017-07-23T19:04:03.477Z
Sasho Nikolov
<p>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$.</p>

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

<ol>
<li><p>What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?</p></li>
<li><p>Is there a cutoff degree $\alpha\in[2,3]$ such that if max degree $3$ holds then counting perfect matching count is in $P$?</p></li>
<li><p>Is there any relevant literature?</p></li>
</ol>

CC BY-SA 3.0
2017-07-23T13:19:45.473Z
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
CC BY-SA 3.0
2017-07-23T18:40:12.967Z
@SashoNikolov thank you. I will leave post as it could benefit other users.
Turbo
CC BY-SA 3.0
2017-07-23T18:57:25.087Z
If this answers your question I can post it as an answer. Unanswered questions keep being bumped up by the site.
Sasho Nikolov
CC BY-SA 3.0
2017-07-23T18:58:15.970Z
@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?
Turbo
<ds.algorithms><graph-theory><counting-complexity><permanent><bipartite-graphs>
What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
Turbo
# What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

(Asked by: username_0 on 2017-07-23)

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?

**Tags:** ds.algorithms, graph-theory, counting-complexity, permanent, bipartite-graphs

> **Comments:**
> **username_1**: 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.  
> **username_0**: @SashoNikolov thank you. I will leave post as it could benefit other users.  
> **username_1**: If this answers your question I can post it as an answer. Unanswered questions keep being bumped up by the site.  
> **username_0**: @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 answers

### Answer by username_1 on 2017-07-23. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: what is $n$ here?  
> **username_1**: The number of vertices of $G$  

---

