Fast Distributed Brooks' Theorem

Manuela Fischer, Magnús M. Halldórsson, Yannic Maus

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

Abstract

We give a randomized ∆-coloring algorithm in the LOCAL model that runs in poly log log n rounds, where n is the number of nodes of the input graph and ∆ is its maximum degree. This means that randomized ∆-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, poly log log n, given the known Ω(log log n) lower bound [Brandt et al., STOC'16]. Our main technical contribution is a constant time reduction to a constant number of (deg + 1)-list coloring instances, for ∆ = ω(log4 n), resulting in a poly log log n-round CONGEST algorithm for such graphs. This reduction is of independent interest for other settings, including providing a new proof of Brooks' theorem for high degree graphs, and leading to a constant-round Congested Clique algorithm in such graphs. When ∆ = Ω(log22 n), our algorithm even runs in O(log n) rounds, showing that the base in the Ω(log log n) lower bound is unavoidable. Previously, the best LOCAL algorithm for all considered settings used a logarithmic number of rounds. Our result is the first CONGEST algorithm for ∆-coloring non-constant degree graphs.

Original languageEnglish
Title of host publication34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
PublisherAssociation for Computing Machinery, Inc
Pages2567-2588
Number of pages22
ISBN (Electronic)9781611977554
DOIs
Publication statusPublished - 2023
Event34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy
Duration: 22 Jan 202325 Jan 2023

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2023-January

Conference

Conference34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Country/TerritoryItaly
CityFlorence
Period22/01/2325/01/23

Bibliographical note

Publisher Copyright:
Copyright © 2023.

Fingerprint

Dive into the research topics of 'Fast Distributed Brooks' Theorem'. Together they form a unique fingerprint.

Cite this