An Optimal Distributed (Δ+1)-Coloring Algorithm?
share
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(^∗ n + Det_d(poly 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(√(Δ) + n + Det_d(poly n)), and is dramatically faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski (FOCS 2016), with complexity O(√(Δ)^2.5Δ + ^* n). Our algorithm appears to be optimal. It matches the Ω(^∗ n) randomized lower bound, due to Naor (SIDMA 1991) and sort of matches the Ω(Det(poly 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(√( n')) by Panconesi and Srinivasan (Journal of Algorithms 1996), and it is quite plausible that the complexities of both problems are the same, asymptotically.
READ FULL TEXT