Overcoming Congestion in Distributed Coloring

Abstract

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 $(\mathrm{degree}+1)$-list-coloring (D1LC), this allows us to solve D1LC in $O({\log }^5\log n)$ CONGEST rounds, and in only $O({\log }^{\ast }n)$ rounds when the graph has minimum degree $\Omega ({\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.

This paper incorporates results from the technical report arXiv:2105.04700 on adapting LOCAL algorithms to CONGEST. This excludes the other results in arXiv:2105.04700, which were refactored in arXiv:2112.00604