Locally-iterative distributed (∆ + 1)-coloring below szegedy-vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models

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 − nei hborhood. 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" [39]. 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 [1, 2, 17, 29]. The latter gave rise to faster algorithms, but their heavy machinery which is of non-locally-iterative nature made them far less suitable to various settings. In this paper 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. • We obtain self-stabilizing distributed algorithms for (∆ + 1)-vertex-coloring, (2∆ − 1)-edge-coloring, maximal independent set and maximal matching with O(∆ + log^∗ n) time. This significantly improves previously-known results that have O(n) or larger running times [21]. • We devise a (2∆ − 1)-edge-coloring algorithm in the CONGEST model with O(∆ + log^∗ n) time and O(∆)-edge-coloring in the Bit-Round model with O(∆ + log n) time. The factors of log^∗ n and log n are unavoidable in the CONGEST and Bit-Round models, respectively. Previously-known algorithms had superlinear dependency on ∆ for (2∆ − 1)-edge-coloring in these models. • We obtain an arbdefective coloring algorithm with running time O(∆+log^∗ n). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it in order to compute a proper (1 +)∆-coloring within O(∆ + log^∗ n) time, and (∆ + 1)-coloring within O(∆ log ∆ log^∗ ∆ + log^∗ n) time. This improves the recent state-of-the-art bounds of Barenboim from PODC'15 [1] and Fraigniaud et al. from FOCS'16 [17] by polylogarithmic factors. • Our algorithms are applicable to the SET-LOCAL model [23] (also known as the weak LOCAL model). In this model a relatively strong lower bound of Ω(∆¹/³) is known for (∆ + 1)-coloring. However, most of the coloring algorithms do not work in this model. (In [23] only Linial's O(∆²)-time algorithm and Kuhn-Wattenhofer O(∆ log ∆)-time algorithms are shown to work in it.) We obtain the first linear-in-∆ algorithms that work also in this model.