We obtain improved distributed algorithms in the CONGEST message-passing setting for problems on power graphs of an input graph G. This includes Coloring, Maximal Independent Set, and related problems. For R = f(Δ^k,n), we develop a general deterministic technique that transforms R-round LOCAL model algorithms for G^k with certain properties into O(R ⋅ Δ^{k/2-1})-round CONGEST algorithms for G^k. This improves the previously-known running time for such transformation, which was O(R⋅Δ^{k-1}). Consequently, for problems that can be solved by algorithms with the required properties and within polylogarithmic number of rounds, we obtain quadratic improvement for G^k and exponential improvement for G². We also obtain significant improvements for problems with larger number of rounds in G. Notable implications of our technique are the following deterministic distributed algorithms: - We devise a distributed algorithm for O(Δ⁴)-coloring of G² whose number of rounds is O(log Δ + log^* n). This improves exponentially (in terms of Δ) the best previously-known deterministic result of Halldorsson, Kuhn and Maus.[M. M. Halldorson et al., 2020] that required O(Δ + log^{*}n) rounds, and the standard simulation of Linial [N. Linial, 1992] algorithm in G^k that required O(Δ ⋅ log^* n) rounds. - We devise an algorithm for O(Δ²)-coloring of G² with O(Δ ⋅ log Δ + log^*n) rounds, and (Δ²+1)-coloring with O(Δ^{1.5} ⋅ log Δ + log^*n) rounds. This improves quadratically, and by a power of 4/3, respectively, the best previously-known results of Halldorsson, Khun and Maus. [M. M. Halldorson et al., 2020]. - For k > 2, our running time for O(Δ^{2k})-coloring of G^k is O(k⋅Δ^{k/2-1}⋅log Δ⋅log^* n). Our running time for O(Δ^k)-coloring of G^k is Õ(k⋅Δ^{k-1}⋅log^* n). This improves best previously-known results quadratically, and by a power of 3/2, respectively. - For constant k > 2, our upper bound for O(Δ^{2k})-coloring of G^k nearly matches the lower bound of Fraigniaud, Halldorsson and Nolin. [P. Fraigniaud et al., 2020] for checking the correctness of a coloring in G^k.

We consider graph coloring and related problems in the distributed message-passing model.Locally-iterative algorithmsare 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 its1-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 timeO(Δ + log*n), i.e.,belowSzegedy-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 withO(Δ + log*n) time. This significantly improves previously known results that haveO(n)or larger running times [ 23 ]. We devise a (2Δ - 1)-edge-coloring algorithm in the CONGEST model withO(Δ + log*n) time andO(Δ)-edge-coloring in the Bit-Round model withO(Δ + logn) time. The factors of log*nand lognare 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 timeO(√ Δ + log*n). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it to compute a proper (1 + ε)Δ-coloring withinO(√ Δ + log*n) time and Δ + 1-coloring withinO(√ Δ log Δ log*Δ + log*n) time. This improves the recent state-of-the-art bounds of Barenboim from PODC’15 [ 2 ] and Fraigniaud et al. from FOCS’16 [ 19 ] by polylogarithmic factors. Our algorithms are applicable to the SET-LOCAL model [ 25 ] (also known as the weak LOCAL model). In this model a relatively strong lower bound of Ω (Δ1/3) is known for Δ + 1-coloring. However, most of the coloring algorithms do not work in this model. (In Reference [ 25 ] only Linial’sO(Δ2)-time algorithm and Kuhn-WattenhoferO(Δ log Δ)-time algorithms are shown to work in it.) We obtain the first linear-in-Δ Δ + 1-coloring algorithms that work also in this model.