Galanis, Andreas ;
Goldberg, Leslie Ann ;
Yang, Kuan
Approximating Partition Functions of BoundedDegree Boolean Counting Constraint Satisfaction Problems
Abstract
We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language Gamma and a degree bound Delta, we study the complexity of #CSP_Delta(Gamma), which is the problem of counting satisfying assignments to CSP instances with constraints from Gamma and whose variables can appear at most Delta times. Our main result shows that: (i) if every function in Gamma is affine, then #CSP_Delta(Gamma) is in FP for all Delta, (ii) otherwise, if every function in Gamma is in a class called IM_2, then for all sufficiently large Delta, #CSP_Delta(Gamma) is equivalent under approximationpreserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large Delta, it is NPhard to approximate the number of satisfying assignments of an instance of #CSP_Delta(Gamma), even within an exponential factor. Our result extends previous results, which apply only in the socalled "conservative" case.
BibTeX  Entry
@InProceedings{galanis_et_al:LIPIcs:2017:7409,
author = {Andreas Galanis and Leslie Ann Goldberg and Kuan Yang},
title = {{Approximating Partition Functions of BoundedDegree Boolean Counting Constraint Satisfaction Problems}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {27:127:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7409},
URN = {urn:nbn:de:0030drops74099},
doi = {10.4230/LIPIcs.ICALP.2017.27},
annote = {Keywords: Constraint Satisfaction, Approximate Counting}
}
07.07.2017
Keywords: 

Constraint Satisfaction, Approximate Counting 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

07.07.2017 