Overcoming Congestion in Distributed Coloring
share
We present a new technique to efficiently sample and communicate a large number of elements from a distributed sampling space. When used in the context of a recent LOCAL algorithm for (degree+1)-list-coloring (D1LC), this allows us to solve D1LC in O(log^5 log n) CONGEST rounds, and in only O(log^* n) rounds when the graph has minimum degree Ω(log^7 n), w.h.p. The technique also has immediate applications in testing some graph properties locally, and for estimating the sparsity/density of local subgraphs in O(1) CONGEST rounds, w.h.p.
READ FULL TEXT