Fast Distributed Vertex Splitting with Applications.

Summary

We present polyloglogn-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into k parts such that a node of degree d(u) has ≈d(u)/k neighbors in each part. Our techniques can be seen as the first progress towards general polyloglogn-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized polyloglogn-round CONGEST algorithm for (1+ϵ)Δ-edge coloring n-node graphs of sufficiently large constant maximum degree Δ, for any ϵ>0. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.