Correlation decay and deterministic FPTAS for counting colorings of a graph

We construct a deterministic algorithm for approximately counting the number of colorings of a graph. Under the assumption that the graph is triangle-free and the number of colors is at least αΔ, where α   is an arbitrary constant bigger than α⁎⁎=2.8432…α⁎⁎=2.8432… , and Δ is the maximum degree of the graph, we obtain the following results. For the case when the number of colors is a large constant, we prove the existence of a deterministic FPTAS for computing the total number of colorings. The same deterministic algorithm has complexity 2O(log2n)2O(log2n), without any assumptions on the number of colors, where n is the instance size. We further extend our method to the general problem of computing the partition function of a discrete Markov random field (MRF) model. Under certain assumptions relating the cardinality of the alphabet, the degree of the graph and the interacting potentials, we construct a deterministic FPTAS for computing the partition function of a MRF.In contrast to our results, the known counting technique – rapidly mixing Markov chain method – is based on randomization. Thus our result is the first non-trivial deterministic FPTAS for the problem of counting the number of colorings. Our approach builds on a certain statistical physics concept, specifically, 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 by Bandyopadhyay and Gamarnik (2008) [1] and Weitz (2006) [25]. The main distinction of this work is that we establish the correlation decay property on a computation tree arising from a certain recursive procedure, rather than reducing the problem to the one on a self-avoiding tree of a graph, as is done in Weitz (2006) [25]. This lets us deal with problems with more than two colors, which the tree-based approach of Weitz (2006) [25] is not capable of solving.