A Distributed Palette Sparsification Theorem

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 Oplog nq independently sampled colors in t1, 2, ..., ∆ ` 1u. 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 Õpnq 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 polyplog nq distributed rounds with small messages. Our main result is an algorithm that computes a ∆ ` 1-coloring after palette sparsification with Oplog² nq random colors per node and runs in Oplog² ∆ ` log<sup>3</sup> log nq rounds on the sparsified graph, using Oplog nq-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 polyplog nq colors per node, requires Ωplog ∆{ log log nq rounds. This distributed palette sparsification result leads to the first polyplog nq-round algorithms for ∆ ` 1-coloring in two previously studied distributed models: the Node Capacitated Clique, and the cluster graph model.