Faster Distributed $Δ$-Coloring via a Reduction to MIS
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917025852424192 |
|---|---|
| author | Bourreau, Yann Brandt, Sebastian Nolin, Alexandre |
| author_facet | Bourreau, Yann Brandt, Sebastian Nolin, Alexandre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_01762 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster Distributed $Δ$-Coloring via a Reduction to MIS Bourreau, Yann Brandt, Sebastian Nolin, Alexandre Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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. |
| title | Faster Distributed $Δ$-Coloring via a Reduction to MIS |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.01762 |