On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916681663643648 |
|---|---|
| author | El-Hayek, Antoine Hanauer, Kathrin Henzinger, Monika |
| author_facet | El-Hayek, Antoine Hanauer, Kathrin Henzinger, Monika |
| contents | Given a graph $G$ that is modified by a sequence of edge insertions and deletions, we study the Maximum $k$-Edge Coloring problem Having access to $k$ colors, how can we color as many edges of $G$ as possible such that no two adjacent edges share the same color? While this problem is different from simply maintaining a $b$-matching with $b=k$, the two problems are closely related: a maximum $k$-matching always contains a $\frac{k+1}k$-approximate maximum $k$-edge coloring. However, maximum $b$-matching can be solved efficiently in the static setting, whereas the Maximum $k$-Edge Coloring problem is NP-hard and even APX-hard for $k \ge 2$.
We present new results on both problems: For $b$-matching, we show a new integrality gap result and for the case where $b$ is a constant, we adapt Wajc's matching sparsification scheme~[STOC20].
Using these as basis, we give three new algorithms for the dynamic Maximum $k$-Edge Coloring problem: Our MatchO algorithm builds on the dynamic $(2+ε)$-approximation algorithm of Bhattacharya, Gupta, and Mohan~[ESA17] for $b$-matching and achieves a $(2+ε)\frac{k+1} k$-approximation in $O(poly(\log n, ε^{-1}))$ update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic $8$-approximation algorithm by Bhattacharya, Henzinger, and Italiano~[SODA15] for fractional $b$-matching and achieves a $(8+ε)\frac{3k+3}{3k-1}$-approximation in $O(poly(\log n, ε^{-1}))$ update time against an adaptive adversary. Moreover, our reductions use the dynamic $b$-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic $b$-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm that runs in $O(Δ+k)$ update time, while guaranteeing a $2.16$~approximation factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_01149 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring El-Hayek, Antoine Hanauer, Kathrin Henzinger, Monika Data Structures and Algorithms Given a graph $G$ that is modified by a sequence of edge insertions and deletions, we study the Maximum $k$-Edge Coloring problem Having access to $k$ colors, how can we color as many edges of $G$ as possible such that no two adjacent edges share the same color? While this problem is different from simply maintaining a $b$-matching with $b=k$, the two problems are closely related: a maximum $k$-matching always contains a $\frac{k+1}k$-approximate maximum $k$-edge coloring. However, maximum $b$-matching can be solved efficiently in the static setting, whereas the Maximum $k$-Edge Coloring problem is NP-hard and even APX-hard for $k \ge 2$. We present new results on both problems: For $b$-matching, we show a new integrality gap result and for the case where $b$ is a constant, we adapt Wajc's matching sparsification scheme~[STOC20]. Using these as basis, we give three new algorithms for the dynamic Maximum $k$-Edge Coloring problem: Our MatchO algorithm builds on the dynamic $(2+ε)$-approximation algorithm of Bhattacharya, Gupta, and Mohan~[ESA17] for $b$-matching and achieves a $(2+ε)\frac{k+1} k$-approximation in $O(poly(\log n, ε^{-1}))$ update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic $8$-approximation algorithm by Bhattacharya, Henzinger, and Italiano~[SODA15] for fractional $b$-matching and achieves a $(8+ε)\frac{3k+3}{3k-1}$-approximation in $O(poly(\log n, ε^{-1}))$ update time against an adaptive adversary. Moreover, our reductions use the dynamic $b$-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic $b$-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm that runs in $O(Δ+k)$ update time, while guaranteeing a $2.16$~approximation factor. |
| title | On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2310.01149 |