TY - GEN
T1 - Conditionally Optimal Parallel Coloring of Forests
AU - Grunau, Christoph
AU - Latypov, Rustam
AU - Maus, Yannic
AU - Pai, Shreyas
AU - Uitto, Jara
N1 - Publisher Copyright:
© Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/10
Y1 - 2023/10
N2 - 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.
AB - 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.
KW - coloring
KW - forests
KW - massively parallel computation
KW - optimal
UR - http://www.scopus.com/inward/record.url?scp=85175338416&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2023.23
DO - 10.4230/LIPIcs.DISC.2023.23
M3 - Conference paper
AN - SCOPUS:85175338416
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Distributed Computing, DISC 2023
A2 - Oshman, Rotem
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 37th International Symposium on Distributed Computing
Y2 - 10 October 2023 through 12 October 2023
ER -