Result: DISTRIBUTED (Δ + 1)-COLORING VIA ULTRAFAST GRAPH SHATTERING.

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper, we present a new algorithm for (Δ +1)-list coloring in the randomized LOCAL model running in O(Detd(poly log n)) = O(poly(log log n)) time, where Detd(n') is the deterministic complexity of (deg +1)-list coloring on n' -vertex graphs. (In this problem, each v has a palette of size deg(v)+1.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [J. ACM, 65 (2018), 19] with complexity O(√log Δ +log log n+Detd(poly log n)) = O(√log n). Unless Δ is small, it is also faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016] and Barenboim, Elkin, and Goldenberg [Proceedings of the 38th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2018], with complexity O(√Δ log Δ log* Δ log n). Our algorithm's running time is syntactically very similar to the Ω(Det (poly log n)) lower bound of Chang, Kopelowitz, and Pettie [SIAM J. Comput., 48 (2019), pp. 122--143], where Det (n') is the deterministic complexity of (Δ + 1)-list coloring on n'-vertex graphs. Although distributed coloring has been actively investigated for 30 years, the best deterministic algorithms for (deg +1)- and (Δ + 1)-list coloring (that depend on n' but not Δ) use a black-box application of network decompositions. The recent deterministic network decomposition algorithm of Rozhoň and Ghaffari [Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), 2020] implies that Detd(n') and Det(n') are both poly(log n'). Whether they are asymptotically equal is an open problem. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)