Document Open Access Logo

Optimal (Degree+1)-Coloring in Congested Clique

Authors Sam Coy , Artur Czumaj , Peter Davies , Gopinath Mishra

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.46.pdf
  • Filesize: 0.98 MB
  • 20 pages

Document Identifiers

Author Details

Sam Coy
  • University of Warwick, Coventry, UK
Artur Czumaj
  • University of Warwick, Coventry, UK
Peter Davies
  • Durham University, UK
Gopinath Mishra
  • University of Warwick, Coventry, UK

Funding

  • Coy, Sam: Research supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP), by an EPSRC studentship, and by the Simons Foundation Award No. 663281 granted to the Institute of Mathematics of the Polish Academy of Sciences for the years 2021-2023.
  • Czumaj, Artur: Research supported in part by the Centre for Discrete Mathematics and its Applications, by EPSRC award EP/V01305X/1, by a Weizmann-UK Making Connections Grant, by an IBM Award, and by the Simons Foundation Award No. 663281 granted to the Institute of Mathematics of the Polish Academy of Sciences for the years 2021-2023.
  • Mishra, Gopinath: Research supported in part by the Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC award EP/V01305X/1, and by the Simons Foundation Award No. 663281 granted to the Institute of Mathematics of the Polish Academy of Sciences for the years 2021-2023.

Cite As Get BibTex

Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Optimal (Degree+1)-Coloring in Congested Clique. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.46

Abstract

We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node u of degree d(u) is assigned a palette of d(u)+1 colors, and the goal is to find a proper coloring using these color palettes. The (degree+1)-list coloring problem is a natural generalization of the classical (Δ+1)-coloring and (Δ+1)-list coloring problems, both being benchmark problems extensively studied in distributed and parallel computing.
In this paper we settle the complexity of the (degree+1)-list coloring problem in the Congested Clique model by showing that it can be solved deterministically in a constant number of rounds.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
  • Theory of computation → Distributed algorithms
  • Theory of computation → Pseudorandomness and derandomization
  • Mathematics of computing → Graph algorithms
Keywords
  • Distributed computing
  • graph coloring
  • parallel computing

Metrics

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

Related Versions

References

  1. Noga Alon and Sepehr Assadi. Palette sparsification beyond (Δ+1) vertex coloring. In Proceedings of the 24th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 6:1-6:22, 2020. Google Scholar
  2. Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567-583, 1986. Google Scholar
  3. Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Sublinear algorithms for (Δ + 1) vertex coloring. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 767-786, 2019. Google Scholar
  4. Étienne Bamas and Louis Esperet. Distributed coloring of graphs with an optimal number of colors. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 10:1-10:15, 2019. Google Scholar
  5. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Efficient deterministic distributed coloring with small bandwidth. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), pages 243-252, 2020. Google Scholar
  6. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013. Google Scholar
  7. Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Brief announcement: Semi-MapReduce meets Congested Clique. Preprint arXiv, 2018. URL: https://arxiv.org/abs/1802.10297.
  8. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. Distributed Computing, 33(3):349-366, 2020. Google Scholar
  9. Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari, Jara Uitto, and Yufan Zheng. The complexity of (Δ + 1) coloring in Congested Clique, Massively Parallel Computation, and centralized local computation. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 471-480, 2019. Google Scholar
  10. 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
  11. Sam Coy, Artur Czumaj, Peter Davies, and Gopinath Mishra. Fast parallel degree+1 list coloring. Preprint arXiv, 2023. URL: https://arxiv.org/abs/2302.04378.
  12. Artur Czumaj, Peter Davies, and Merav Parter. Component stability in low-space massively parallel computation. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC), pages 481-491, 2021. Google Scholar
  13. Artur Czumaj, Peter Davies, and Merav Parter. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms, 17(2), May 2021. Google Scholar
  14. Artur Czumaj, Peter Davies, and Merav Parter. Improved deterministic (Δ+1) coloring in low-space MPC. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC), pages 469-479, 2021. Google Scholar
  15. Artur Czumaj, Peter Davies, and Merav Parter. Simple, deterministic, constant-round coloring in Congested Clique and MPC. SIAM Journal on Computing, 50(5):1603-1626, 2021. Google Scholar
  16. Janosch Deurer, Fabian Kuhn, and Yannic Maus. Deterministic distributed dominating set approximation in the CONGEST model. In Proceedings of the 38th ACM Symposium on Principles of Distributed Computing (PODC), pages 94-103, 2019. Google Scholar
  17. Paul Erdös and John L. Selfridge. On a combinatorial game. Journal of Combinatorial Theory, Series A, 14(3):298-301, 1973. Google Scholar
  18. Manuela Fischer, Jeff Giliberti, and Christoph Grunau. Improved deterministic connectivity in massively parallel computation. In Proceedings of the 36th International Symposium on Distributed Computing (DISC), pages 22:1-22:17, 2022. Google Scholar
  19. Manuela Fischer, Magnús M. Halldórsson, and Yannic Maus. Fast distributed Brooks' theorem. In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2567-2588, 2023. Google Scholar
  20. Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. Local conflict coloring. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pages 625-634, 2016. Google Scholar
  21. Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 29:1-29:17, 2018. Google Scholar
  22. Mohsen Ghaffari and Fabian Kuhn. Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition. In Proceedings of the 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 1009-1020, 2021. Google Scholar
  23. Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. Efficient randomized distributed coloring in CONGEST. In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pages 1180-1193, 2021. Google Scholar
  24. Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. Near-optimal distributed degree+1 coloring. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 450-463, 2022. Google Scholar
  25. Magnús M. Halldórsson, Alexandre Nolin, and Tigran Tonoyan. Overcoming congestion in distributed coloring. In Proceedings of the 41st ACM Symposium on Principles of Distributed Computing (PODC), pages 26-36, 2022. Google Scholar
  26. James W. Hegeman and Sriram V. Pemmaraju. Lessons from the Congested Clique applied to MapReduce. Theoretical Computer Science, 608:268-281, 2015. Google Scholar
  27. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for MapReduce. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 938-948, 2010. Google Scholar
  28. Fabian Kuhn. Faster deterministic distributed coloring through recursive list coloring. In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1244-1259, 2020. Google Scholar
  29. Christoph Lenzen. Optimal deterministic routing and sorting on the Congested Clique. In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC), pages 42-50, 2013. Google Scholar
  30. Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193-201, February 1992. Google Scholar
  31. Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg. Minimum-weight spanning tree construction in O(log log n) communication rounds. SIAM Journal on Computing, 35(1):120-131, 2005. Google Scholar
  32. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036-1053, 1986. Google Scholar
  33. Michael Luby. Removing randomness in parallel computation without a processor penalty. Journal of Computer and System Sciences, 47(2):250-286, 1993. Google Scholar
  34. Rajeev Motwani, Joseph Naor, and Moni Naor. The probabilistic method yields deterministic parallel algorithms. Journal of Computer and System Sciences, 49(3):478-516, 1994. Google Scholar
  35. Moni Naor. A lower bound on probabilistic algorithms for distributive ring coloring. SIAM Journal on Discrete Mathematics, 4(3):409-412, 1991. Google Scholar
  36. Merav Parter. (Δ+1) coloring in the Congested Clique model. In Proceedings of the 45th Annual International Colloquium on Automata, Languages and Programming (ICALP), pages 160:1-160:14, 2018. Google Scholar
  37. Merav Parter and Hsin-Hao Su. Randomized (Δ+1)-coloring in O(log^*Δ) Congested Clique rounds. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC), pages 39:1-39:18, 2018. Google Scholar
  38. David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 2000. Google Scholar
  39. Prabhakar Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37(2):130-143, 1988. Google Scholar
  40. Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual 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