2026-07-22T12:14:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7409 2024-03-06T10:40:18Z ddc:004 open_access

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems Galanis, Andreas Goldberg, Leslie Ann Yang, Kuan Constraint Satisfaction Approximate Counting 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 approximation-preserving (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 NP-hard 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 so-called "conservative" case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Galanis and Leslie Ann Goldberg and Kuan Yang 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.27 urn:nbn:de:0030-drops-74099 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.27 eng https://creativecommons.org/licenses/by/3.0/legalcode