Locally-iterative Distributed (Δ + 1)-coloring and Applications

We consider graph coloring and related problems in the distributed message-passing model. Locally-iterative algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its 1-hop-neighborhood. In STOC’93 Szegedy and Vishwanathan showed that any locally-iterative Δ + 1-coloring algorithm requires Ω (Δ log Δ + log ^* n) rounds, unless there exists “a very special type of coloring that can be very efficiently reduced” [44]. No such special coloring has been found since then. This led researchers to believe that Szegedy-Vishwanathan barrier is an inherent limitation for locally-iterative algorithms and to explore other approaches to the coloring problem [2, 3, 19, 32]. The latter gave rise to faster algorithms, but their heavy machinery that is of non-locally-iterative nature made them far less suitable to various settings. In this article, we obtain the aforementioned special type of coloring. Specifically, we devise a locally-iterative Δ + 1-coloring algorithm with running time O(Δ + log ^* n), i.e., below Szegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing, and bandwidth-restricted settings. This includes the following results: