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


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

| cite | improve this answer | |
  • $\begingroup$ do you know which page they talk about this construction in Dagum and Luby and also how many vertices are used in $G'$? $\endgroup$ – T.... Jul 24 '17 at 5:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Jul 24 '17 at 6:13

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.