Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems

Abstract

We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language $\Gamma$ and a degree bound $\Delta$, we study the complexity of #CSP${}_{\Delta }(\Gamma )$, which is the problem of counting satisfying assignments to CSP instances with constraints from $\Gamma$ and whose variables can appear at most $\Delta$ times. Our main result shows that: (i) if every function in $\Gamma$ is affine, then #CSP${}_{\Delta }(\Gamma )$ is in FP for all $\Delta$, (ii) otherwise, if every function in $\Gamma$ is in a class called IM${}_2$, then for all sufficiently large $\Delta$, #CSP${}_{\Delta }(\Gamma )$ is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large $\Delta$, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP${}_{\Delta }(\Gamma )$, even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.

To appear in JCSS. This version: minor corrections to typos

References in corpus (2)

• #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
• FPTAS for Counting Monotone CNF