Document Open Access Logo

Simple and Near-Optimal Distributed Coloring for Sparse Graphs

Authors Mohsen Ghaffari, Christiana Lymouri

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.20.pdf
  • Filesize: 491 kB
  • 14 pages

Document Identifiers

Author Details

Mohsen Ghaffari
Christiana Lymouri

Cite As Get BibTex

Mohsen Ghaffari and Christiana Lymouri. Simple and Near-Optimal Distributed Coloring for Sparse Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.20

Abstract

Graph coloring is one of the central problems in distributed graph algorithms. Much of the research on this topic has focused on coloring with Delta+1 colors, where Delta denotes the maximum degree. Using Delta+1 colors may be unsatisfactory in sparse graphs, where not all nodes have such a high degree; it would be more desirable to use a number of colors that improves with sparsity. A standard measure that captures sparsity is arboricity, which is the smallest number of forests into which the edges of the graph can be partitioned.

We present simple randomized distributed algorithms that, with high probability, color any n-node alpha-arboricity graph:

- using (2+epsilon)alpha colors, for constant epsilon>0, in O(log n) rounds, if alpha=Omega(log n log log n), or

- using O(alpha log alpha) colors, in O(log n) rounds, or

- using O(alpha) colors, in O(log n min{log log n, log alpha}) rounds.

These algorithms are nearly-optimal, as it is known by results of Linial [FOCS'87] and Barenboim and Elkin [PODC'08] that coloring with Theta(alpha) colors, or even poly(alpha) colors, requires Omega(log_alpha n) rounds. The previously best-known O(log n)-time result was a deterministic algorithm due to Barenboim and Elkin [PODC'08], which uses Theta(alpha^2) colors. Barenboim and Elkin stated improving this number of colors as an open problem in their Distributed Graph Coloring Book.

Subject Classification

Keywords
  • Distributed Graph Algorithms
  • Graph Coloring
  • Arboricity

Metrics

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

References

  1. Baruch Awerbuch, M Luby, AV Goldberg, and Serge A Plotkin. Network decomposition and locality in distributed computation. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 364-369, 1989. Google Scholar
  2. Leonid Barenboim. Deterministic (Δ+ 1)-coloring in sublinear (in Δ) time in static, dynamic, and faulty networks. Journal of the ACM (JACM), page 47, 2016. Google Scholar
  3. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed mis algorithm for sparse graphs using nash-williams decomposition. In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC'08, pages 25-34, 2008. Google Scholar
  4. Leonid Barenboim and Michael Elkin. Distributed (Δ+ 1)-coloring in linear (in Δ) time. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 111-120, 2009. Google Scholar
  5. 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
  6. Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. Journal of the ACM (JACM), page 23, 2011. 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, Michael Elkin, and Fabian Kuhn. Distributed (Δ+1)-coloring in linear (in Δ) time. SIAM Journal on Computing, 43(1):72-95, 2014. Google Scholar
  9. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In Foundations of Computer Science (FOCS) 2012, pages 321-330, 2012. Google Scholar
  10. Béla Bollobás. Chromatic number, girth and maximal degree. Discrete Mathematics, 24(3):311-314, 1978. Google Scholar
  11. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the lovász local lemma and graph coloring. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 134-143, 2014. Google Scholar
  12. Richard Cole and Uzi Vishkin. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 206-219. ACM, 1986. Google Scholar
  13. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 625-634. IEEE, 2016. Google Scholar
  14. David G Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+ 1)-coloring in sublogarithmic rounds. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 465-478, 2016. Google Scholar
  15. Öjvind Johansson. Simple distributed Δ+ 1-coloring of graphs. Information Processing Letters, 70(5):229-232, 1999. Google Scholar
  16. Kishore Kothapalli and Sriram Pemmaraju. Distributed graph coloring in a few rounds. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC'11, pages 31-40, 2011. Google Scholar
  17. Fabian Kuhn. Weak graph colorings: Distributed algorithms and applications. In Proceedings of the Twenty-first Annual Symposium on Parallelism in Algorithms and Architectures, pages 138-144, 2009. Google Scholar
  18. Nathan Linial. Distributive graph algorithms global solutions from local data. In Proc. of the Symp. on Found. of Comp. Sci. (FOCS), pages 331-335. IEEE, 1987. Google Scholar
  19. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  20. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036-1053, 1986. Google Scholar
  21. CSJA Nash-Williams. Decomposition of finite graphs into forests. Journal of the London Mathematical Society, 1(1):12-12, 1964. Google Scholar
  22. Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed computing, 14(2):97-100, 2001. Google Scholar
  23. Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of the Symp. on Theory of Comp. (STOC), pages 581-592. ACM, 1992. Google Scholar
  24. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  25. Seth Pettie and Hsin-Hao Su. Distributed coloring algorithms for triangle-free graphs. Information and Computation, 243:263-280, 2015. Google Scholar
  26. Johannes Schneider and Roger Wattenhofer. A new technique for distributed symmetry breaking. In Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 257-266, 2010. Google Scholar
  27. Johannes Schneider and Roger Wattenhofer. Distributed coloring depending on the chromatic number or the neighborhood growth. In International Colloquium on Structural Information and Communication Complexity, pages 246-257. Springer, 2011. Google Scholar
  28. Márió Szegedy and Sundar Vishwanathan. Locality based graph coloring. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pages 201-207, 1993. 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