The Complexity of Weighted Boolean #CSP
Authors:
- Martin DyerMDMartin Dyer
- Leslie Ann GoldbergLGLeslie Ann Goldberg
- Mark JerrumMJMark Jerrum
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (5) , 1970-1986
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 parameterized by a finite set $\mathcal{F}$ of nonnegative 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 computing the partition function, i.e., the sum of the weights of all configurations, is $\text{{\sf FP}}^{\text{{\sf#P}}}$-complete unless either (1) every function in $\mathcal{F}$ is of “product type,” or (2) every function in $\mathcal{F}$ is “pure affine.” In the remaining cases, computing the partition function is in P.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Inapproximability of the Tutte polynomialInformation and Computation, 2008
- The complexity of soft constraint satisfactionArtificial Intelligence, 2006
- The complexity of partition functionsTheoretical Computer Science, 2005
- The complexity of counting colourings and independent sets in sparse graphs and hypergraphscomputational complexity, 2000
- The complexity of counting graph homomorphismsRandom Structures & Algorithms, 2000
- 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
- Complexity of Generalized Satisfiability Counting ProblemsInformation and Computation, 1996
- An Introduction to the Ising ModelThe American Mathematical Monthly, 1987
- Operations with structuresActa Mathematica Hungarica, 1967