Document Open Access Logo

Conditionally Optimal Parallel Coloring of Forests

Authors Christoph Grunau , Rustam Latypov , Yannic Maus , Shreyas Pai , Jara Uitto

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.23.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Christoph Grunau
  • ETH Zürich, Switzerland
Rustam Latypov
  • Aalto University, Finland
Yannic Maus
  • TU Graz, Austria
Shreyas Pai
  • Aalto University, Finland
Jara Uitto
  • Aalto University, Finland

Funding

  • Latypov, Rustam: Academy of Finland, Grant 334238.
  • Maus, Yannic: Austrian Science Fund (FWF), Grant P36280-N.
  • Pai, Shreyas: Academy of Finland, Grant 334238.

Cite As Get BibTex

Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto. Conditionally Optimal Parallel Coloring of Forests. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.23

Abstract

We show the first conditionally optimal deterministic algorithm for 3-coloring forests in the low-space massively parallel computation (MPC) model. Our algorithm runs in O(log log n) rounds and uses optimal global space. The best previous algorithm requires 4 colors [Ghaffari, Grunau, Jin, DISC'20] and is randomized, while our algorithm are inherently deterministic.
Our main technical contribution is an O(log log n)-round algorithm to compute a partition of the forest into O(log n) ordered layers such that every node has at most two neighbors in the same or higher layers. Similar decompositions are often used in the area and we believe that this result is of independent interest. Our results also immediately yield conditionally optimal deterministic algorithms for maximal independent set and maximal matching for forests, matching the state of the art [Giliberti, Fischer, Grunau, SPAA'23]. In contrast to their solution, our algorithms are not based on derandomization, and are arguably simpler.

Subject Classification

ACM Subject Classification
  • Theory of computation → Massively parallel algorithms
Keywords
  • massively parallel computation
  • coloring
  • forests
  • optimal

Metrics

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

Related Versions

References

  1. Noga Alon, Lásló 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. URL: https://doi.org/10.1016/0196-6774(86)90019-2.
  2. Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally Checkable Labelings with Small Messages. In the Proceedings of the International Symposium on Distributed Computing (DISC), pages 8:1-8:18, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.8.
  3. Alkida Balliu, Rustam Latypov, Yannic Maus, Dennis Olivetti, and Jara Uitto. Optimal Deterministic Massively Parallel Connectivity on Forests. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2589-2631, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch99.
  4. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Efficient Deterministic Distributed Coloring with Small Bandwidth. In PODC '20: ACM Symposium on Principles of Distributed Computing (PODC), pages 243-252, 2020. URL: https://doi.org/10.1145/3382734.3404504.
  5. Leonid Barenboim and Michael Elkin. Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition. Distributed Comput., 22(5-6):363-379, 2010. URL: https://doi.org/10.1007/s00446-009-0088-2.
  6. 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
  7. Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 481-490, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331609.
  8. Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, and Vahab Mirrokni. Near-Optimal Massively Parallel Graph Connectivity. In FOCS, 2019. URL: https://doi.org/10.1109/FOCS.2019.00095.
  9. Sebastian Brandt, Manuela Fischer, and Jara Uitto. Breaking the Linear-memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory. Theoretical Computer Science, 849:22-34, 2021. URL: https://doi.org/10.1016/j.tcs.2020.10.007.
  10. Yi-Jun Chang. The Complexity Landscape of Distributed Locally Checkable Problems on Trees. In DISC, pages 18:1-18:17, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.18.
  11. 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 PODC, 2019. URL: https://doi.org/10.1145/3293611.3331607.
  12. Yi-Jun Chang and Seth Pettie. A Time Hierarchy Theorem for the LOCAL Model. SIAM J. Comput., 48(1):33-69, 2019. URL: https://doi.org/10.1137/17M1157957.
  13. Sam Coy and Artur Czumaj. Deterministic Massively Parallel Connectivity. In Proceedings of the ACM Symposium on Theory of Computing (STOC), 2022. URL: https://doi.org/10.1145/3519935.3520055.
  14. Artur Czumaj, Peter Davies, and Merav Parter. Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space. In the Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 175-185, 2020. URL: https://doi.org/10.1145/3350755.3400282.
  15. Artur Czumaj, Peter Davies, and Merav Parter. Component Stability in Low-Space Massively Parallel Computation. In PODC, 2021. URL: https://doi.org/10.1145/3465084.3467903.
  16. Artur Czumaj, Peter Davies, and Merav Parter. Improved Deterministic (Δ+1)-Coloring in Low-Space MPC. In PODC, pages 469-479, 2021. URL: https://doi.org/10.1145/3465084.3467937.
  17. 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. URL: https://doi.org/10.1137/20M1366502.
  18. Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM, pages 107-113, 2008. URL: https://doi.org/10.1145/1327452.1327492.
  19. Mohsen Ghaffari. An Improved Distributed Algorithm for Maximal Independent Set. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 270-277, 2016. Google Scholar
  20. Mohsen Ghaffari, Themis Gouleakis, Christian Konrad, Slobodan Mitrovic, and Ronitt Rubinfeld. Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover. In PODC, pages 129-138, 2018. URL: https://doi.org/10.1145/3212734.3212743.
  21. Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2532-2566, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch97.
  22. Mohsen Ghaffari, Christoph Grunau, and Ce Jin. Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond. In DISC, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.34.
  23. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. In FOCS, pages 1650-1663, 2019. URL: https://doi.org/10.1109/FOCS.2019.00097.
  24. Mohsen Ghaffari and Ali Sayyadi. Distributed Arboricity-Dependent Graph Coloring via All-to-All Communication. In ICALP, pages 142:1-142:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.142.
  25. Mohsen Ghaffari and Jara Uitto. Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation. In SODA, 2019. URL: https://doi.org/10.1137/1.9781611975482.99.
  26. Jeff Giliberti, Manuela Fischer, and Christoph Grunau. Deterministic massively parallel symmetry breaking for sparse graphs. CoRR, abs/2301.11205, 2023. URL: https://doi.org/10.48550/arXiv.2301.11205.
  27. Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, and Osamu Watanabe, editors, Algorithms and Computation, pages 374-383, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  28. Chetan Gupta, Rustam Latypov, Yannic Maus, Shreyas Pai, Simo Särkkä, Jan Studený, Jukka Suomela, Jara Uitto, and Hossein Vahidi. Fast dynamic programming in trees in the mpc model, 2023. URL: https://arxiv.org/abs/2305.03693.
  29. Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks. ACM SIGOPS Operating Systems Review, pages 59-72, 2007. URL: https://doi.org/10.1145/1272996.1273005.
  30. Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce. In SODA, 2010. URL: https://doi.org/10.1137/1.9781611973075.76.
  31. Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii. Filtering: A Method for Solving Graph Problems in MapReduce. In SPAA, pages 85-94, 2011. URL: https://doi.org/10.1145/1989493.1989505.
  32. Rustam Latypov and Jara Uitto. Deterministic 3-coloring of trees in the sublinear MPC model. CoRR, abs/2105.13980, 2021. URL: https://arxiv.org/abs/2105.13980.
  33. Christoph Lenzen and Roger Wattenhofer. Brief Announcement: Exponential Speed-Up of Local Algorithms Using Non-Local Communication. In PODC, 2010. URL: https://doi.org/10.1145/1835698.1835772.
  34. Nathan Linial. Distributive Graph Algorithms - Global Solutions from Local Data. In FOCS, 1987. URL: https://doi.org/10.1109/SFCS.1987.20.
  35. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput., 21(1):193-201, 1992. URL: https://doi.org/10.1137/0221015.
  36. Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15:1036-1053, 1986. URL: https://doi.org/10.1137/0215074.
  37. Crispin Nash-Williams. Decomposition of Finite Graphs Into Forests. Journal of the London Mathematical Society, s1-39:12, 1964. URL: https://doi.org/10.1112/jlms/s1-39.1.12.
  38. Öjvind Johansson. Simple Distributed Δ + 1-coloring of Graphs. Information Processing Letters, pages 229-232, 1999. URL: https://doi.org/10.1016/S0020-0190(99)00064-2.
  39. Merav Parter. (δ+1) coloring in the congested clique model. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, International Colloquium on Automata, Languages, and Programming, (ICALP), volume 107, pages 160:1-160:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.160.
  40. Merav Parter and Hsin-Hao Su. Randomized (δ+1)-coloring in o(log^* δ) congested clique rounds. In 32nd International Symposium on Distributed Computing (DISC), volume 121, pages 39:1-39:18, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.39.
  41. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation). Journal of the ACM, 2018. URL: https://doi.org/10.1145/3232536.
  42. Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In STOC, pages 350-363, 2020. URL: https://doi.org/10.1145/3357713.3384298.
  43. Tom White. Hadoop: The Definitive Guide. O'Reilly Media, Inc., 2009. Google Scholar
  44. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster Computing with Working Sets. In the Proceedings of the SENIX Conference on Hot Topics in Cloud Computing (HotCloud), 2010. URL: https://doi.org/10.5555/1863103.1863113.
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