2023/01/16 by Flin, Maxime, Ghaffari, Mohsen, Halldórsson, Magnús M. +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2301.06457
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 O(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 Δ/ loglog 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.