ALCOMFT-TR-02-18

Leslie Ann Goldberg, Steven Kelk and Mike Paterson
The complexity of choosing an H-colouring (nearly) uniformly at random
Warwick. Work package 4. May 2002.

Abstract: \def\CountBIS\textsc#BIS Cooper, Dyer and Frieze studied the problem of sampling H-colourings (nearly) uniformly at random. Special cases of this problem include sampling colourings and independent sets and sampling from statistical physics models such as the Widom-Rowlinson model, the Beach model, the Potts model and the hard-core lattice gas model. Cooper et al. considered the family of ``cautious'' ergodic Markov chains with uniform stationary distribution and showed that, for every fixed connected ``nontrivial'' graph H, every such chain mixes slowly. In this paper, we give a complexity result for the problem. Namely, we show that for any fixed graph H with no trivial components, there is unlikely to be any Polynomial Almost Uniform Sampler (PAUS) for H-colourings. We show that if there were a PAUS for the H-colouring problem, there would also be a PAUS for sampling independent sets in bipartite graphs and, by the self-reducibility of the latter problem, there would be a Fully-Polynomial Randomised Approximation Scheme (FPRAS) for \CountBIS - the problem of counting independent sets in bipartite graphs. Dyer, Goldberg, Greenhill and Jerrum have shown that \CountBIS is complete in a certain logically-defined complexity class. Thus, a PAUS for sampling H-colourings would give an FPRAS for the entire complexity class. In order to achieve our result we introduce the new notion of sampling-preserving reduction which seems to be more useful in certain settings than approximation-preserving reduction.

Postscript file: ALCOMFT-TR-02-18.ps.gz (151 kb).