2026-07-24T00:57:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3930 2024-03-06T10:34:39Z ddc:004 open_access

The complexity of approximating conservative counting CSPs Chen, Xi Dyer, Martin Goldberg, Leslie Ann Jerrum, Mark Lu, Pinyan McQuillan, Colin Richerby, David counting constraint satisfaction problem approximation complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Martin Dyer and Leslie Ann Goldberg and Mark Jerrum and Pinyan Lu and Colin McQuillan and David Richerby 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.148 urn:nbn:de:0030-drops-39303 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.148 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode