Abstract
Approximate random k-colouring of a graph G = (V,E), efficiently, is a very well studied problem in computer science and statistical physics. It amounts to constructing, in polynomial time, a k-colouring of G which is distributed close to Gibbs distribution. Here, we deal with the problem when the underlying graph is an instance of Erdős-Rényi random graph G(n,d/n), where d is fixed.
This paper improves on the approximate sampling colouring algorithm proposed in SODA 2012. We provide improved performance guarantees for this efficient algorithm, as we reduce the lower bound of the number of colours required by a factor of 1/2. In particular, we show the following statement for the accuracy of algorithm: For typical instances of G(n,d/n) the algorithm outputs a k-colouring of G(n,d/n) which is asymptotically uniform as long k ≥ (1 + ε)d. For the improvement we make an extensive use of the spatial correlation decay properties of the Gibbs distribution and the local treelike structure of the underlying graph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Achlioptas, D., Coja-Oghlan, A.: Algorithmic Barriers from Phase Transitions. In: Proc. of FOCS 2008, pp. 793–802 (2008)
Aldous, D.: Random walks of finite groups and rapidly mixing Markov chains. In: Séminaire de Probabilités XVII 1981/82, pp. 243–297. Springer, Heidelberg (1983)
van den Berg, J., Maes, C.: Disagreement percolation in the study of Markov fields. Annals of Probability 22, 749–763 (1994)
Dyer, M., Flaxman, A., Frieze, A.M., Vigoda, E.: Random colouring sparse random graphs with fewer colours than the maximum degree. Journal R.S.A. 29, 450–465 (2006)
Dyer, M., Frieze, A.M., Hayes, A., Vigoda, E.: Randomly colouring constant degree graphs. In: Proc. of 45th FOCS, pp. 582–589 (2004)
Efthymiou, C.: Switching colouring of G(n,d/n) for sampling up to Gibbs Uniqueness Threshold. Technical Report on arxiv.org
Efthymiou, C.: MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold. In: Proc. of SODA 2014, pp. 305–316 (2014)
Efthymiou, C.: A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours. In: Proc. of SODA 2012, pp. 272–280 (2012)
Jonasson, J.: Uniqueness of Uniform Random Colorings of Regular Trees. Statistics & Probability Letters 57, 243–248 (2001)
Janson, S., Luczak, T., Ruciński, A.: Random graphs. Wiley and Sons, Inc. (2000)
Jerrum, M., Sinclair, A.: The Markov chain Monte Carlo method:an approach to approximate counting and integration. In: Dorit, H. (ed.) Approximation Algorithms for NP-Hard Problems. PWS (1996)
Molloy, M.: The freezing threshold for k-colourings of a random graph. In: Proc. of the 44th ACM Symposium on Theory of Computing (STOC 2012), pp. 921–930 (2012)
Mossel, E., Sly, A.: Gibbs Rapidly Samples Colorings of G n,d/n . Journal Probability Theory and Related Fields 148(1-2) (2010)
Vigoda, E.: Improved bounds for sampling colorings. Journal of Mathematical Physics 41(3), 1555–1569 (2000); A preliminary version appears in FOCS 1999
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Efthymiou, C. (2014). Switching Colouring of G(n,d/n) for Sampling up to Gibbs Uniqueness Threshold. In: Schulz, A.S., Wagner, D. (eds) Algorithms - ESA 2014. ESA 2014. Lecture Notes in Computer Science, vol 8737. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44777-2_31
Download citation
DOI: https://doi.org/10.1007/978-3-662-44777-2_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-44776-5
Online ISBN: 978-3-662-44777-2
eBook Packages: Computer ScienceComputer Science (R0)