{"ID":2842121,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.10036","arxiv_id":"2511.10036","title":"Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow","abstract":"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.","short_abstract":"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 cur...","url_abs":"https://arxiv.org/abs/2511.10036","url_pdf":"https://arxiv.org/pdf/2511.10036v2","authors":"[\"Yotam Kenneth-Mordoch\",\"Robert Krauthgamer\"]","published":"2025-11-13T07:21:00Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}