License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2466
URN: urn:nbn:de:0030-drops-24669
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2466/
Go to the corresponding LIPIcs Volume Portal

Dyer, Martin ; Goldberg, Leslie Ann ; Jalsenius, Markus ; Richerby, David

The Complexity of Approximating Bounded-Degree Boolean #CSP

pdf-format:
1001.DyerMartin.2466.pdf (0.3 MB)

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 $\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 Bounded-Degree Boolean #CSP}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{323--334},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2466},
  URN =		{urn:nbn:de:0030-drops-24669},
  doi =		{10.4230/LIPIcs.STACS.2010.2466},
  annote =	{Keywords: Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms}
}

Keywords: Boolean constraint satisfaction problem, generalized satisfiability, counting, approximation algorithms
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI