<p><a href="http://www.sciencedirect.com/science/article/pii/0304397592902347" rel="nofollow noreferrer">Dagum and Luby</a> show (using a construction credited to <a href="http://www.sciencedirect.com/science/article/pii/0022000092900054" rel="nofollow noreferrer">Dahlhaus and Karpinski</a>) how to construct, given a bipartite graph $G$, a bipartite graph $G'$ of maximum degree $3$ such that $G'$ has exactly as many perfect matchings as $G$ (see Theorem 6.2.). Then from $G'$ you can construct a graph $G''$ with average degree arbitrarily close to $2$ and twice as many perfect matchings as $G'$, as I explained <a href="https://cstheory.stackexchange.com/questions/38685/what-is-known-about-counting-bipartite-perfect-matching-with-average-degree-in">here</a>. Both constructions are in polynomial time. Therefore, the best polytime deterministic approximation to the number of perfect matchings of a graph of maximum degree 3, and average degree in $[2,3]$ is equal to the best polytime deterministic approximation to the permanent of a 0-1 matrix. As far as I know, this is the factor $2^n$ approximation achieved by <a href="https://arxiv.org/abs/1408.0976" rel="nofollow noreferrer">Gurvits and Samorodnitsky</a>. </p>

<p>(It may be helpful to note that a $\exp(n^\varepsilon)$ approximation for $\varepsilon &lt; 1$ would imply an FPTAS.)</p>

CC BY-SA 3.0
2017-07-24T05:53:57.940Z
do you know which page they talk about this construction in Dagum and Luby and also how many vertices are used in $G'$?
Turbo
CC BY-SA 3.0
2017-07-24T06:13:29.870Z
As I said in my answer, it's Theorem 6.2. The proof is on page 299. $G'$ has $2m - n/2$ vertices, where $m$ is the number of edges of $G$ and $n$ is the number of vertices of $G$.
Sasho Nikolov
CC BY-SA 3.0
2017-07-24T05:11:39.647Z
2017-07-24T05:11:39.647Z
Sasho Nikolov
<p>We do not have a deterministic constant factor approximation scheme for general $n\times n$ $0/1$ permanent.</p>

<p>What is the best factor in deterministic approximation schemes if we only care counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?</p>

CC BY-SA 3.0
2017-07-24T04:38:04.197Z
Possible duplicate of [What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?](https://cstheory.stackexchange.com/questions/38685/what-is-known-about-counting-bipartite-perfect-matching-with-average-degree-in)
Mikhail Rudoy
CC BY-SA 3.0
2017-07-24T05:38:35.537Z
@MikhailRudoy not a duplicate.
Turbo
<approximation-algorithms><permanent>
Approximating max degree $3$ perfect matching count?
Turbo
# Approximating max degree $3$ perfect matching count?

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

We do not have a deterministic constant factor approximation scheme for general $n\times n$ $0/1$ permanent.

What is the best factor in deterministic approximation schemes if we only care counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

**Tags:** approximation-algorithms, permanent
> **Comments:**
> **username_1**: Possible duplicate of [What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?](https://cstheory.stackexchange.com/questions/38685/what-is-known-about-counting-bipartite-perfect-matching-with-average-degree-in)  
> **username_0**: @MikhailRudoy not a duplicate.  

---

## 1 answers

### Answer by username_2 on 2017-07-24. Score: 2 | Accepted answer

[Dagum and Luby](http://www.sciencedirect.com/science/article/pii/0304397592902347) show (using a construction credited to [Dahlhaus and Karpinski](http://www.sciencedirect.com/science/article/pii/0022000092900054)) how to construct, given a bipartite graph $G$, a bipartite graph $G'$ of maximum degree $3$ such that $G'$ has exactly as many perfect matchings as $G$ (see Theorem 6.2.). Then from $G'$ you can construct a graph $G''$ with average degree arbitrarily close to $2$ and twice as many perfect matchings as $G'$, as I explained [here](https://cstheory.stackexchange.com/questions/38685/what-is-known-about-counting-bipartite-perfect-matching-with-average-degree-in). Both constructions are in polynomial time. Therefore, the best polytime deterministic approximation to the number of perfect matchings of a graph of maximum degree 3, and average degree in $[2,3]$ is equal to the best polytime deterministic approximation to the permanent of a 0-1 matrix. As far as I know, this is the factor $2^n$ approximation achieved by [Gurvits and Samorodnitsky](https://arxiv.org/abs/1408.0976).

(It may be helpful to note that a $\exp(n^\varepsilon)$ approximation for $\varepsilon < 1$ would imply an FPTAS.)

> **Comments:**
> **username_0**: do you know which page they talk about this construction in Dagum and Luby and also how many vertices are used in $G'$?  
> **username_2**: As I said in my answer, it's Theorem 6.2. The proof is on page 299. $G'$ has $2m - n/2$ vertices, where $m$ is the number of edges of $G$ and $n$ is the number of vertices of $G$.  

---

