The Complexity of Weighted Boolean #CSP

Abstract

This paper gives a dichotomy theorem for the complexity of computing the partition function of an instance of a weighted Boolean constraint satisfaction problem. The problem is parameterised by a finite set F of non-negative functions that may be used to assign weights to the configurations (feasible solutions) of a problem instance. Classical constraint satisfaction problems correspond to the special case of 0,1-valued functions. We show that the partition function, i.e. the sum of the weights of all configurations, can be computed in polynomial time if either (1) every function in F is of ``product type'', or (2) every function in F is ``pure affine''. For every other fixed set F, computing the partition function is FP^{#P}-complete.

Minor revision

References in corpus (1)

• Inapproximability of the Tutte polynomial

Cited by in corpus (11)

• The complexity of weighted and unweighted #CSP
• The expressibility of functions on the Boolean domain, with applications to Counting CSPs
• Classical simulation of quantum circuits by half Gauss sums
• The Complexity of Counting Homomorphisms to Cactus Graphs Modulo 2
• The complexity of approximating conservative counting CSPs
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• A full dichotomy for Holant${}^c$, inspired by quantum computation
• Beyond #CSP: A Dichotomy for Counting Weighted Eulerian Orientations with ARS
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• A Dichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs
• Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems