A Distributed Palette Sparsification Theorem
share
Is fully decentralized graph streaming possible? We consider this question in the context of the Δ+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 Δ+1-coloring after palette sparsification with polylog n random colors per node and runs in O(log^2 Δ + 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 Δ+1-coloring algorithm that runs in the model on the sparsified graph given by palette sparsification requires Ω(logΔ / loglog 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 Δ+1-coloring in two previously studied distributed models: the Node Capacitated Clique, and the cluster graph model.
READ FULL TEXT