Speedup of Distributed Algorithms for Power Graphs in the CONGEST Model
share
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. We develop a general deterministic technique that transforms R-round algorithms for G with certain properties into O(R ·Δ^k/2 - 1)-round 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^2. We also obtain significant improvements for problems with larger number of rounds in G.
READ FULL TEXT