# Approximating max degree $3$ perfect matching count?

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$?

• – Mikhail Rudoy Jul 24 '17 at 4:38
• @MikhailRudoy not a duplicate. – 1.. Jul 24 '17 at 5:38

Dagum and Luby show (using a construction credited to Dahlhaus and Karpinski) 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. 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.
(It may be helpful to note that a $\exp(n^\varepsilon)$ approximation for $\varepsilon < 1$ would imply an FPTAS.)
• do you know which page they talk about this construction in Dagum and Luby and also how many vertices are used in $G'$? – 1.. Jul 24 '17 at 5:53
• 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 Jul 24 '17 at 6:13