Efficient randomized distributed coloring in CONGEST

DOI10.1145/3406325.3451089MaRDI QIDQ6065242zbMATH OpenOpenAlexWikidataFDO

Authors Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus, Tigran Tonoyan

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.14169

zbMATH Keywords

massively parallel computationCONGEST modeldeterministic vertex coloring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an $n$-node graph $G$, and where the nodes of $G$ operate in synchronous communication rounds in which they can exchange $O(logn)$-bit messages over all the edges of $G$. For graphs with maximum degree $Delta$, we show that the $(Delta+1)$-list coloring problem (and therefore also the standard $(Delta+1)$-coloring problem) can be solved in $O(lo{g}^{5}logn)$ rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous $(Delta+1)$-coloring algorithm in the CONGEST model had a running time of $O(logDelta+lo{g}^{6}logn)$ rounds. As a function of $n$ alone, the best previous algorithm therefore had a round complexity of $O(logn)$, which is a bound that can also be achieved by a na"{i}ve folklore algorithm. For large maximum degree $Delta$, our algorithm hence is an exponential improvement over the previous state of the art.

Cited in

(11)

• Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring
• Distributed algorithms for fractional coloring
• Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds
• scientific article; zbMATH DE number 7368393 (Why is no real title available?)
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Optimal Message-Passing with Noisy Beeps
• Improved dynamic colouring of sparse graphs
• Finding a small vertex cut on distributed networks
• The message complexity of distributed graph optimization
• Optimal message-passing with noisy beeps
• Hardness and algorithms for several new optimization problems on the weighted massively parallel computation model

This page was built for publication: Efficient randomized distributed coloring in CONGEST

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065242)