Fast Distributed Vertex Splitting with Applications.

Magnús M. Halldórsson, Yannic Maus, Alexandre Nolin

Publikation: Beitrag in Buch/Bericht/KonferenzbandBeitrag in einem KonferenzbandBegutachtung


We present poly log log n-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈ d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general poly log log n-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized poly log log n-round CONGEST algorithm for (1 + ε)∆-edge coloring n-node graphs of sufficiently large constant maximum degree ∆, for any ε > 0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

Titel36th International Symposium on Distributed Computing (DISC 2022)
Redakteure/-innenChristian Scheideler
Herausgeber (Verlag)Schloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektronisch)978-395977255-6
PublikationsstatusVeröffentlicht - 1 Okt. 2022
Veranstaltung36th International Symposium on Distributed Computing: DISC 2022 - Augusta, USA / Vereinigte Staaten
Dauer: 25 Okt. 202227 Okt. 2022


NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Konferenz36th International Symposium on Distributed Computing
Land/GebietUSA / Vereinigte Staaten

ASJC Scopus subject areas

  • Software

Dieses zitieren