Faster Distributed Δ-Coloring via a Reduction to MIS

Summary

Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of Õ(log^{5/3} n) rounds for maximal independent set (MIS) and (Δ + 1)-coloring [Ghaffari, Grunau, FOCS'24] and Õ(log^{19/9} n) rounds for the more restrictive Δ-coloring problem [Ghaffari, Kuhn, FOCS'21; Ghaffari, Grunau, FOCS'24; Bourreau, Brandt, Nolin, STOC'25]. In our work, we show that Δ-coloring can be solved deterministically in Õ(log^{5/3} n) rounds as well, matching the currently best bound for (Δ + 1)-coloring. We achieve our result by developing a reduction from Δ-coloring to MIS that guarantees that the (asymptotic) complexity of Δ-coloring is at most the complexity of MIS, unless MIS can be solved in sublogarithmic time, in which case, due to the Ω(log n)-round Δ-coloring lower bound from [BFHKLRSU, STOC'16], our reduction implies a tight complexity of Θ(log n) for Δ-coloring. In particular, any improvement on the complexity of the MIS problem will yield the same improvement for the complexity of Δ-coloring (up to the true complexity of Δ-coloring). Our reduction also yields improvements for Δ-coloring in the randomized LOCAL model and when complexities are parameterized by both n and Δ. For instance, we obtain a randomized complexity bound of Õ(log^{5/3} log n) rounds (improving over the state of the art of Õ(log^{8/3} log n) rounds) on general graphs and tight complexities of Θ(log n) and Θ(log log n) for the deterministic, resp. randomized, complexity on bounded-degree graphs. In the special case of graphs of constant clique number (which for instance include bipartite graphs), we additionally give a reduction to the (Δ + 1)-coloring problem.