Towards Optimal Distributed Edge Coloring with Fewer Colors
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_ | 1866908379887173632 |
|---|---|
| author | Jakob, Manuel Maus, Yannic Schager, Florian |
| author_facet | Jakob, Manuel Maus, Yannic Schager, Florian |
| contents | There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while $(2Δ-1)$-edge coloring can be solved in $\mathcal{O}(\log^{\ast}(n))$ rounds on constant-degree graphs, the seemingly minor reduction to $(2Δ-2)$ colors leads to an $Ω(\log n)$ lower bound [Chang, He, Li, Pettie & Uitto, SODA'18]. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper.
As our main contribution we design a deterministic distributed $\mathcal{O}(\log n)$-round reduction from the $(2Δ-2)$-edge coloring problem to the much easier $(2Δ-1)$-edge coloring problem. This reduction is optimal, as the $(2Δ-2)$-edge coloring problem admits an $Ω(\log n)$ lower bound, whereas the $2Δ-1$-edge coloring problem can be solved in $\mathcal{O}(\log^{\ast}n)$ rounds. By plugging in the $(2Δ-1)$-edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC'22] running in $\mathcal{O}(\log^{12}Δ+ \log^{\ast} n)$ rounds, we obtain an optimal runtime of $\mathcal{O}(\log n)$ rounds as long as $Δ= 2^{\mathcal{O}(\log^{1/12} n)}$. Furthermore, on general graphs our reduction improves the runtime from $\widetilde{\mathcal{O}}(\log^3 n)$ to $\widetilde{\mathcal{O}}(\log^{5/3} n)$.
In addition, we also obtain an optimal $\mathcal{O}(\log \log n)$-round randomized reduction of $(2Δ- 2)$-edge coloring to $(2Δ- 1)$-edge coloring. Lastly, we obtain an $\mathcal{O}(\log_Δn)$-round reduction from the $(2Δ-1)$-edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_13003 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards Optimal Distributed Edge Coloring with Fewer Colors Jakob, Manuel Maus, Yannic Schager, Florian Data Structures and Algorithms Distributed, Parallel, and Cluster Computing There is a huge difference in techniques and runtimes of distributed algorithms for problems that can be solved by a sequential greedy algorithm and those that cannot. A prime example of this contrast appears in the edge coloring problem: while $(2Δ-1)$-edge coloring can be solved in $\mathcal{O}(\log^{\ast}(n))$ rounds on constant-degree graphs, the seemingly minor reduction to $(2Δ-2)$ colors leads to an $Ω(\log n)$ lower bound [Chang, He, Li, Pettie & Uitto, SODA'18]. Understanding this sharp divide between very local problems and inherently more global ones remains a central open question in distributed computing and it is a core focus of this paper. As our main contribution we design a deterministic distributed $\mathcal{O}(\log n)$-round reduction from the $(2Δ-2)$-edge coloring problem to the much easier $(2Δ-1)$-edge coloring problem. This reduction is optimal, as the $(2Δ-2)$-edge coloring problem admits an $Ω(\log n)$ lower bound, whereas the $2Δ-1$-edge coloring problem can be solved in $\mathcal{O}(\log^{\ast}n)$ rounds. By plugging in the $(2Δ-1)$-edge coloring algorithms from [Balliu, Brandt, Kuhn & Olivetti, PODC'22] running in $\mathcal{O}(\log^{12}Δ+ \log^{\ast} n)$ rounds, we obtain an optimal runtime of $\mathcal{O}(\log n)$ rounds as long as $Δ= 2^{\mathcal{O}(\log^{1/12} n)}$. Furthermore, on general graphs our reduction improves the runtime from $\widetilde{\mathcal{O}}(\log^3 n)$ to $\widetilde{\mathcal{O}}(\log^{5/3} n)$. In addition, we also obtain an optimal $\mathcal{O}(\log \log n)$-round randomized reduction of $(2Δ- 2)$-edge coloring to $(2Δ- 1)$-edge coloring. Lastly, we obtain an $\mathcal{O}(\log_Δn)$-round reduction from the $(2Δ-1)$-edge coloring, albeit to the somewhat harder maximal independent set (MIS) problem. |
| title | Towards Optimal Distributed Edge Coloring with Fewer Colors |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.13003 |