Dyer, Martin ;
Goldberg, Leslie Ann ;
Jalsenius, Markus ;
Richerby, David
The Complexity of Approximating BoundedDegree 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 boundeddegree 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 polynomialtime 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 $\NPtime = \RPtime$. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
BibTeX  Entry
@InProceedings{dyer_et_al:LIPIcs:2010:2466,
author = {Martin Dyer and Leslie Ann Goldberg and Markus Jalsenius and David Richerby},
title = {{The Complexity of Approximating BoundedDegree Boolean #CSP}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {323334},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2466},
URN = {urn:nbn:de:0030drops24669},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2466},
annote = {Keywords: Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms}
}
2010
Keywords: 

Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Related Scholarly Article: 


Issue date: 

2010 
Date of publication: 

2010 