CISPA
Browse
1.9781611977912.142.pdf (880.86 kB)

A Distributed Palette Sparsification Theorem.

Download (880.86 kB)
conference contribution
posted on 2024-05-22, 12:23 authored by Maxime Flin, Mohsen Ghaffari, Magnús M Halldórsson, Fabian Kuhn, Alexandre Nolin
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. 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

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC