A Distributed Palette Sparsification Theorem
Maxime Flin, Mohsen Ghaffari, Magnús M. Halldórsson, Fabian Kühn, Alexandre Nolin · Society for Industrial and Applied Mathematics eBooks · 2024
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.