2020/07/13 by Jain, Vishesh, Sah, Ashwin, Sawhney, Mehtaab
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2007.06360
We present a randomized algorithm which takes as input an undirected graph G on n vertices with maximum degree Δ, and a number of colors k ≥ (8/3 + oΔ(1))Δ, and returns -- in expected time O(nΔ2logk) -- a proper k-coloring of G distributed perfectly uniformly on the set of all proper k-colorings of G. Notably, our sampler breaks the barrier at k = 3Δ encountered in recent work of Bhandari and Chakraborty [STOC 2020]. We also sketch how to modify our methods to relax the restriction on k to k ≥ (8/3 - ε0)Δ for an absolute constant ε0 > 0. As in the work of Bhandari and Chakraborty, and the pioneering work of Huber [STOC 1998], our sampler is based on Coupling from the Past [Propp&Wilson, Random Struct. Algorithms, 1995] and the bounding chain method [Huber, STOC 1998; Häggström&Nelander, Scand. J. Statist., 1999]. Our innovations include a novel bounding chain routine inspired by Jerrum's analysis of the Glauber dynamics [Random Struct. Algorithms, 1995], as well as a preconditioning routine for bounding chains which uses the algorithmic Lovász Local Lemma [Moser&Tardos, J.ACM, 2010].