The Complexity of Partition Functions
Andrei Bulatov and Martin Grohe
Abstract
We give a complexity theoretic classification of the counting versions of so-called H-colouring problems for graphs H that may have multiple edges between the same pair of vertices. More generally, we study the problem of computing a weighted sum of homomorphisms to a weighted graph H.
The problem has two interesting alternative formulations: First, it is equivalent to computing the partition function of a spin system as studied in statistical physics. And second, it is equivalent to counting the solutions to a constraint satisfaction problem whose constraint language consists of two equivalence relations.
In a nutshell, our result says that the problem is in polynomial time if the adjacency matrix of H has row rank 1, and #P-complete otherwise.
Details
| Institution |
Oxford University Computing Laboratory |
| Month |
July |
| Number |
RR−04−04 |
| Year |
2004 |