Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
This addresses a fundamental challenge in distributed computing for network synchronization and resource allocation, offering near-optimal performance with significant speedups.
The paper tackles the problem of distributed vertex coloring in graphs with maximum degree Δ, presenting an algorithm that computes a (Δ-k)-coloring in Õ(log⁴ log n) rounds, which is nearly optimal and improves exponentially on prior work for polylogarithmic Δ.
For any $Î$, let $k_Î$ be the maximum integer $k$ such that $(k+1)(k+2)\le Î$. We give a distributed \LOCAL algorithm that, given an integer $k < k_Î$, computes a valid $Î-k$-coloring if one exists. The algorithm runs in $\tilde{O}(\log^4 \log n)$ rounds, which is within a polynomial factor of the $Ω(\log\log n)$ lower bound, which already applies to the case $k=0$. It is also best possible in the sense that if $k \ge k_Î$, the problem requires $Ω(n/Î)$ distributed rounds [Molloy, Reed, '14, Bamas, Esperet '19]. For $Î$ at most polylogarithmic, the algorithm is an exponential improvement over the current state of the art of $O(\log^{49/12} n)$ rounds. When $Î\ge (\log n)^{50}$, our algorithm achieves an even faster runtime of $O(\log^* n)$ rounds.