 |
Center for Nonlinear Studies |
We consider the coloring problem for a graph G on n vertices and maximum degree d where the colors are drawn from a finite set of q colors. In the regime where q is at least d+2, there are exponentially many valid colorings of the graph. Computing this number exactly is known to be a #P-hard problem. The number of valid colorings is also equal to the partition function of the natural graphical model associated with the coloring problem. We explore algorithms which aim at approximating this partition function up to an inverse polynomial accuracy in time polynomial in n. We give a brief overview of randomized algorithms based on fast mixing of the Metropolis Hastings markov chain. We then explore deterministic algorithms which exploit the decay of correlations or spatial mixing in the associated graphical model to provide approximations by local computations. We cover some recent results on spatial mixing and their relationship to approximate counting. We conclude with a general conjecture about the hardness of approximability of the partition function in spin systems with local interactions.
Host: Misha Chertkov