Speaker:
Charilaos Efthymiou
Title:
A simple algorithm for random colouring G(n,d/n) using
(2+\epsilon)d colours.
Abstract:
Approximate random k-colouring of a graph G=(V,E) is a well-studied
problem in computer science and statistical physics. It amounts to
constructing a k-colouring of G which is distributed close to Gibbs
distribution, i.e. the uniform distribution over all the k-colourings
of G.
In this talks we deal with the problem when the underlying graph is an
instance of Erdos-Renyi random graph G(n,p), where p=d/n and d is fixed.
I will present a new efficient algorithm for approximate random k-colouring.
With probability 1-n^{-\Omega(1)} over the input graph instances G(n,d/n)
and for k>(2+\epsilon)d, the algorithm returns a k-colouring distributed
within total variation distance 1-n^{-Omega(1)} from the Gibbs
distribution.
The algorithm is neither MCMC based nor inspired by the message passing
heuristics introduced by statistical physicists. It is a combinatorial one
and it is based on the following simple idea. Remove edges of the input
graph G(n,d/n) until it becomes so simple that we can take a random
colouring efficiently. Random colour this simple subgraph. Then, rebuild
the initial graph by adding the deleted edges one by one. Each time we add
an edge update the colouring of some vertices so as the colouring of the
graph (with the added edge) to be random.