Fast Distributed Vertex Splitting with Applications.

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

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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.

Original languageEnglish
Title of host publication36th International Symposium on Distributed Computing (DISC 2022)
EditorsChristian Scheideler
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)978-395977255-6
Publication statusPublished - 1 Oct 2022
Event36th International Symposium on Distributed Computing: DISC 2022 - Augusta, United States
Duration: 25 Oct 202227 Oct 2022

Publication series

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


Conference36th International Symposium on Distributed Computing
Country/TerritoryUnited States


  • CONGEST model
  • Distributed computing
  • Edge coloring
  • Graph problems
  • List coloring
  • LOCAL model
  • Lovász local lemma

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Fast Distributed Vertex Splitting with Applications.'. Together they form a unique fingerprint.

Cite this