Faster Vizing and Near-Vizing Edge Coloring Algorithms
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914806682877952 |
|---|---|
| author | Assadi, Sepehr |
| author_facet | Assadi, Sepehr |
| contents | Vizing's celebrated theorem states that every simple graph with maximum degree $Δ$ admits a $(Δ+1)$ edge coloring which can be found in $O(m \cdot n)$ time on $n$-vertex $m$-edge graphs. This is just one color more than the trivial lower bound of $Δ$ colors needed in any proper edge coloring. After a series of simplifications and variations, this running time was eventually improved by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to $O(m\sqrt{n\log{n}})$ time. This has effectively remained the state-of-the-art modulo an $O(\sqrt{\log{n}})$-factor improvement by Sinnamon in 2019.
As our main result, we present a novel randomized algorithm that computes a $Δ+O(\log{n})$ coloring of any given simple graph in $O(m\logΔ)$ expected time; in other words, a near-linear time randomized algorithm for a ``near''-Vizing's coloring.
As a corollary of this algorithm, we also obtain the following results:
* A randomized algorithm for $(Δ+1)$ edge coloring in $O(n^2\log{n})$ expected time. This is near-linear in the input size for dense graphs and presents the first polynomial time improvement over the longstanding bounds of Gabow et.al. for Vizing's theorem in almost four decades.
* A randomized algorithm for $(1+\varepsilon) Δ$ edge coloring in $O(m\log{(1/\varepsilon)})$ expected time for any $\varepsilon = ω(\log{n}/Δ)$. The dependence on $\varepsilon$ exponentially improves upon a series of recent results that obtain algorithms with runtime of $Ω(m/\varepsilon)$ for this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13371 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Vizing and Near-Vizing Edge Coloring Algorithms Assadi, Sepehr Data Structures and Algorithms Vizing's celebrated theorem states that every simple graph with maximum degree $Δ$ admits a $(Δ+1)$ edge coloring which can be found in $O(m \cdot n)$ time on $n$-vertex $m$-edge graphs. This is just one color more than the trivial lower bound of $Δ$ colors needed in any proper edge coloring. After a series of simplifications and variations, this running time was eventually improved by Gabow, Nishizeki, Kariv, Leven, and Terada in 1985 to $O(m\sqrt{n\log{n}})$ time. This has effectively remained the state-of-the-art modulo an $O(\sqrt{\log{n}})$-factor improvement by Sinnamon in 2019. As our main result, we present a novel randomized algorithm that computes a $Δ+O(\log{n})$ coloring of any given simple graph in $O(m\logΔ)$ expected time; in other words, a near-linear time randomized algorithm for a ``near''-Vizing's coloring. As a corollary of this algorithm, we also obtain the following results: * A randomized algorithm for $(Δ+1)$ edge coloring in $O(n^2\log{n})$ expected time. This is near-linear in the input size for dense graphs and presents the first polynomial time improvement over the longstanding bounds of Gabow et.al. for Vizing's theorem in almost four decades. * A randomized algorithm for $(1+\varepsilon) Δ$ edge coloring in $O(m\log{(1/\varepsilon)})$ expected time for any $\varepsilon = ω(\log{n}/Δ)$. The dependence on $\varepsilon$ exponentially improves upon a series of recent results that obtain algorithms with runtime of $Ω(m/\varepsilon)$ for this problem. |
| title | Faster Vizing and Near-Vizing Edge Coloring Algorithms |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2405.13371 |