Deterministic Minimum Steiner Cut in Maximum Flow Time
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911939482877952 |
|---|---|
| author | Ding, Matthew Li, Jason |
| author_facet | Ding, Matthew Li, Jason |
| contents | We devise a deterministic algorithm for minimum Steiner cut, which uses $(\log n)^{O(1)}$ maximum flow calls and additional near-linear time. This algorithm improves on Li and Panigrahi's (FOCS 2020) algorithm, which uses $(\log n)^{O(1/ε^4)}$ maximum flow calls and additional $O(m^{1+ε})$ time, for $ε> 0$. Our algorithm thus shows that deterministic minimum Steiner cut can be solved in maximum flow time up to polylogarithmic factors, given any black-box deterministic maximum flow algorithm. Our main technical contribution is a novel deterministic graph decomposition method for terminal vertices that generalizes all existing $s$-strong partitioning methods, which we believe may have future applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_16415 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Deterministic Minimum Steiner Cut in Maximum Flow Time Ding, Matthew Li, Jason Data Structures and Algorithms Discrete Mathematics G.2.2; F.2.2 We devise a deterministic algorithm for minimum Steiner cut, which uses $(\log n)^{O(1)}$ maximum flow calls and additional near-linear time. This algorithm improves on Li and Panigrahi's (FOCS 2020) algorithm, which uses $(\log n)^{O(1/ε^4)}$ maximum flow calls and additional $O(m^{1+ε})$ time, for $ε> 0$. Our algorithm thus shows that deterministic minimum Steiner cut can be solved in maximum flow time up to polylogarithmic factors, given any black-box deterministic maximum flow algorithm. Our main technical contribution is a novel deterministic graph decomposition method for terminal vertices that generalizes all existing $s$-strong partitioning methods, which we believe may have future applications. |
| title | Deterministic Minimum Steiner Cut in Maximum Flow Time |
| topic | Data Structures and Algorithms Discrete Mathematics G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2312.16415 |