1.9781611977912.142.pdf (880.86 kB)

# A Distributed Palette Sparsification Theorem.

conference contribution

posted on 2024-05-22, 12:23 authored by Maxime Flin, Mohsen Ghaffari, Magnús M Halldórsson, Fabian Kuhn, Alexandre NolinThe 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.
Our main result is an algorithm that computes a Δ + 1-coloring after palette sparsification with O (log2 n) random colors per node and runs in O(log2 Δ + log3 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 LOCAL model on the sparsified graph, given by palette sparsification, for any poly (log n) colors per node, requires Ω(log Δ/ log log n) rounds. This distributed palette sparsification result leads to 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.
* The full version of the paper can be accessed at https://arxiv.org/abs/2301.06457

## History

## Editor

Woodruff DP## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM-SIAM Symposium on Discrete Algorithms (SODA)## Journal

SODA## Page Range

4083-4123## Publisher

SIAM## BibTeX

@conference{Flin:Ghaffari:Halldórsson:Kuhn:Nolin:2024, title = "A Distributed Palette Sparsification Theorem.", author = "Flin, Maxime" AND "Ghaffari, Mohsen" AND "Halldórsson, Magnús M" AND "Kuhn, Fabian" AND "Nolin, Alexandre", editor = "Woodruff, David P", year = 2024, month = 1, journal = "SODA", pages = "4083--4123", publisher = "SIAM" }## Usage metrics

## Categories

No categories selected## Keywords

## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC