Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910104104730624 |
|---|---|
| author | Kenneth-Mordoch, Yotam Krauthgamer, Robert |
| author_facet | Kenneth-Mordoch, Yotam Krauthgamer, Robert |
| contents | All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum $s,t$-cut for every pair of vertices $s,t$. A recent line of work on fast algorithms for APMC has culminated with a reduction of APMC to $\mathrm{polylog}(n)$-many max-flow computations. But unfortunately, no fast algorithms are currently known for exact max-flow in several standard models of computation, such as the cut-query model and the fully-dynamic model.
Our main technical contribution is a sparsifier that preserves all minimum $s,t$-cuts in an unweighted graph, and can be constructed using only approximate max-flow computations. We then use this sparsifier to devise new algorithms for APMC in unweighted graphs in several computational models: (i) a randomized algorithm that makes $\tilde{O}(n^{3/2})$ cut queries to the input graph; (ii) a deterministic fully-dynamic algorithm with $n^{3/2+o(1)}$ worst-case update time; and (iii) a randomized two-pass streaming algorithm with space requirement $\tilde{O}(n^{3/2})$. These results improve over the known bounds, even for (single pair) minimum $s,t$-cut in the respective models. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_10036 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow Kenneth-Mordoch, Yotam Krauthgamer, Robert Data Structures and Algorithms All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum $s,t$-cut for every pair of vertices $s,t$. A recent line of work on fast algorithms for APMC has culminated with a reduction of APMC to $\mathrm{polylog}(n)$-many max-flow computations. But unfortunately, no fast algorithms are currently known for exact max-flow in several standard models of computation, such as the cut-query model and the fully-dynamic model. Our main technical contribution is a sparsifier that preserves all minimum $s,t$-cuts in an unweighted graph, and can be constructed using only approximate max-flow computations. We then use this sparsifier to devise new algorithms for APMC in unweighted graphs in several computational models: (i) a randomized algorithm that makes $\tilde{O}(n^{3/2})$ cut queries to the input graph; (ii) a deterministic fully-dynamic algorithm with $n^{3/2+o(1)}$ worst-case update time; and (iii) a randomized two-pass streaming algorithm with space requirement $\tilde{O}(n^{3/2})$. These results improve over the known bounds, even for (single pair) minimum $s,t$-cut in the respective models. |
| title | Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.10036 |