Conditionally Optimal Parallel Coloring of Forests

Christoph Grunau; Rustam Latypov; Yannic Maus; Shreyas Pai; Jara Uitto

doi:10.4230/LIPIcs.DISC.2023.23

Conditionally Optimal Parallel Coloring of Forests

Christoph Grunau^*
, Rustam Latypov^*
, Yannic Maus^*
, Shreyas Pai^*
, Jara Uitto^*

^*Corresponding author for this work

Swiss Federal Institute of Technology Zurich
Graz University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

2 Citations (Scopus)

28 Downloads (Pure)

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.

Original language	English
Title of host publication	37th International Symposium on Distributed Computing, DISC 2023
Editors	Rotem Oshman
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)	978-3-95977-301-0
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2023.23
Publication status	Published - Oct 2023
MoE publication type	A4 Conference publication
Event	International Symposium on Distributed Computing - L'Aquila, Italy Duration: 10 Oct 2023 → 12 Oct 2023 Conference number: 37

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	281
ISSN (Print)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	Italy
City	L'Aquila
Period	10/10/2023 → 12/10/2023

Funding

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

Keywords

coloring
forests
massively parallel computation
optimal

Access to Document

10.4230/LIPIcs.DISC.2023.23Licence: CC BY

SCI_Grunau_etal_DISC_2023Final published version, 495 KBLicence: CC BY

Cite this

Grunau, C., Latypov, R., Maus, Y., Pai, S., & Uitto, J. (2023). Conditionally Optimal Parallel Coloring of Forests. In R. Oshman (Ed.), 37th International Symposium on Distributed Computing, DISC 2023 Article 23 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 281). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2023.23

@inproceedings{1fa1999a717746b79edcaba2a8cb1f39,

title = "Conditionally Optimal Parallel Coloring of Forests",

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.",

keywords = "coloring, forests, massively parallel computation, optimal",

author = "Christoph Grunau and Rustam Latypov and Yannic Maus and Shreyas Pai and Jara Uitto",

note = "Funding Information: Academy of Finland, Grant 334238. Austrian Science Fund (FWF), Grant P36280-N. Funding Information: Funding Rustam Latypov: Academy of Finland, Grant 334238. Yannic Maus: Austrian Science Fund (FWF), Grant P36280-N. Shreyas Pai: Academy of Finland, Grant 334238. Publisher Copyright: {\textcopyright} Christoph Grunau, Rustam Latypov, Yannic Maus, Shreyas Pai, and Jara Uitto; licensed under Creative Commons License CC-BY 4.0.; International Symposium on Distributed Computing, DISC ; Conference date: 10-10-2023 Through 12-10-2023",

year = "2023",

month = oct,

doi = "10.4230/LIPIcs.DISC.2023.23",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Rotem Oshman",

booktitle = "37th International Symposium on Distributed Computing, DISC 2023",

address = "Germany",

}

Grunau, C, Latypov, R, Maus, Y, Pai, S & Uitto, J 2023, Conditionally Optimal Parallel Coloring of Forests. in R Oshman (ed.), 37th International Symposium on Distributed Computing, DISC 2023., 23, Leibniz International Proceedings in Informatics, LIPIcs, vol. 281, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, L'Aquila, Italy, 10/10/2023. https://doi.org/10.4230/LIPIcs.DISC.2023.23

Conditionally Optimal Parallel Coloring of Forests. / Grunau, Christoph; Latypov, Rustam; Maus, Yannic et al.
37th International Symposium on Distributed Computing, DISC 2023. ed. / Rotem Oshman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 23 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 281).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

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 - Conference code: 37

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 - https://www.scopus.com/pages/publications/85175338416

U2 - 10.4230/LIPIcs.DISC.2023.23

DO - 10.4230/LIPIcs.DISC.2023.23

M3 - Conference article in proceedings

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 - International Symposium on Distributed Computing

Y2 - 10 October 2023 through 12 October 2023

ER -

Conditionally Optimal Parallel Coloring of Forests

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Massively Parallel Algorithms for Large-Scale Graph Problems

Cite this

Conditionally Optimal Parallel Coloring of Forests

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Massively Parallel Algorithms for Large-Scale Graph Problems

Cite this