Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model

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.[25] that required O(∆ + log^∗ n) rounds, and the standard simulation of Linial [30] 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. [25]. 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.