Correlation decay and deterministic FPTAS for counting list-colorings of a graph

ABSTRACT

We propose a deterministic algorithm for approximately counting the number of list colorings of a graph. Under the assumption that the graph is triangle free, the size of every list is at least αΔ, where α is an arbitrary constant bigger than α = 2.8432 ..., the solution of αe^-1/α = 2, and α is the maximum degree of the graph, we obtain the following results. For the case when the size of the each list is a large constant, we show the existence of a deterministic FPTAS for computing the total number of list colorings. The same deterministic algorithm has complexity 2^O(log² n) without any assumptions on the sizes of the lists, where n is the size of the instance.

Our results are not based on the most powerful existing counting technique - rapidly mixing Markov chain method. Rather we build upon concepts from statistical physics, in particular, the decay of correlation phenomena and its implication for the uniqueness of Gibbs measures in infinite graphs. This approach was proposed in two recent papers [BG06] and [Wei05]. The principle insight of the present work is that the correlation decay property can be established with respect to certain computation tree, as opposed to the conventional correlation decay property which is typically established with respect to graph theoretic neighborhoods of a given node. This allows truncation of computation at a logarithmic depth in order to obtain polynomial accuracy in polynomial time. While the analysis conducted in this paper is limited to the problem of counting list colorings, the proposed algorithm can be extended to an arbitrary constraint satisfaction problem in a straightforward way.

REFERENCES

• 1: {BF87} I. Bárány and Z. Füredy, Computing the volume is difficult, Discrete Comput. Geom. 2 (1987), no. 4, 319--326.
• 2: Antar Bandyopadhyay , David Gamarnik, Counting without sampling: new algorithms for enumeration problems using statistical physics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.890-899, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109655]
• 3: {BW02} G. Brightwell and P. Winkler, Random colorings of a Cayley tree, in Contemporary Combinatorics, B. Bollobas, ed., Bolyai Society Mathematical Studies, 2002, pp. 247--276.
• 4: {BW04} G. R. Brightwell and P. Winkler, Graph homomorphisms and long range action, in Graphs, morphisms and statistical physics (Nesetril and Winkler eds.), DI-MACS series in discrete mathematics and computer science, 2004, pp. 29--47.
• 5: Martin Dyer , Alan Frieze , Thomas P. Hayes , Eric Vigoda, Randomly Coloring Constant Degree Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.582-589, October 17-19, 2004 [doi>10.1109/FOCS.2004.57]
• 6: {Ele86} G. Elekes, A geometric inequality and the complexity of computing volume, Discrete Comput. Geom. 1 (1986), no. 4, 289--292.
• 7: {FV06} A. Frieze and E. Vigoda, Survey of Markov chains for randomly sampling colorings, To appear in Festschrift for Dominic Welsh (2006).
• 8: Leslie Ann Goldberg , Russell Martin , Mike Paterson, Strong Spatial Mixing with Fewer Colors for Lattice Graphs, SIAM Journal on Computing, v.35 n.2, p.486-517, 2005 [doi>10.1137/S0097539704445470]
• 9: 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]
• 10: {Jon02} J. Jonasson, Uniqueness of uniform random colorings of regular trees, Statistics and Probability Letters 57 (2002), 243--248.
• 11: {JS06} K. Jung and D. Shah, On correctness of belief propagation algorithm, Preprint (2006).
• 12: {Sha05} D. Shah, Max weight independent set and matching via max-product, Preprint (2005).
• 13: {SS97} J. Salas and A. D. Sokal, Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem, J. Statist. Phys. 86 (1997), no. 3-4, 551--579.
• 14: {TJ02} S. Tatikonda and M. I. Jordan, Loopy belief propagation and gibbs measures, In Uncertainty in Artificial Intelligence (UAI), D. Koller and A. Darwiche (Eds)., 2002.
• 15: {Vig00} E. Vigoda, Improved bounds for sampling colorings, Journal of Mathematical Physics (2000).
• 16: {Wei05} D. Weitz, Counting down the tree, Submitted. (2005).
• 17: {YFW00} J. Yedidia, W. Freeman, and Y. Weiss, Understanding Belief Propagation and its generalizations, Mitsubishi Elect. Res. Lab. (2000), no. TR-2001-22.