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(log * n + Det d (poly log n)) time, where Det d (n ′ ) is the deterministic complexity of (deg +1)-list coloring on n ′ -vertex graphs. This improves upon a previous randomized algorithm of Harris, Schneider, and Su (STOC 2016) with complexity O( log ∆ + log log n + Det d (poly log n)), and (when ∆ is sufficiently large) is much faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski (FOCS 2016), whose time complexity is O( Our algorithm appears to be optimal. It matches the Ω(log * n) randomized lower bound, due to Naor (SIDMA 1991) and sort of matches the Ω(Det(poly log n)) randomized lower bound due to Chang, Kopelowitz, and Pettie (FOCS 2016), where Det is the deterministic complexity of (∆ + 1)-list coloring. The best known upper bounds on Det d (n ′ ) and Det(n ′ ) are both 2 O ( √ log n ′ ) (Panconesi and Srinivasan (J. Algor 1996)) and it is quite plausible that the complexities of both problems are the same, asymptotically. Later, Chang, Kopelowitz, and Pettie (CKP) [8] gave a simple proof illustrating why graph shattering is inherent to the LOCAL model: the randomized complexity of any locally checkable problem 2 is at least its deterministic complexity on log n-size instances. The CKP lower bound explains why the state-of-the-art randomized symmetry breaking algorithms have such strange stated running times: they all depend on a randomized graph shattering routine (Rand.) and a deterministic (Det.) algorithm. • O(log ∆ + 2 O ( √ log log n) ) for MIS (Rand. due to [16] and Det. to [27] ), due to [19] and Det. to [27] ), • O(log ∆ + (log log n) 3 ) for maximal matching (Rand. due to [5] and Det. to [13] ), • O((log log n) 8 ) for (2∆ − 1)-edge coloring (Rand. due to [12] and Det. to [14] ).
There is a randomized O log * n + 2 √ log log n -time algorithm for (∆ + 1)-coloring by Chang et al. REF .
An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018
Computer Science