The complexity of approximating conservative counting CSPs

• We classify the complexity of approximating conservative weighted counting CSP.
• It is in FP, as hard as counting bipartite independent sets (#BIS) or as hard as #SAT.
• For functions of arity 2, the #BIS-hard case is equivalent to #BIS.
• For higher arity, the #BIS-hard case reduces to a Boolean weighted #CSP or is NP-hard.
• Given a weighted constraint language, the classification is decidable.

We study the complexity of the approximate weighted counting constraint satisfaction problem #CSP(F)#CSP(F). In the conservative case, where FF contains all unary functions, a classification is known over the Boolean domain; we extend this to arbitrary finite domains. We show that if FF is “weakly log-modular”, then #CSP(F)#CSP(F) is in FP. Otherwise, it is at least as difficult to approximate as #BIS (counting independent sets in bipartite graphs). #BIS is complete for the complexity class #RHΠ1#RHΠ1, and believed to be intractable. We further sub-divide the #BIS-hard case: if FF is “weakly log-supermodular”, #CSP(F)#CSP(F) is as easy as a Boolean log-supermodular weighted #CSP; otherwise, we show that it is NP-hard to approximate. Finally, we give a full trichotomy for the arity-2 case: #CSP(F)#CSP(F) is in FP, is #BIS-equivalent, or is equivalent to #SAT (approximately counting the satisfying assignments of Boolean CNF formulas). We also discuss algorithmic aspects of our classification.