Document Open Access Logo

Coloring Fast Without Learning Your Neighbors' Colors

Authors Magnús M. Halldórsson , Fabian Kuhn , Yannic Maus , Alexandre Nolin

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.39.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Magnús M. Halldórsson
  • Reykjavik University, Iceland
Fabian Kuhn
  • University of Freiburg, Germany
Yannic Maus
  • Technion - Israel Institute of Technology, Haifa, Israel
Alexandre Nolin
  • Reykjavik University, Iceland

Funding

This project was supported by the European Union’s Horizon 2020 Research and Innovation Programme under grant agreement no. 755839 and by the Icelandic Research Fund grant 174484.

Cite As Get BibTex

Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. Coloring Fast Without Learning Your Neighbors' Colors. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.39

Abstract

We give an improved randomized CONGEST algorithm for distance-2 coloring that uses Δ²+1 colors and runs in O(log n) rounds, improving the recent O(log Δ ⋅ log n)-round algorithm in [Halldórsson, Kuhn, Maus; PODC '20]. We then improve the time complexity to O(log Δ) + 2^{O(√{log log n})}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • distributed graph coloring
  • distance 2 coloring
  • congestion

Metrics

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

Related Versions

References

  1. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Algorithms, 7(4):567-583, 1986. Google Scholar
  2. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for (Δ+1) vertex coloring. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 767-786, 2019. Google Scholar
  3. Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. Network decomposition and locality in distributed computation. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 364-369, 1989. Google Scholar
  4. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Efficient deterministic distributed coloring with small bandwidth. In Proc. 39th ACM Symp. on Principles of Distributed Computing (PODC), page 243–252, 2020. Google Scholar
  5. Reuven Bar-Yehuda, Keren Censor-Hillel, Yannic Maus, Shreyas Pai, and Sriram V. Pemmaraju. Distributed approximation on power graphs. In Proc. 39th ACM Symp. on Principles of Distributed Computing (PODC), page 501–510, 2020. Google Scholar
  6. Leonid Barenboim. Deterministic (Δ + 1)-coloring in sublinear (in Δ) time in static, dynamic and faulty networks. In Proc. 34th Symp. on Principles of Distributed Computing (PODC), pages 345-354, 2015. Google Scholar
  7. Leonid Barenboim and Michael Elkin. Deterministic distributed vertex coloring in polylogarithmic time. In Proc. 29th Symp. on Principles of Distributed Computing (PODC), 2010. Google Scholar
  8. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013. Google Scholar
  9. Leonid Barenboim, Michael Elkin, and Uri Goldenberg. Locally-iterative distributed (Δ+ 1)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC), pages 437-446, 2018. Google Scholar
  10. Leonid Barenboim, Michael Elkin, and Fabian Kuhn. Distributed (Δ+1)-coloring in linear (in Δ) time. SIAM J. on Computing, 43(1):72-95, 2015. Google Scholar
  11. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In Proc. 53th Symp. on Foundations of Computer Science (FOCS), 2012. Google Scholar
  12. József Beck. An algorithmic approach to the Lovaśz local lemma. Random Structures & Algorithms, 2:343-365, 1991. Google Scholar
  13. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. In Proc. 31st Symp. on Distributed Computing (DISC), pages 11:1-11:16, 2017. Google Scholar
  14. Yi Jun Chang, Wenzheng Li, and Seth Pettie. An optimal distributed (Δ+1)-coloring algorithm? In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 445-456, 2018. Google Scholar
  15. Imrich Chlamtac and Shay Kutten. A spatial-reuse TDMA/FDMA for mobile multi-hop radio networks. In Proc. 4th IEEE Int. Conf. on Computer Communications (INFOCOM), pages 389-394, 1985. Google Scholar
  16. Janosch Deurer, Fabian Kuhn, and Yannic Maus. Deterministic distributed dominating set approximation in the CONGEST model. In Proc. 38th ACM Symp. on Principles of Distributed Computing (PODC), pages 94-103, 2019. Google Scholar
  17. Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2Δ-1)-edge-coloring is much easier than maximal matching in the distributed setting. In Proc. of 26th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 355-370, 2015. Google Scholar
  18. Pierre Fraigniaud, Magnús M. Halldórsson, and Alexandre Nolin. Distributed testing of distance-k colorings. In Proc. 27th Coll. on Structural Information and Communication Complexity (SIROCCO), pages 275-290, 2020. Google Scholar
  19. Mohsen Ghaffari. Distributed maximal independent set using small messages. In Proc. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 805-820, 2019. Google Scholar
  20. Mohsen Ghaffari, Christoph Grunau, and Václav Rozhoň. Improved deterministic network decomposition, 2020. URL: http://arxiv.org/abs/2007.08253.
  21. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Proc. 59th Symp. on Foundations of Computer Science (FOCS), pages 662-673, 2018. Google Scholar
  22. Mohsen Ghaffari and Julian Portmann. Improved network decompositions using small messages with applications on MIS, neighborhood covers, and beyond. In Proc. 33rd Int. Symp. on Distributed Computing (DISC), pages 18:1-18:16, 2019. Google Scholar
  23. Magnús M. Halldórsson, Fabian Kuhn, and Yannic Maus. Distance-2 coloring in the CONGEST model. In Proc. 39th ACM Symp. on Principles of Distributed Computing (PODC), pages 233-242, 2020. Google Scholar
  24. Magnus M. Halldorsson, Fabian Kuhn, Yannic Maus, and Alexandre Nolin. Coloring fast without learning your neighbors' colors, 2020. URL: http://arxiv.org/abs/2008.04303.
  25. David G Harris, Johannes Schneider, and Hsin-Hao Su. Distributed (Δ+ 1)-coloring in sublogarithmic rounds. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 465-478, 2016. Google Scholar
  26. Ö. Johansson. Simple distributed Δ+1-coloring of graphs. Inf. Process. Lett., 70(5):229-232, 1999. Google Scholar
  27. Fabian Kuhn. Faster deterministic distributed coloring through recursive list coloring. In Proc. 31st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1244-1259, 2020. Google Scholar
  28. Fabian Kuhn and Roger Wattenhofer. On the complexity of distributed graph coloring. In Proc. 25th ACM Symp. on Principles of Distributed Computing (PODC), pages 7-15, 2006. Google Scholar
  29. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  30. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. on Computing, 15:1036-1053, 1986. Google Scholar
  31. Steffen Mecke. MAC layer and coloring. In D. Wagner and R. Wattenhofer, editors, Algorithms for Sensor and Ad Hoc Networks, pages 63-80, 2007. Google Scholar
  32. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  33. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 350-363, 2020. 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