2022/11/14 by Manuela Fischer, Fischer, Manuela, Yannic Maus +3 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2211.07606
openalex publication_date 2022/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, polyloglog 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 loglog 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 Δ=ω(log21 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.