Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929414577586176 |
|---|---|
| author | Elkin, Michael Khuzman, Ariel |
| author_facet | Elkin, Michael Khuzman, Ariel |
| contents | We study the edge-coloring problem in simple $n$-vertex $m$-edge graphs with maximum degree $Δ$. This is one of the most classical and fundamental graph-algorithmic problems. Vizing's celebrated theorem provides $(Δ+1)$-edge-coloring in $O(m\cdot n)$ deterministic time. This running time was improved to $O\left(m\cdot\min\left\{Δ\cdot\log n,\sqrt{n}\right\}\right)$, and very recently to randomized $\tilde{O}\left(m\cdot n^{1/3}\right)$. A randomized $(1+\varepsilon)Δ$-edge-coloring algorithm can be computed in $O\left(m\cdot\frac{\log^6 n}{\varepsilon^2}\right)$ time, and for large values of $Δ$, this task requires randomized $O\left(\frac{m\cdot\log\varepsilon^{-1}}{\varepsilon^2}\right)$ time. It was however open if there exists a deterministic near-linear time algorithm for this basic problem. We devise a simple deterministic $(1+\varepsilon)Δ$-edge-coloring algorithm with running time $O\left(m\cdot\frac{\log n}{\varepsilon}\right)$. A randomized variant of our algorithm has running time $O(m\cdot(\varepsilon^{-18}+\log(\varepsilon\cdotΔ)))$.
We also study edge-coloring of graphs with arboricity at most $α$. A randomized computation of $(Δ+1)$-edge-coloring requires $\tilde{O}\left(\min\{m\cdot\sqrt{n},m\cdotΔ\}\cdot\fracαΔ\right)$ time. Deterministically, this task can be done in $O\left(m\cdotα^7\cdot\log n\right)$ time. However, for large values of $α$, these algorithms require super-linear time. We devise a deterministic $(Δ+\varepsilonα)$-edge-coloring algorithm with running time $O\left(\frac{m\cdot\log n}{\varepsilon^7}\right)$. A randomized version of our algorithm requires $O\left(\frac{m\cdot\log n}{\varepsilon}\right)$ expected time.
Our algorithm is based on a novel two-way degree-splitting, which we devise in this paper. We believe that this technique is of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10538 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time Elkin, Michael Khuzman, Ariel Data Structures and Algorithms We study the edge-coloring problem in simple $n$-vertex $m$-edge graphs with maximum degree $Δ$. This is one of the most classical and fundamental graph-algorithmic problems. Vizing's celebrated theorem provides $(Δ+1)$-edge-coloring in $O(m\cdot n)$ deterministic time. This running time was improved to $O\left(m\cdot\min\left\{Δ\cdot\log n,\sqrt{n}\right\}\right)$, and very recently to randomized $\tilde{O}\left(m\cdot n^{1/3}\right)$. A randomized $(1+\varepsilon)Δ$-edge-coloring algorithm can be computed in $O\left(m\cdot\frac{\log^6 n}{\varepsilon^2}\right)$ time, and for large values of $Δ$, this task requires randomized $O\left(\frac{m\cdot\log\varepsilon^{-1}}{\varepsilon^2}\right)$ time. It was however open if there exists a deterministic near-linear time algorithm for this basic problem. We devise a simple deterministic $(1+\varepsilon)Δ$-edge-coloring algorithm with running time $O\left(m\cdot\frac{\log n}{\varepsilon}\right)$. A randomized variant of our algorithm has running time $O(m\cdot(\varepsilon^{-18}+\log(\varepsilon\cdotΔ)))$. We also study edge-coloring of graphs with arboricity at most $α$. A randomized computation of $(Δ+1)$-edge-coloring requires $\tilde{O}\left(\min\{m\cdot\sqrt{n},m\cdotΔ\}\cdot\fracαΔ\right)$ time. Deterministically, this task can be done in $O\left(m\cdotα^7\cdot\log n\right)$ time. However, for large values of $α$, these algorithms require super-linear time. We devise a deterministic $(Δ+\varepsilonα)$-edge-coloring algorithm with running time $O\left(\frac{m\cdot\log n}{\varepsilon^7}\right)$. A randomized version of our algorithm requires $O\left(\frac{m\cdot\log n}{\varepsilon}\right)$ expected time. Our algorithm is based on a novel two-way degree-splitting, which we devise in this paper. We believe that this technique is of independent interest. |
| title | Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.10538 |