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^*

^*Tämän työn vastaava kirjoittaja

Swiss Federal Institute of Technology
Graz University of Technology

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

2 Sitaatiot (Scopus)

28 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	37th International Symposium on Distributed Computing, DISC 2023
Toimittajat	Rotem Oshman
Kustantaja	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)	978-3-95977-301-0
DOI - pysyväislinkit	https://doi.org/10.4230/LIPIcs.DISC.2023.23
Tila	Julkaistu - lokak. 2023
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	International Symposium on Distributed Computing - L'Aquila, Italia Kesto: 10 lokak. 2023 → 12 lokak. 2023 Konferenssinumero: 37

Julkaisusarja

Nimi	Leibniz International Proceedings in Informatics, LIPIcs
Vuosikerta	281
ISSN (painettu)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Lyhennettä	DISC
Maa/Alue	Italia
Kaupunki	L'Aquila
Ajanjakso	10/10/2023 → 12/10/2023

Rahoitus

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.

Pääsy asiakirjaan

10.4230/LIPIcs.DISC.2023.23Lisenssi: CC BY

SCI_Grunau_etal_DISC_2023Final published version, 495 KBLisenssi: CC BY

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

1 Päättynyt

Massively Parallel Algorithms for Large-Scale Graph Problems
Uitto, J. (Vastuullinen johtaja), Latypov, R. (Projektin jäsen), Pai, S. (Projektin jäsen), Zhu, X. (Projektin jäsen), Miikonen, H. (Projektin jäsen) & Cambus, M. (Projektin jäsen)
01/09/2020 → 31/08/2024
Projekti: RCF Academy Project

Siteeraa tätä

Grunau, C., Latypov, R., Maus, Y., Pai, S., & Uitto, J. (2023). Conditionally Optimal Parallel Coloring of Forests. teoksessa R. Oshman (Toimittaja), 37th International Symposium on Distributed Computing, DISC 2023 Artikkeli 23 (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 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. julkaisussa R Oshman (Toimittaja), 37th International Symposium on Distributed Computing, DISC 2023., 23, Leibniz International Proceedings in Informatics, LIPIcs, Vuosikerta 281, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, L'Aquila, Italia, 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. toim. / Rotem Oshman. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 23 (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 281).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

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

Abstrakti

Julkaisusarja

Conference

Rahoitus

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Projektit

Massively Parallel Algorithms for Large-Scale Graph Problems

Siteeraa tätä