Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Chen, Xi; Dyer, Martin; Goldberg, Leslie Ann; Jerrum, Mark; Lu, Pinyan; McQuillan, Colin; Richerby, David https://www.dagstuhl.de/lipics License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-39303
URL:

; ; ; ; ; ;

The complexity of approximating conservative counting CSPs

pdf-format:


Abstract

We study the complexity of approximation for a weighted counting constraint satisfaction problem #CSP(F). In the conservative case, where F contains all unary functions, a classification is known for the Boolean domain. We give a classification for problems with general finite domain. We define weak log-modularity and weak log-supermodularity, and show that #CSP(F) is in FP if F is weakly log-modular. Otherwise, it is at least as hard to approximate as #BIS, counting independent sets in bipartite graphs, which is believed to be intractable. We further sub-divide the #BIS-hard case. If F is weakly log-supermodular, we show that #CSP(F) is as easy as Boolean log-supermodular weighted #CSP. Otherwise, it is NP-hard to approximate. Finally, we give a trichotomy for the arity-2 case. Then, #CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT, the problem of approximately counting satisfying assignments of a CNF Boolean formula.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2013:3930,
  author =	{Xi Chen and Martin Dyer and Leslie Ann Goldberg and Mark Jerrum and Pinyan Lu and Colin McQuillan and David Richerby},
  title =	{{The complexity of approximating conservative counting CSPs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{148--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Natacha Portier and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3930},
  URN =		{urn:nbn:de:0030-drops-39303},
  doi =		{10.4230/LIPIcs.STACS.2013.148},
  annote =	{Keywords: counting constraint satisfaction problem, approximation, complexity}
}

Keywords: counting constraint satisfaction problem, approximation, complexity
Seminar: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Issue date: 2013
Date of publication: 26.02.2013


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