The Complexity of Weighted Boolean #CSP
Authors:
Preprint
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Inapproximability of the Tutte polynomialInformation and Computation, 2008
- Complexity Classifications of Boolean Constraint Satisfaction Problems2001
- Graph Homomorphisms and Phase TransitionsJournal of Combinatorial Theory, Series B, 1999
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group TheorySIAM Journal on Computing, 1998
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975