Approximate Counting CSP Seen from the Other Side
Andrei A. Bulatov, Stanislav Živný · ACM Transactions on Computation Theory · 2020
In this article, 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 undertaking minors.