A Distributed Palette Sparsification Theorem.

Summary

The celebrated palette sparsification result of [Assadi, Chen, and Khanna SODA’19] shows that to compute a Δ + 1 coloring of the graph, where Δ denotes the maximum degree, it suffices if each node limits its color choice to O(log n) independently sampled colors in {1, 2,…, Δ + 1}. They showed that it is possible to color the resulting sparsified graph—the spanning subgraph with edges between neighbors that sampled a common color, which are only Õ(n) edges—and obtain a Δ + 1 coloring for the original graph. However, to compute the actual coloring, that information must be gathered at a single location for centralized processing. We seek instead a local algorithm to compute such a coloring in the sparsified graph. The question is if this can be achieved in poly (log n) distributed rounds with small messages. Our main result is an algorithm that computes a Δ + 1-coloring after palette sparsification with O (log2 n) random colors per node and runs in O(log2 Δ + log3 log n) rounds on the sparsified graph, using O(log n)-bit messages. We show that this is close to the best possible: any distributed Δ + 1-coloring algorithm that runs in the LOCAL model on the sparsified graph, given by palette sparsification, for any poly (log n) colors per node, requires Ω(log Δ/ log log n) rounds. This distributed palette sparsification result leads to the first poly (log n)- round algorithms for Δ + 1-coloring in two previously studied distributed models: the Node Capacitated Clique, and the cluster graph model. * The full version of the paper can be accessed at https://arxiv.org/abs/2301.06457