The complexity of choosing an H-colouring (nearly) uniformly at random

ABSTRACT

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 BIS --- the problem of counting independent sets in bipartite graphs. Dyer, Goldberg, Greenhill and Jerrum have shown that BIS 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.

REFERENCES

• 1: C. Borgs, J.T. Chayes, M. Dyer and P. Tetali, On the sampling problem for H-colorings on the hypercubic lattice, pre-print (2000).
• 2: Graham R. Brightwell , Peter Winkler, Graph homomorphisms and phase transitions, Journal of Combinatorial Theory Series B, v.77 n.2, p.221-262, Nov. 1999 [doi>10.1006/jctb.1999.1899]
• 3: Colin Cooper , Martin Dyer , Alan Frieze, On Markov chains for randomly H-coloring a graph, Journal of Algorithms, v.39 n.1, p.117-134, April 2001 [doi>10.1006/jagm.2000.1142]
• 4: Josep Díaz , Maria J. Serna , Dimitrios M. Thilikos, (H, C, K)-Coloring: Fast, Easy, and Hard Cases, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science, p.304-315, August 27-31, 2001
• 5: J. Diaz, M. Serna and D.M. Thilikos, The complexity of parameterized H-colorings: a survey, pre-print (2000).
• 6: Martin Dyer , Alan Frieze , Mark Jerrum, On Counting Independent Sets in Sparse Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.210, October 17-18, 1999
• 7: M. Dyer and C. Greenhill, Random walks on combinatorial objects. In J.D. Lamb and D.A. Preece, editors, Surveys in Combinatorics, volume 267 of London (MATH)ematical Society Lecture Note Series, pages 101--136. Cambridge University Press, 1999.
• 8: Martin Dyer , Catherine Greenhill, On Markov chains for independent sets, Journal of Algorithms, v.35 n.1, p.17-49, April 2000 [doi>10.1006/jagm.1999.1071]
• 9: Martin Dyer , Catherine Greenhill, The complexity of counting graph homomorphisms, Random Structures & Algorithms, v.17 n.3-4, p.260-289, Oct. 2000
• 10: Martin E. Dyer , Leslie Ann Goldberg , Catherine S. Greenhill , Mark Jerrum, On the relative complexity of approximate counting problems, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.108-119, September 05-08, 2000
• 11: M. Dyer, M. Jerrum and E. Vigoda, Rapidly mixing Markov chains for dismantleable constraint graphs, Pre-print 2001.
• 12: Anna Galluccio , Pavol Hell , Jaroslav Nešetřil, The complexity of H-colouring of bounded degree graphs, Discrete Mathematics, v.222 n.1-3, p.101-109, July 28 2000 [doi>10.1016/S0012-365X(00)00009-1]
• 13: Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
• 14: Mark Jerrum, A very simple algorithm for estimating the number of k-colorings of a low-degree graph, Random Structures & Algorithms, v.7 n.2, p.157-165, September 1995 [doi>10.1002/rsa.3240070205]
• 15: M. Jerrum, Sampling and Counting, Chapter 3 of Lecture Notes from a recent Nachdiplomvorlesung at ETH-Zürich "Counting, sampling and integrating: algorithms and complexity". Available at http://www.dcs.ed.ac.uk/home/mrj/pubs.html.
• 16: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 17: E. Vigoda, Improved bounds for sampling colorings, Journal of (MATH)ematical Physics, 41 (2000) 1555--1569.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Algorithms, Experimentation, Performance, Theory