Document Open Access Logo

Constant-Time Dynamic (Δ+1)-Coloring

Authors Monika Henzinger , Pan Peng

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2020.53.pdf
  • Filesize: 0.59 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Dynamic graph algorithms
  • Graph coloring
  • Random sampling

Metrics

Abstract

We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation.

Cite As Get BibTex

Monika Henzinger and Pan Peng. Constant-Time Dynamic (Δ+1)-Coloring. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.STACS.2020.53

Author Details

Monika Henzinger
  • University of Vienna, Faculty of Computer Science, Vienna, Austria
Pan Peng
  • Department of Computer Science, University of Sheffield, Sheffield, UK

Funding

The research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.

References

  1. Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, and Sander Verdonschot. Dynamic graph coloring. In Workshop on Algorithms and Data Structures, pages 97-108. Springer, 2017. Google Scholar
  2. Leonid Barenboim and Tzalik Maimon. Fully-dynamic graph algorithms with sublinear time inspired by distributed computing. Procedia Computer Science, 108:89-98, 2017. Google Scholar
  3. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms (TALG), 8(4):35, 2012. Google Scholar
  4. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 2019. IEEE, 2019. Google Scholar
  5. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1-20. SIAM, 2018. Google Scholar
  6. Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, and Shay Solomon. Fully dynamic (δ+1) coloring in constant update time. Private communication. Google Scholar
  7. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2+ε)-approximate minimum vertex cover in O(1/ε²) amortized update time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1872-1885. SIAM, 2019. Google Scholar
  8. Manuel Blum, Robert W Floyd, Vaughan Pratt, Ronald L Rivest, and Robert E Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448-461, 1973. Google Scholar
  9. R. L. Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194–197, 1941. Google Scholar
  10. Keren Censor-Hillel, Elad Haramaty, and Zohar Karnin. Optimal dynamic distributed mis. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 217-226. ACM, 2016. Google Scholar
  11. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), 2019. IEEE, 2019. Google Scholar
  12. Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert Endre Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738-761, 1994. Google Scholar
  13. Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1937-1945. SIAM, 2019. Google Scholar
  14. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. Google Scholar
  15. Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees (preliminary version). In STOC, pages 252-257, 1983. Google Scholar
  16. Monika R Henzinger and Valerie King. Maintaining minimum spanning trees in dynamic graphs. In International Colloquium on Automata, Languages, and Programming, pages 594-604. Springer, 1997. Google Scholar
  17. Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM, 46(4):502-516, 1999. URL: https://doi.org/10.1145/320211.320215.
  18. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  19. Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Algorithms-ESA 2015, pages 742-753. Springer, 2015. Google Scholar
  20. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In SODA, pages 1131-1141, 2013. Google Scholar
  21. Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge university press, 2005. Google Scholar
  22. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^1/2-ε)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122-1129. ACM, 2017. Google Scholar
  23. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 950-961. IEEE, 2017. Google Scholar
  24. Mihai Patrascu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932-963, 2006. URL: https://doi.org/10.1137/S0097539705447256.
  25. Shay Solomon. Fully dynamic maximal matching in constant update time. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 325-334. IEEE, 2016. Google Scholar
  26. Shay Solomon and Nicole Wein. Improved dynamic graph coloring. In 26th Annual European Symposium on Algorithms, 2018. Google Scholar
  27. Dominic JA Welsh and Martin B Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85-86, 1967. Google Scholar
  28. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1130-1143. ACM, 2017. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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