Treffer: The Complexity of Approximating Bounded-Degree Boolean #CSP

Title:
The Complexity of Approximating Bounded-Degree Boolean #CSP
Authors:
Dyer, Martin, Ann Goldberg, Leslie, Jalsenius, Markus, Richerby, David
Contributors:
School of Computing [Leeds], University of Leeds, Department of Computer Science [Liverpool], University of Liverpool, Department of Computer Science, University of Bristol [Bristol], Inria Nancy Grand Est & Loria, Jean-Yves Marion and Thomas Schwentick
Source:
27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010. :323-334
Publisher Information:
HAL CCSD, 2010.
Publication Year:
2010
Collection:
collection:STACS2010
Subject Terms:
Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.1: Combinatorics, [INFO.INFO-CC]Computer Science [cs], Computational Complexity [cs.CC]
Subject Geographic:
Nancy, France
Original Identifier:
HAL:
Document Type:
Konferenz conferenceObject<br />Conference papers
Language:
English
Access URL:
https://inria.hal.science/inria-00455310
https://inria.hal.science/inria-00455310v1/document
https://inria.hal.science/inria-00455310v1/file/dyer.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00455310v1
Database:
HAL

Weitere Informationen

The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum degree is at least 25 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 in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.