Approximate counting CSP seen from the other side

Journal article

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 parameterised 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.

Authors: Bulatov, A; Živný, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Computation Theory
• Volume: 12
• Issue: 2
• Article number: 11
• Publication date: 2020-05-19
• Acceptance date: 2020-01-11
• DOI: 10.1145/3389390
• EISSN: 1942-3462
• ISSN: 1942-3454
• Language: English
• Keywords: FFR