  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 \cdot \Delta^{k/2 - 1})$-round algorithms for $G^k$. This
improves the previously-known running time for such transformation, which was
$O(R \cdot \Delta^{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$.
