Document Open Access Logo

Fast Distributed Vertex Splitting with Applications

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

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.26.pdf
  • Filesize: 1.03 MB
  • 24 pages

Document Identifiers

Author Details

Magnús M. Halldórsson
  • Reykjavik University, Iceland
Yannic Maus
  • TU Graz, Austria
Alexandre Nolin
  • Reykjavik University, Iceland
  • CISPA, Saarbrücken, Germany

Cite As Get BibTex

Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast Distributed Vertex Splitting with Applications. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 26:1-26:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DISC.2022.26

Abstract

We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma. 
As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1+ε)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Graph problems
  • Edge coloring
  • List coloring
  • Lovász local lemma
  • LOCAL model
  • CONGEST model
  • Distributed computing

Metrics

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

Related Versions

References

  1. Noga Alon. A parallel algorithmic version of the local lemma. Random Structures & Algorithms, 2(4):367-378, 1991. Google Scholar
  2. Philipp Bamberger, Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto. On the complexity of distributed splitting problems. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2019. URL: https://doi.org/10.1145/3293611.3331630.
  3. Leonid Barenboim and Michael Elkin. Distributed (Δ+ 1)-coloring in linear (in Δ) time. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 111-120, 2009. Google Scholar
  4. Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. Journal of the ACM, 63(3):20:1-20:45, 2016. Google Scholar
  5. József Beck. An algorithmic approach to the Lovász local lemma. I. Random Structures & Algorithms, 2(4):343-365, 1991. Google Scholar
  6. Anton Bernshteyn. A fast distributed algorithm for Δ+ 1-edge-coloring. Journal of Combinatorial Theory, Series B, 152:319-352, 2022. Google Scholar
  7. Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, and Jara Uitto. A lower bound for the distributed Lovász local lemma. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 479-488, 2016. Google Scholar
  8. Sebastian Brandt, Christoph Grunau, and Václav Rozhon. Generalizing the sharp threshold phenomenon for the distributed complexity of the Lovász local lemma. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 329-338. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405730.
  9. Sebastian Brandt, Yannic Maus, and Jara Uitto. A sharp threshold phenomenon for the distributed complexity of the Lovász local lemma. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 389-398. ACM, 2019. URL: https://doi.org/10.1145/3293611.3331636.
  10. Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive Lovász local lemma. ACM Transactions on Algorithms (TALG), 16(1):1-51, 2019. Google Scholar
  11. Yi-Jun Chang, Wenzheng Li, and Seth Pettie. Distributed (Δ+1)-coloring via ultrafast graph shattering. SIAM Journal on Computing, 49(3):497-539, 2020. Google Scholar
  12. Yi-Jun Chang and Seth Pettie. A time hierarchy theorem for the LOCAL model. SIAM Journal on Computing, 48(1):33-69, 2019. Google Scholar
  13. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su. Distributed algorithms for the Lovász local lemma and graph coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 134-143, 2014. URL: https://doi.org/10.1145/2611462.2611465.
  14. Devdatt P. Dubhashi, David A. Grable, and Alessandro Panconesi. Near-optimal, distributed edge colouring via the nibble method. Theor. Comput. Sci., 203(2):225-251, 1998. URL: https://doi.org/10.1016/S0304-3975(98)00022-X.
  15. Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2Δ-1)-edge-coloring is much easier than maximal matching in the distributed setting. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 355-370, 2015. URL: https://doi.org/10.1137/1.9781611973730.26.
  16. Paul Erdös and László Lovász. Problems and Results on 3-chromatic Hypergraphs and some Related Questions. Colloquia Mathematica Societatis János Bolyai, pages 609-627, 1974. Google Scholar
  17. Manuela Fischer. Improved deterministic distributed matching via rounding. In Proceedings of the International Symposium on Distributed Computing (DISC), volume 91 of LIPIcs, pages 17:1-17:15. LZI, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.17.
  18. Manuela Fischer and Mohsen Ghaffari. Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy. In Proceedings of the International Symposium on Distributed Computing (DISC), volume 91 of LIPIcs, pages 18:1-18:16. LZI, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.18.
  19. Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 180-191, 2017. Google Scholar
  20. Mohsen Ghaffari. An improved distributed algorithm for maximal independent set. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270-277, 2016. Google Scholar
  21. Mohsen Ghaffari. Distributed maximal independent set using small messages. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 805-820, 2019. Google Scholar
  22. Mohsen Ghaffari, Christoph Grunau, and Václav Rozhoň. Improved deterministic network decomposition. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021. URL: http://arxiv.org/abs/2007.08253.
  23. Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 662-673, 2018. Google Scholar
  24. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. Improved distributed delta-coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 427-436, 2018. Google Scholar
  25. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved distributed degree splitting and edge coloring. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 19:1-19:15, 2017. Google Scholar
  26. Mohsen Ghaffari and Fabian Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 1009-1020, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00101.
  27. Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 784-797, 2017. Google Scholar
  28. Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505-2523, 2017. Google Scholar
  29. Magnús M. Halldórsson and Alexandre Nolin. Superfast coloring in CONGEST via efficient color sampling. In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2021. Google Scholar
  30. Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Fast distributed vertex splitting with applications, 2022. URL: https://doi.org/10.48550/ARXIV.2208.08119.
  31. David G. Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 700-724, 2019. Google Scholar
  32. Penny E. Haxell. A note on vertex list colouring. Comb. Probab. Comput., 10(4):345-347, 2001. Google Scholar
  33. Ken-ichi Kawarabayashi and Gregory Schwartzman. Adapting local sequential algorithms to the distributed setting. In Proceedings of the International Symposium on Distributed Computing (DISC), volume 121 of LIPIcs, pages 35:1-35:17. LZI, 2018. Google Scholar
  34. Fabian Kuhn. Weak graph colorings: distributed algorithms and applications. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA), pages 138-144, 2009. Google Scholar
  35. Nathan Linial. Distributive graph algorithms - global solutions from local data. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 331-335, 1987. Google Scholar
  36. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, 1992. Google Scholar
  37. Yannic Maus. Distributed graph coloring made easy. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA), pages 362-372. ACM, 2021. URL: https://doi.org/10.1145/3409964.3461804.
  38. Yannic Maus and Tigran Tonoyan. Local conflict coloring revisited: Linial for lists. In Proceedings of the International Symposium on Distributed Computing (DISC), pages 16:1-16:18, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.16.
  39. Yannic Maus and Jara Uitto. Efficient CONGEST algorithms for the Lovász local lemma. In Proceedings of the International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, pages 31:1-31:19. LZI, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.31.
  40. Michael Molloy and Bruce Reed. Further algorithmic aspects of the local lemma. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 524-529, 1998. Google Scholar
  41. Robin A. Moser and Gábor Tardos. A Constructive Proof of the General Lovász Local Lemma. J. ACM, pages 11:1-11:15, 2010. Google Scholar
  42. Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM Journal on Computing, 26(2):350-368, 1997. URL: https://doi.org/10.1137/S0097539793250767.
  43. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google Scholar
  44. Bruce Reed. The list colouring constants. Journal of Graph Theory, 31(2):149-153, 1999. URL: https://doi.org/10.1002/(SICI)1097-0118(199906)31:2<149::AID-JGT8>3.0.CO;2-%23.
  45. Bruce Reed and Benny Sudakov. Asymptotically the list colouring constants are 1. Journal of Combinatorial Theory, Series B, 86(1):27-37, 2002. Google Scholar
  46. Václav Rozhoň 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
  47. Hsin-Hao Su and Hoa T. Vu. Towards the locality of Vizing’s theorem. In Proceedings of the ACM Symposium on Theory of Computing (STOC), pages 355-364, 2019. 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