An optimal distributed (Δ+1)-coloring algorithm?

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 ( v ’s palette has size deg( v )+1) on n ′-vertex graphs. This improves upon a previous randomized algorithm of Harris, Schneider, and Su (STOC 2016). with complexity O (√logΔ + loglog 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), with complexity O (√Δlog 2.5 Δ + log * n ). 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 ′) by Panconesi and Srinivasan (Journal of Algorithms 1996), and it is quite plausible that the complexities of both problems are the same, asymptotically.

Authors

• Yi-Jun Chang
• Wenzheng Li
• Seth Pettie

Keywords

• Distributed algorithms
• Local model
• Vertex Coloring