ALCOMFT-TR-02-20

M. Dyer, L. A. Goldberg and M. Jerrum
Counting and sampling H-colourings
Warwick. Work package 4. May 2002.

Abstract: \def\numP\ensuremath\mathrm#P For counting problems in \numP which are ``essentially self-reducible'', it is known that sampling and approximate counting are equivalent. However, many problems of interest do not have such a structure and there is already some evidence that this equivalence does not hold for the whole of \numP. An intriguing example is the class of H-colouring problems, which have recently been the subject of much study, and their natural generalisation to vertex- and edge-weighted versions. Particular cases of the counting-to-sampling reduction have been observed, but it has been an open question as to how far these reductions might extend to any H and a general graph G. Here we give the first completely general counting-to-sampling reduction. For every fixed H, we show that the problem of approximately determining the partition function of weighted H-colourings can be reduced to the problem of sampling these colourings from an approximately correct distribution. In particular, any rapidly-mixing Markov chain for sampling H-colourings can be turned into an FPRAS for counting H-colourings.

Postscript file: ALCOMFT-TR-02-20.ps.gz (126 kb).