A Distributed Palette Sparsification Theorem

Is fully decentralized graph streaming possible? We consider this question in the context of the $\Delta+1$-coloring problem. With the celebrated distributed sketching technique of palette sparsification [Assadi, Chen, and Khanna SODA'19], nodes limit themselves to $O(\log n)$ independently sampled colors. They showed that it suffices to color the resulting sparsified graph with edges between nodes that sampled a common color. To compute the actual coloring, however, that information must be gathered at a single server 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 $\Delta+1$-coloring after palette sparsification with $poly\log n$ random colors per node and runs in $O(\log^2 \Delta + \log^3 \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 $\Delta+1$-coloring algorithm that runs in the \LOCAL model on the sparsified graph given by palette sparsification requires $\Omega(\log \Delta / \log\log n)$ rounds. Our result has implications beyond streaming, as space efficiency also leads to low message complexity. In particular, our algorithm yields the first $poly(\log n)$-round algorithms for $\Delta+1$-coloring in two previously studied distributed models: the Node Capacitated Clique, and the cluster graph model.