ECCC-Report TR19-164https://eccc.weizmann.ac.il/report/2019/164Comments and Revisions published for TR19-164en-usSun, 17 Nov 2019 12:56:43 +0200
Paper TR19-164
| Improved bounds for perfect sampling of $k$-colorings in graphs |
Siddharth Bhandari,
Sayantan Chakraborty
https://eccc.weizmann.ac.il/report/2019/164 We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k > 3\Delta$, and returns a random proper $k$-coloring of $G$. The
distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; the expected running time of the algorithm is $\mathrm{poly}(k,n)=\widetilde{O}(n\Delta^2\cdot \log(k))$.
This improves upon a result of Huber~(STOC 1998) who obtained polynomial time perfect sampling algorithm for $k>\Delta^2+2\Delta$.
Prior to our work, no algorithm with expected running time $\mathrm{poly}(k,n)$ was known to guarantee perfectly sampling for $\Delta = \omega(1)$ and for any $k \leq \Delta^2+2\Delta$.
Our algorithm (like several other perfect sampling algorithms including Huber's) is based on the Coupling from the Past method. Inspired by the bounding chain approach pioneered independently by H\"aggstr\"om \& Nelander~(Scand.{} J.{} Statist., 1999) and Huber~(STOC 1998), our algorithm is based on a novel bounding chain for the coloring problem.Sun, 17 Nov 2019 12:56:43 +0200https://eccc.weizmann.ac.il/report/2019/164