## Abstract

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 Oplog nq independently sampled colors in t1, 2, ..., ∆ ` 1u. 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 Õpnq 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 polyplog nq distributed rounds with small messages. Our main result is an algorithm that computes a ∆ ` 1-coloring after palette sparsification with Oplog^{2} nq random colors per node and runs in Oplog^{2} ∆ ` log^{3} log nq rounds on the sparsified graph, using Oplog nq-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 polyplog nq colors per node, requires Ωplog ∆{ log log nq rounds. This distributed palette sparsification result leads to the first polyplog nq-round algorithms for ∆ ` 1-coloring in two previously studied distributed models: the Node Capacitated Clique, and the cluster graph model.

Original language | English |
---|---|

Pages | 4083-4123 |

Number of pages | 41 |

DOIs | |

Publication status | Published - 2024 |

Event | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 - Alexandria, United States Duration: 7 Jan 2024 → 10 Jan 2024 |

### Conference

Conference | 35th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 |
---|---|

Country/Territory | United States |

City | Alexandria |

Period | 7/01/24 → 10/01/24 |

### Bibliographical note

Publisher Copyright:Copyright © 2024 by SIAM.