{"ID":2887335,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.01762","arxiv_id":"2508.01762","title":"Faster Distributed $Δ$-Coloring via a Reduction to MIS","abstract":"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 $\\tilde{O}(\\log^{5/3} n)$ rounds for maximal independent set (MIS) and $(Δ+ 1)$-coloring [Ghaffari, Grunau, FOCS'24] and $\\tilde{O}(\\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 $\\tilde{O}(\\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 yields improvements for $Δ$-coloring in the randomized LOCAL model and when complexities are parameterized by both $n$ and $Δ$. We obtain a randomized complexity bound of $\\tilde{O}(\\log^{5/3} \\log n)$ rounds (improving over the state of the art of $\\tilde{O}(\\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 also give a reduction to the $(Δ+1)$-coloring problem.","short_abstract":"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 $\\tilde{O}(\\log^{5/3} n)$ rounds for maximal independent set (MIS) and $(Δ+ 1)$-coloring [Ghaffari, Grunau, FOCS'24] and $\\tilde{O}(\\log^{19/9} n)...","url_abs":"https://arxiv.org/abs/2508.01762","url_pdf":"https://arxiv.org/pdf/2508.01762v2","authors":"[\"Yann Bourreau\",\"Sebastian Brandt\",\"Alexandre Nolin\"]","published":"2025-08-03T14:04:06Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.DS\"]","methods":"[]","has_code":false}