The Complexity of Approximating Bounded-Degree Boolean #CSP

Abstract : 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.
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.323-334, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées


https://hal.inria.fr/inria-00455310
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:02:56 AM
Last modification on : Wednesday, February 10, 2010 - 10:12:43 AM
Document(s) archivé(s) le : Friday, June 18, 2010 - 7:50:34 PM

File

dyer.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455310, version 1

Collections

Citation

Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.323-334, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455310>

Share

Metrics

Record views

147

Document downloads

65