Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-164 | 21st May 2020 12:48

Improved Bounds for Perfect Sampling of k-Colorings in Graphs

RSS-Feed




Revision #1
Authors: Siddharth Bhandari, Sayantan Chakraborty
Accepted on: 21st May 2020 12:49
Downloads: 599
Keywords: 


Abstract:

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 \emph{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 a 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 with sub-quadratic number of colors in general.

Our algorithm (like several other perfect sampling algorithms including Huber's) is based on the Coupling from the Past method. Inspired by the \emph{bounding chain} approach, pioneered independently by
Huber~(STOC 1998) and
H\"aggstr\"om \& Nelander~(Scand.{} J.{} Statist., 1999), we employ a novel bounding chain to derive our result for the graph coloring problem.



Changes to previous version:

Rewrite of previous version.


Paper:

TR19-164 | 6th November 2019 11:48

Improved bounds for perfect sampling of k-colorings in graphs





TR19-164
Authors: Siddharth Bhandari, Sayantan Chakraborty
Publication: 17th November 2019 12:56
Downloads: 985
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint