The complexity of approximating bounded-degree Boolean #CSP

The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the m...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2012-11, Vol.220-221, p.1-14
Main Authors: Dyer, Martin, Goldberg, Leslie Ann, Jalsenius, Markus, Richerby, David
Format: Article
Language:English
Subjects:
Approximation algorithm
Complexity
Counting constraint satisfaction problem
CSP
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2011.12.007