Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
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_ | 1866912177401626624 |
|---|---|
| author | El-Hayek, Antoine Henzinger, Monika Li, Jason |
| author_facet | El-Hayek, Antoine Henzinger, Monika Li, Jason |
| contents | Dynamically maintaining the minimum cut in a graph $G$ under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an $n$-node graph the best known $(1+o(1))$-approximate algorithm takes $\tilde O(\sqrt{n})$ update time [Thorup 2007]. If the minimum cut is guaranteed to be $(\log n)^{o(1)}$, a deterministic exact algorithm with $n^{o(1)}$ update time exists [Jin, Sun, Thorup 2024]. We present the first fully dynamic algorithm for $(1+o(1))$-approximate minimum cut with $n^{o(1)}$ update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15069 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation El-Hayek, Antoine Henzinger, Monika Li, Jason Data Structures and Algorithms Dynamically maintaining the minimum cut in a graph $G$ under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an $n$-node graph the best known $(1+o(1))$-approximate algorithm takes $\tilde O(\sqrt{n})$ update time [Thorup 2007]. If the minimum cut is guaranteed to be $(\log n)^{o(1)}$, a deterministic exact algorithm with $n^{o(1)}$ update time exists [Jin, Sun, Thorup 2024]. We present the first fully dynamic algorithm for $(1+o(1))$-approximate minimum cut with $n^{o(1)}$ update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs. |
| title | Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.15069 |