FPTAS for #BIS with Degree Bounds on One Side

Abstract

Counting the number of independent sets for a bipartite graph (#BIS) plays a crucial role in the study of approximate counting. It has been conjectured that there is no fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for #BIS, and it was proved that the problem for instances with a maximum degree of $6$ is already as hard as the general problem. In this paper, we obtain a surprising tractability result for a family of #BIS instances. We design a very simple deterministic fully polynomial-time approximation scheme (FPTAS) for #BIS when the maximum degree for one side is no larger than $5$. There is no restriction for the degrees on the other side, which do not even have to be bounded by a constant. Previously, FPTAS was only known for instances with a maximum degree of $5$ for both sides.

15 pages, to appear in STOC 2015; Improved presentations from previous version;

References in corpus (10)

• Approximating the partition function of the ferromagnetic Potts model
• #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
• Spatial mixing and approximation algorithms for graphs with bounded connective constant
• The expressibility of functions on the Boolean domain, with applications to Counting CSPs
• FPTAS for Counting Monotone CNF
• A Simple FPTAS for Counting Edge Covers
• Approximate Counting via Correlation Decay in Spin Systems
• A Counterexample to rapid mixing of the Ge-Stefankovic Process
• The Complexity of Ferromagnetic Two-spin Systems with External Fields
• The Complexity of Approximately Counting Stable Roommate Assignments

Cited by in corpus (5)

• Algorithmic Pirogov-Sinai theory
• On a conjecture of Sokal concerning roots of the independence polynomial
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• Computing the Independence Polynomial: from the Tree Threshold down to the Roots
• Improved Strong Spatial Mixing for Colorings on Trees