Programming Research Group Research Report RR-04-04

Andrei Bulatov and Martin Grohe

July 2004, 45pp.

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.