The Library
A simple algorithm for sampling colourings of G(N,D/N) up to Gibbs Uniqueness threshold
Tools
Efthymiou, Charilaos (2016) A simple algorithm for sampling colourings of G(N,D/N) up to Gibbs Uniqueness threshold. SIAM Journal on Computing, 45 (6). pp. 2087-2116. doi:10.1137/140977643 ISSN 0097-5397.
|
PDF
WRAP-simple-algorithm-sampling-colourings-gibbs-uniqueness--Efthymiou-2016.pdf - Accepted Version - Requires a PDF viewer. Download (805Kb) | Preview |
Official URL: https://doi.org/10.1137/140977643
Abstract
Approximate random $k$-colouring of a graph G 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 in polynomial time. Here, we deal with the problem when the underlying graph is an instance of Erdos-Renyi random graph G(n,d/n), where d is a sufficiently large constant.
We propose a novel efficient algorithm for approximate random k-colouring G(n,d/n) for any k>(1+\epsilon)d. To be more specific, with probability at least 1-n^{-\Omega(1)} over the input instances G(n,d/n) and for k>(1+\epsilon)d, the algorithm returns a k-colouring which is distributed within total variation distance n^{-\Omega(1)} from the Gibbs distribution of the input graph instance.
The algorithm we propose is neither a MCMC one nor inspired by the message passing algorithms proposed by statistical physicists. Roughly the idea is as follows: Initially we remove sufficiently many edges of the input graph. This results in a ``simple graph" which can be $k$-coloured randomly efficiently. The algorithm colours randomly this simple graph. Then it puts back the removed edges one by one. Every time a new edge is put back the algorithm updates the colouring of the graph so that the colouring remains random.
The performance of the algorithm depends heavily on certain spatial correlation decay properties of the Gibbs distribution.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Algorithms | ||||||
Journal or Publication Title: | SIAM Journal on Computing | ||||||
Publisher: | Society for Industrial and Applied Mathematics (SIAM) | ||||||
ISSN: | 0097-5397 | ||||||
Official Date: | 29 November 2016 | ||||||
Dates: |
|
||||||
Volume: | 45 | ||||||
Number: | 6 | ||||||
Page Range: | pp. 2087-2116 | ||||||
DOI: | 10.1137/140977643 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | “First Published in SIAM Journal on Computing in 45(6) 2016, published by the Society for Industrial and Applied Mathematics (SIAM)” © by SIAM. Unauthorized reproduction of this article is prohibited.”) | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Copyright Holders: | © 2016, Society for Industrial and Applied Mathematics | ||||||
Date of first compliant deposit: | 15 March 2019 | ||||||
Date of first compliant Open Access: | 20 March 2019 | ||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year