Document Open Access Logo

Improved Dynamic Graph Coloring

Authors Shay Solomon, Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.72.pdf
  • Filesize: 433 kB
  • 16 pages

Document Identifiers

Author Details

Shay Solomon
  • IBM Research, TJ Watson Research Center, Yorktown Heights, NY USA
Nicole Wein
  • EECS, Massachusetts Institute of Technology, Cambridge, MA USA

Cite AsGet BibTex

Shay Solomon and Nicole Wein. Improved Dynamic Graph Coloring. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.72

Abstract

This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n^{1-epsilon} for any epsilon > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs. Towards understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm for C-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step. Optimizing the number of recolorings, sometimes referred to as the recourse bound, is important for various practical applications. In WADS'17, Barba et al. devised two complementary algorithms: For any beta > 0, the first (respectively, second) maintains an O(C beta n^{1/beta}) (resp., O(C beta))-coloring while recoloring O(beta) (resp., O(beta n^{1/beta})) vertices per update. Barba et al. also showed that the second trade-off appears to exhibit the right behavior, at least for beta = O(1): Any algorithm that maintains a c-coloring of an n-vertex dynamic forest must recolor Omega(n^{2/(c(c-1))}) vertices per update, for any constant c >= 2. Our contribution is two-fold: - We devise a new algorithm for general graphs that improves significantly upon the first trade-off in a wide range of parameters: For any beta > 0, we get a O~(C/(beta)log^2 n)-coloring with O(beta) recolorings per update, where the O~ notation supresses polyloglog(n) factors. In particular, for beta = O(1) we get constant recolorings with polylog(n) colors; not only is this an exponential improvement over the previous bound, but it also unveils a rather surprising phenomenon: The trade-off between the number of colors and recolorings is highly non-symmetric. - For uniformly sparse graphs, we use low out-degree orientations to strengthen the above result by bounding the update time of the algorithm rather than the number of recolorings. Then, we further improve this result by introducing a new data structure that refines bounded out-degree edge orientations and is of independent interest.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Dynamic graph algorithms
Keywords
  • coloring
  • dynamic graph algorithms
  • graph arboricity
  • edge orientations

Metrics

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

References

  1. Ittai Abraham, Shiri Chechik, and Sebastian Krinninger. Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, January 16-19, 2017, pages 440-452, 2017. Google Scholar
  2. A. Andersson and Mikkel Thorup. Dynamic ordered sets with exponential search trees. J. ACM, 54(3):13, 2007. Google Scholar
  3. Srinivasa R Arikati, Anil Maheshwari, and Christos D Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78(1-3):1-16, 1997. Google Scholar
  4. Baruch Awerbuch, Michael Luby, Andrew V Goldberg, and Serge A Plotkin. Network decomposition and locality in distributed computation. In FOCS, 1989., 30th Annual Symposium on, pages 364-369. IEEE, 1989. Google Scholar
  5. Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen, Marcel Roeloffzen, and Sander Verdonschot. Dynamic graph coloring. In Proceedings of the 15th International Symposium on Algorithms and Data Structures, WADS 2017, St. John’s, NL, Canada, July 31 - August 2, 2017, pages 97-108, 2017. Google Scholar
  6. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. Distributed Computing, 22(5-6):363-379, 2010. Google Scholar
  7. Leonid Barenboim and Michael Elkin. Distributed graph coloring: Fundamentals and recent developments. Synthesis Lectures on Distributed Computing Theory, 4(1):1-171, 2013. Google Scholar
  8. Leonid Barenboim and Tzalik Maimon. Fully-dynamic graph algorithms with sublinear time inspired by distributed computing. In Proceedings of the International Conference on Computational Science, ICCS 2017, Zurich, Switzerland, June 12-14, 2017, pages 89-98, 2017. Google Scholar
  9. Edvin Berglin and Gerth Stølting Brodal. A simple greedy algorithm for dynamic graph orientation. In LIPIcs-Leibniz International Proceedings in Informatics, volume 92. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  10. Aaron Bernstein and Cliff Stein. Fully dynamic matching in bipartite graphs. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Part I, pages 167-179, 2015. Google Scholar
  11. Aaron Bernstein and Cliff Stein. Faster fully dynamic matchings with small approximation ratios. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 692-711, 2016. Google Scholar
  12. Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1-20, 2018. Google Scholar
  13. Greg Bodwin and Sebastian Krinninger. Fully dynamic spanners with worst-case update time. arXiv preprint arXiv:1606.07864, 2016. Google Scholar
  14. G. S. Brodal and R. Fagerberg. Dynamic representation of sparse graphs. In Proc. of 6th WADS, pages 342-351, 1999. Google Scholar
  15. Moses Charikar and Shay Solomon. Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. arXiv preprint arXiv:1711.06883, 2017. Google Scholar
  16. Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1):32-53, 1986. Google Scholar
  17. Artur Czumaj and Christian Sohler. Testing hypergraph coloring. In International Colloquium on Automata, Languages, and Programming, pages 493-505. Springer, 2001. Google Scholar
  18. Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs. communities, 28:43, 2018. Google Scholar
  19. Paul Dietz and Daniel Sleator. Two algorithms for maintaining order in a list. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 365-372. ACM, 1987. Google Scholar
  20. Paul F Dietz and Rajeev Raman. Persistence, amortization and randomization. In Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, pages 78-88. Society for Industrial and Applied Mathematics, 1991. Google Scholar
  21. Paul F Dietz and Rajeev Raman. A constant update time finger search tree. Information Processing Letters, 52(3):147-154, 1994. Google Scholar
  22. Zdeněk Dvořák and Vojtěch Tuma. A dynamic data structure for counting subgraphs in sparse graphs. In Workshop on Algorithms and Data Structures, pages 304-315. Springer, 2013. Google Scholar
  23. Talya Eden, Reut Levi, and Dana Ron. Testing bounded arboricity. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2081-2092. SIAM, 2018. Google Scholar
  24. Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In European Symposium on Algorithms, pages 394-405. Springer, 2014. Google Scholar
  25. Daniele Frigioni, Alberto Marchetti-Spaccamela, and Umberto Nanni. Fully dynamic shortest paths in digraphs with arbitrary arc weights. Journal of Algorithms, 49(1):86-113, 2003. Google Scholar
  26. Andrew V Goldberg, Serge A Plotkin, and Gregory E Shannon. Parallel symmetry-breaking in sparse graphs. SIAM Journal on Discrete Mathematics, 1(4):434-446, 1988. Google Scholar
  27. Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  28. Bradley Hardy, Rhyd Lewis, and Jonathan Thompson. Modifying colourings between time-steps to tackle changes in dynamic random graphs. In European Conference on Evolutionary Computation in Combinatorial Optimization, pages 186-201. Springer, 2016. Google Scholar
  29. Bradley Hardy, Rhyd Lewis, and Jonathan Thompson. Tackling the edge dynamic graph colouring problem with and without future adjacency information. Journal of Heuristics, pages 1-23, 2017. Google Scholar
  30. M. He, G. Tang, and N. Zeh. Orienting dynamic graphs, with applications to maximal matchings and adjacency queries. In Proc. 25th ISAAC, pages 128-140, 2014. Google Scholar
  31. Shweta Jain and C Seshadhri. A fast and provable method for estimating clique counts using turán’s theorem. In Proceedings of the 26th International Conference on World Wide Web, pages 441-449. International World Wide Web Conferences Steering Committee, 2017. Google Scholar
  32. Alexis Kaporis, Christos Makris, George Mavritsakis, Spyros Sioutas, Athanasios Tsakalidis, Kostas Tsichlas, and Christos Zaroliagis. Isb-tree: a new indexing scheme with efficient expected behaviour. In International Symposium on Algorithms and Computation, pages 318-327. Springer, 2005. Google Scholar
  33. Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In Proc. 33rd ICALP, pages 226-237, 2006. Google Scholar
  34. T. Kopelowitz, R. Krauthgamer, E. Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In Proc. 41st ICALP, pages 532-543, 2014. Google Scholar
  35. Łukasz Kowalik. Fast 3-coloring triangle-free planar graphs. In European Symposium on Algorithms, pages 436-447. Springer, 2004. Google Scholar
  36. Łukasz Kowalik. Adjacency queries in dynamic sparse graphs. Information Processing Letters, 102(5):191-195, 2007. Google Scholar
  37. Lukasz Kowalik and Maciej Kurowski. Oracles for bounded-length shortest paths in planar graphs. ACM Transactions on Algorithms (TALG), 2(3):335-363, 2006. Google Scholar
  38. Christos Levcopoulos and Mark H. Overmars. A balanced search tree with O worst-case update time. Acta Inf., 26(3):269-277, 1988. Google Scholar
  39. Min Chih Lin, Francisco J Soulignac, and Jayme L Szwarcfiter. Arboricity, h-index, and dynamic algorithms. Theoretical Computer Science, 426:75-90, 2012. Google Scholar
  40. Nathan Linial. Distributive graph algorithms-global solutions from local data. In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 331-335, 1987. Google Scholar
  41. Nathan Linial. Locality in distributed graph algorithms. SIAM J. Comput., 21(1):193-201, 1992. Google Scholar
  42. Michael Luby. Removing randomness in parallel computation without a processor penalty. J. Comput. Syst. Sci., 47(2):250-286, 1993. Google Scholar
  43. Cara Monical and Forrest Stonedahl. Static vs. dynamic populations in genetic algorithms for coloring a dynamic graph. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, pages 469-476. ACM, 2014. Google Scholar
  44. Christian Worm Mortensen. Fully dynamic orthogonal range reporting on ram. SIAM Journal on Computing, 35(6):1494-1525, 2006. Google Scholar
  45. C St JA Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 1(1):12-12, 1964. Google Scholar
  46. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2013, Palo Alto, CA, USA, June 1-4, 2013, pages 745-754, 2013. Google Scholar
  47. K. Onak, B. Schieber, S. Solomon, and N. Wein. Fully dynamic mis in uniformly sparse graphs. In Proc. 45th ICALP, 2018. Google Scholar
  48. Linda Ouerfelli and Hend Bouziri. Greedy algorithms for dynamic graph coloring. In Communications, Computing and Control Applications (CCCA), 2011 International Conference on, pages 1-5. IEEE, 2011. Google Scholar
  49. Merav Parter, David Peleg, and Shay Solomon. Local-on-average distributed tasks. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 220-239, 2016. Google Scholar
  50. David Peleg and Shay Solomon. Dynamic (1 + ε)-approximate matchings: A density-sensitive approach. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016. Google Scholar
  51. Davy Preuveneers and Yolande Berbers. Acodygra: an agent algorithm for coloring dynamic graphs. Symbolic and Numeric Algorithms for Scientific Computing (September 2004), 6:381-390, 2004. Google Scholar
  52. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Proc. of 1st ITCS, pages 223-238, 2011. Google Scholar
  53. Scott Sallinen, Keita Iwabuchi, Suraj Poudel, Maya Gokhale, Matei Ripeanu, and Roger Pearce. Graph colouring as a challenge problem for dynamic graph processing on distributed systems. In High Performance Computing, Networking, Storage and Analysis, SC16: International Conference for, pages 347-358. IEEE, 2016. Google Scholar
  54. Stephen B Seidman. Network structure and minimum degree. Social networks, 5(3):269-287, 1983. Google Scholar
  55. Shay Solomon. Fully dynamic maximal matching in constant update time. In Proceedings of the 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, NJ, USA, October 9-11, 2016, pages 325-334, 2016. Google Scholar
  56. Shay Solomon. Local algorithms for bounded degree sparsifiers in sparse graphs. In LIPIcs-Leibniz International Proceedings in Informatics, volume 94. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  57. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Proceedings of the 37th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2005, Baltimore, MD, USA, May 21-24, 2005, pages 112-119, 2005. Google Scholar
  58. 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, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1130-1143, 2017. Google Scholar
  59. Long Yuan, Lu Qin, Xuemin Lin, Lijun Chang, and Wenjie Zhang. Effective and efficient dynamic graph coloring. Proceedings of the VLDB Endowment, 11(3):338-351, 2017. Google Scholar
  60. David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(1):103-128, 2007. 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 Imprint Privacy Contact