Improved Bounds for Perfect Sampling of k-Colorings in Graphs.

Abstract: I this talk we will present a randomized algorithm that takes as input an undirected n-vertex graph G with maximum degree Δ and an integer k>3Δ, 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 poly(k,n)=O(nΔ^2⋅log(k)). This improves upon a result of Huber~(STOC 1998) who obtained a polynomial time perfect sampling algorithm for k>Δ^2+2Δ. Prior to our work, no algorithm with expected running time 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äggström & Nelander~(Scand. J. Statist., 1999), we employ a novel bounding chain to derive our result for the graph coloring problem.

probability

Audience: advanced learners

Bangalore Probability Seminar

Series comments: The link to zoom meeting can be found on the seminar's google calendar - www.isibang.ac.in/~d.yogesh/BPS.html