Document Open Access Logo

Randomly Coloring Graphs of Logarithmically Bounded Pathwidth

Author Shai Vardi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.57.pdf
  • Filesize: 0.5 MB
  • 19 pages

Document Identifiers

Author Details

Shai Vardi
  • Krannert School of Management, Purdue University, West Lafayette, IN, 47907, USA

Funding

  • Vardi, Shai: Supported in part by the Linde Foundation and NSF grants CNS-1254169 and CNS-1518941.

Cite As Get BibTex

Shai Vardi. Randomly Coloring Graphs of Logarithmically Bounded Pathwidth. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.57

Abstract

We consider the problem of sampling a proper k-coloring of a graph of maximal degree Delta uniformly at random. We describe a new Markov chain for sampling colorings, and show that it mixes rapidly on graphs of logarithmically bounded pathwidth if k >=(1+epsilon)Delta, for any epsilon>0, using a hybrid paths argument.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Markov-chain Monte Carlo methods
Keywords
  • Random coloring
  • Glauber dynamics
  • Markov-chain Monte Carlo

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. David J. Aldous. Random walks on finite groups and rapidly mixing markov chains. Séminaire de probabilités de Strasbourg, 17:243-297, 1983. URL: http://eudml.org/doc/113445.
  2. Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres. Glauber dynamics on trees and hyperbolic graphs. Probability Theory and Related Fields, 131(3):311-340, 2005. Google Scholar
  3. Umberto Bertelè and Francesco Brioschi. Nonserial Dynamic Programming. Academic Press, Inc., Orlando, FL, USA, 1972. Google Scholar
  4. H.L. Bodlaender, J.R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. Journal of Algorithms, 18(2):238-255, 1995. Google Scholar
  5. G.R. Brightwell and P. Winkler. Random coloring of a Cayley tree. Contemporary combintorics, 10:247-276, 2002. Google Scholar
  6. Graham Brightwell and Peter Winkler. Counting linear extensions is #P-complete. In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC '91, pages 175-181, 1991. Google Scholar
  7. Andrei Z. Broder. How hard is to marry at random? (on the approximation of the permanent). In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC '86, pages 50-58, 1986. Google Scholar
  8. Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. A note on multiflows and treewidth. Algorithmica, 54(3):400-412, 2009. Google Scholar
  9. Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of markov chains. Ann. Appl. Probab., 1(1):36-61, 02 1991. URL: http://dx.doi.org/10.1214/aoap/1177005980.
  10. Martin E. Dyer, Abraham D. Flaxman, Alan M. Frieze, and Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms, 29(4):450-465, 2006. Google Scholar
  11. Martin E. Dyer and Alan M. Frieze. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms, 23(2):167-179, 2003. Google Scholar
  12. Martin E. Dyer and Alan M. Frieze. Randomly coloring random graphs. Random Struct. Algorithms, 36(3):251-272, 2010. Google Scholar
  13. Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, and Eric Vigoda. Randomly coloring constant degree graphs. Random Struct. Algorithms, 43(2):181-200, 2013. Google Scholar
  14. Charilaos Efthymiou. A simple algorithm for sampling colorings of g(n, d/n) up to the gibbs uniqueness threshold. SIAM J. Comput., 45(6):2087-2116, 2016. Google Scholar
  15. J. A. Ellis, I. H. Sudborough, and J. S. Turner. The vertex separation and search number of a graph. Inf. Comput., 113(1):50-79, 1994. Google Scholar
  16. Alan Frieze and Eric Vigoda. A survey on the use of markov chains to randomly sample colorings. In Combinatorics, Complexity and Chance. Oxford University Press, 2007. URL: http://dx.doi.org/10.1093/acprof:oso/9780198571278.003.0004.
  17. Leslie Ann Goldberg, Mark Jerrum, and Marek Karpinski. The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms, 36(4):464-476, 2010. Google Scholar
  18. Heng Guo and Mark Jerrum. Random cluster dynamics for the ising model is rapidly mixing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 1818-1827, 2017. Google Scholar
  19. Venkatesan Guruswami. Rapidly mixing markov chains: A comparison of techniques (A survey). CoRR, abs/1603.01512, 2016. URL: http://arxiv.org/abs/1603.01512.
  20. Thomas P. Hayes. Randomly coloring graphs of girth at least five. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 269-278, 2003. Google Scholar
  21. Thomas P. Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS, pages 39-46, 2006. Google Scholar
  22. Thomas P. Hayes, Juan Carlos Vera, and Eric Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, '07, pages 450-458, 2007. Google Scholar
  23. Thomas P. Hayes, Juan Carlos Vera, and Eric Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. Random Struct. Algorithms, 47(4):731-759, 2015. Google Scholar
  24. Thomas P. Hayes and Eric Vigoda. A non-markovian coupling for randomly sampling colorings. In 44th Symposium on Foundations of Computer Science (FOCS '03), Proceedings, pages 618-627, 2003. Google Scholar
  25. Thomas P. Hayes and Eric Vigoda. Coupling with the stationary distribution and improved sampling for colorings and independent sets. Ann. Appl. Probab., 16(3):1297-1318, 2006. Google Scholar
  26. Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms, 7(2):157-166, 1995. Google Scholar
  27. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149-1178, 1989. Google Scholar
  28. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671-697, 2004. Google Scholar
  29. Nancy G. Kinnersley. The vertex separation number of a graph equals its path-width. Information Processing Letters, 42(6):345-350, 1992. Google Scholar
  30. Ephraim Korach and Nir Solel. Tree-width, path-width, and cutwidth. Discrete Applied Mathematics, 43(1):97-101, 1993. Google Scholar
  31. V. S. Anil Kumar and H. Ramesh. Coupling vs. conductance for the jerrum-sinclair chain. Random Struct. Algorithms, 18(1):1-17, 2001. Google Scholar
  32. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006. Google Scholar
  33. Jun S. Liu. Monte Carlo Strategies in Scientific Computing. Springer Publishing Company, Incorporated, 2008. Google Scholar
  34. Pinyan Lu, Kuan Yang, Chihao Zhang, and Minshen Zhu. An FPTAS for counting proper four-colorings on cubic graphs. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1798-1817, 2017. Google Scholar
  35. Brendan Lucier and Michael Molloy. The Glauber dynamics for colorings of bounded degree trees. SIAM J. Discrete Math., 25(2):827-853, 2011. Google Scholar
  36. Fabio Martinelli, Alistair Sinclair, and Dror Weitz. Fast mixing for independent sets, colorings and other models on trees. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pages 456-465, 2004. Google Scholar
  37. Michael Molloy. The Glauber dynamics on colorings of a graph with high girth and maximum degree. SIAM J. Comput., 33(3):721-737, 2004. Google Scholar
  38. Ben Morris and Alistair Sinclair. Random walks on truncated cubes and sampling 0-1 knapsack solutions. SIAM J. Comput., 34(1):195-226, 2004. Google Scholar
  39. Elchanan Mossel and Allan Sly. Gibbs rapidly samples colorings of g(n, d/n). Probability Theory and Related Fields, 148(1):37-69, Sep 2010. Google Scholar
  40. R. B. Potts. Some generalized order-disorder transformations. Mathematical Proceedings of the Cambridge Philosophical Society, 48(1):106-109, 1952. URL: http://dx.doi.org/10.1017/S0305004100027419.
  41. Neil Robertson and P.D. Seymour. Graph minors. i. excluding a forest. Journal of Combinatorial Theory, Series B, 35(1):39-61, 1983. Google Scholar
  42. Neil Robertson and P.D Seymour. Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. Google Scholar
  43. J. Salas and A.D. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J Stat Phys, 86:551-579, 1997. Google Scholar
  44. Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability & Computing, 1:351-370, 1992. Google Scholar
  45. Prasad Tetali, Juan Carlos Vera, Eric Vigoda, and Linji Yang. Phase transition for the mixing time of the Glauber dynamics for coloring regular trees. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 1646-1656, 2010. Google Scholar
  46. Eric Vigoda. Improved bounds for sampling colorings. In 40th Annual Symposium on Foundations of Computer Science, FOCS '99, pages 51-59, 1999. Google Scholar
  47. Jian-Sheng Wang, Robert H. Swendsen, and Roman Kotecký. Antiferromagnetic potts models. Phys. Rev. Lett., 63:109-112, Jul 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact