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 2 nq random colors per node and runs in Oplog 2 ∆ log 3 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.