2026-07-22T00:06:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11004 2024-03-06T10:47:02Z ddc:004 open_access

Approximate Counting CSP Seen from the Other Side Bulatov, Andrei A. Živný, Stanislav constraint satisfaction approximate counting homomorphisms In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(C,-), in which the goal is, given a relational structure A from a class C of structures and an arbitrary structure B, to find the number of homomorphisms from A to B. Flum and Grohe showed that #CSP(C,-) is solvable in polynomial time if C has bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on decision CSPs, Dalmau and Jonsson then showed that, if C is a recursively enumerable class of relational structures of bounded arity, then assuming FPT != #W[1], there are no other cases of #CSP(C,-) solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04]. We show that, assuming FPT != W[1] (under randomised parametrised reductions) and for C satisfying certain general conditions, #CSP(C,-) is not solvable even approximately for C of unbounded treewidth; that is, there is no fixed parameter tractable (and thus also not fully polynomial) randomised approximation scheme for #CSP(C,-). In particular, our condition generalises the case when C is closed under taking minors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei A. Bulatov and Stanislav Živný 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.60 urn:nbn:de:0030-drops-110041 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.60 eng https://creativecommons.org/licenses/by/3.0/legalcode