Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow

Robert Krauthgamer; Yotam Kenneth-Mordoch

arxiv: 2511.10036 · v2 · submitted 2025-11-13 · 💻 cs.DS

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow

Yotam Kenneth-Mordoch , Robert Krauthgamer This is my paper

Pith reviewed 2026-05-17 22:40 UTC · model grok-4.3

classification 💻 cs.DS

keywords all-pairs minimum cutgraph sparsifierapproximate max-flowcut queriesdynamic algorithmsstreaming algorithmsunweighted graphs

0 comments

The pith

A sparsifier built from approximate max-flows preserves all minimum s-t cuts in unweighted graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a sparsifier for unweighted graphs that maintains the value and structure of every minimum s-t cut. This sparsifier is constructed using only approximate max-flow computations rather than exact ones. By applying this tool, the authors obtain improved algorithms for computing all-pairs minimum cuts in the cut-query model, the fully dynamic model, and the streaming model. These advances also strengthen the best known bounds even for the single-pair minimum cut problem in those settings.

Core claim

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: a randomized algorithm that makes O(n^{3/2}) cut queries, a deterministic fully-dynamic algorithm with n^{3/2+o(1)} worst-case update time, and a randomized two-pass streaming algorithm with O(n^{3/2}) space.

What carries the argument

The cut-preserving sparsifier for unweighted graphs constructed via approximate max-flow oracles.

If this is right

New randomized cut-query algorithm for all-pairs min-cut using tilde O(n^{3/2}) queries.
Deterministic fully-dynamic algorithm with n^{3/2+o(1)} worst-case update time for all-pairs min-cut.
Randomized two-pass streaming algorithm using tilde O(n^{3/2}) space for all-pairs min-cut.
Improved bounds even for single-pair min-cut in the same models.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same sparsifier idea may apply to other global cut problems that currently depend on exact max-flow oracles.
It hints that exact flow values are not required to recover exact min-cut partitions when graphs have unit capacities.
Similar constructions could be tested in additional models such as distributed or parallel computation.

Load-bearing premise

The input graph is unweighted and an efficient approximate max-flow oracle is available in the target computational model.

What would settle it

An unweighted graph and approximate max-flow oracle where the resulting sparsifier changes the minimum s-t cut value or the cut set for some vertex pair.

Figures

Figures reproduced from arXiv: 2511.10036 by Robert Krauthgamer, Yotam Kenneth-Mordoch.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a cut-preserving sparsifier built from approximate max-flow that yields improved APMC bounds in cut-query, dynamic, and streaming models, but the error analysis for exact preservation needs direct checking.

read the letter

The main takeaway is a sparsifier that keeps every minimum s-t cut identical to the original unweighted graph yet is built only from approximate max-flow calls. They then feed this sparsifier into algorithms for all-pairs min-cut, getting Õ(n^{3/2}) cut queries, n^{3/2+o(1)} worst-case dynamic update time, and Õ(n^{3/2}) streaming space. These numbers beat the previous best results that relied on exact max-flow, and the gains even apply to single-pair min-cut in the same models. That is the concrete advance. The construction itself looks like the right lever for models where exact max-flow remains expensive. Integer cut values in unweighted graphs give some slack for choosing a small enough approximation factor, so the basic idea is plausible. The paper also shows the sparsifier can be reused across the three settings without redesigning the core object each time. That reuse is a plus. The soft spot is the approximation error. The stress-test note is on target: a (1+ε) oracle can flip comparisons on small cuts, and doing this for every pair at once requires a uniform bound on misclassification. If the paper only sketches the construction without an explicit ε schedule and a union-bound or sampling argument that works for all Θ(n²) pairs, the preservation claim rests on an unverified step. Minor gaps in the write-up of the sparsifier construction would also slow a reader down. This work is aimed at people who design algorithms in restricted models and care about min-cut as a primitive. A reader who already follows dynamic or streaming graph papers will get immediate value from the new bounds if the proofs hold. It is worth sending to peer review because the reduction is new, the applications are concrete, and the claims are falsifiable once the full argument is on the table. Ask the authors to spell out the error tolerance and the exact preservation guarantee in the first round.

Referee Report

1 major / 2 minor

Summary. The paper introduces a cut-preserving sparsifier for unweighted graphs that can be constructed using only approximate max-flow oracles. This sparsifier is then used to obtain improved algorithms for all-pairs minimum cut (APMC) in three models: a randomized Õ(n^{3/2}) cut-query algorithm, a deterministic fully-dynamic algorithm with n^{3/2+o(1)} worst-case update time, and a randomized two-pass streaming algorithm using Õ(n^{3/2}) space. These bounds improve even over known single-pair min-cut results in the respective models by bypassing the need for exact max-flow.

Significance. If the sparsifier construction succeeds in preserving all minimum s-t cuts exactly, the work provides a valuable new primitive for cut problems in models where exact max-flow is not known to be efficient. The explicit improved bounds across multiple models, grounded in standard graph-theoretic reductions, represent a meaningful advance for APMC and related problems. The manuscript includes reproducible algorithmic descriptions that could be implemented and tested in the target models.

major comments (1)

[Sparsifier construction (Section 3)] Sparsifier construction (Section 3): The central claim is that the output sparsifier H preserves both the min-cut value and the actual cut sets for every s,t pair exactly. The construction repeatedly invokes a (1+ε)-approximate max-flow oracle to identify critical edges. Because min-cut values are integers, for any cut of value λ an approximation with ε > 1/(2λ) can flip comparisons between candidate cuts and cause the procedure to drop an edge that belongs to some min s,t-cut or retain a non-critical edge. No explicit setting of ε = o(1/n) together with a union-bound argument over all Θ(n²) pairs appears in the error analysis, leaving the exact preservation property unproven under the stated approximation guarantee.

minor comments (2)

[Abstract and Introduction] The abstract and introduction should explicitly state the range of ε for which the sparsifier is guaranteed to work, rather than leaving it implicit in the oracle assumption.
[Preliminaries] Notation for the sparsifier H and the original graph G should be introduced once and used consistently; several passages switch between “sparsifier” and “H” without a clear definition paragraph.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on the manuscript. The primary concern is the rigor of the error analysis for exact min-cut preservation in the sparsifier of Section 3. We respond to this point below and will strengthen the presentation in revision.

read point-by-point responses

Referee: Sparsifier construction (Section 3): The central claim is that the output sparsifier H preserves both the min-cut value and the actual cut sets for every s,t pair exactly. The construction repeatedly invokes a (1+ε)-approximate max-flow oracle to identify critical edges. Because min-cut values are integers, for any cut of value λ an approximation with ε > 1/(2λ) can flip comparisons between candidate cuts and cause the procedure to drop an edge that belongs to some min s,t-cut or retain a non-critical edge. No explicit setting of ε = o(1/n) together with a union-bound argument over all Θ(n²) pairs appears in the error analysis, leaving the exact preservation property unproven under the stated approximation guarantee.

Authors: We thank the referee for identifying this aspect of the analysis. In unweighted graphs the minimum-cut value λ for any pair satisfies 1 ≤ λ ≤ n−1. Choosing ε = 1/n² therefore guarantees ε < 1/(2λ) for every possible λ, ensuring that (1+ε)-approximate max-flow values cannot flip the comparison between a true min-cut and any cut of value at least λ+1. We will add an explicit statement of this parameter choice to Section 3. In addition, we will include a union bound over the O(n²) pairs (together with the failure probability of the approximate max-flow oracle) to show that the sparsifier preserves every minimum s-t cut exactly with high probability. These clarifications will be incorporated in the revised manuscript. revision: yes

Circularity Check

0 steps flagged

No circularity: sparsifier derived from external approximate max-flow oracle

full rationale

The derivation begins with an external approximate max-flow oracle (assumed available in the target model) and constructs a sparsifier that preserves all min s,t-cuts exactly. This sparsifier is then used to obtain APMC algorithms in cut-query, dynamic, and streaming models. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; the central claim relies on standard graph-theoretic properties of cuts and the oracle rather than internal fitting or renaming. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The claim rests on the existence of a cut-preserving sparsifier constructible from approximate max-flow oracles together with standard assumptions about undirected unweighted graphs and the availability of approximate oracles in the listed models.

axioms (2)

domain assumption The input graph is undirected and unweighted.
Explicitly stated as the setting for the sparsifier and algorithms.
domain assumption An efficient approximate max-flow oracle exists in the target model.
The sparsifier is constructed using only approximate max-flow computations.

invented entities (1)

Cut-preserving sparsifier no independent evidence
purpose: A smaller graph that retains every minimum s-t cut of the original while being buildable from approximate max-flow oracles.
New object introduced to bypass exact max-flow; no independent evidence outside the paper is provided in the abstract.

pith-pipeline@v0.9.0 · 5530 in / 1467 out tokens · 40569 ms · 2026-05-17T22:40:21.080805+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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.
IndisputableMonolith/Foundation/AlphaCoordinateFixation.lean alpha_pin_under_high_calibration unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

performing this star transform to all super-vertices yields a graph H_ap that is an APMC sparsifier

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 1 internal anchor

[1]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics , year =

[ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 265–276. ACM, 2019.doi:10.1145/3313276.3316361. [AD21] Sepehr Assadi and Aditi Dudeja. A simple semi-streaming algorithm for global minimum cuts. In4...

work page doi:10.1145/3313276.3316361 2019
[2]

[ADK+16] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng

doi:10.1137/1.9781611976496.19. [ADK+16] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. InIEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 335–344. IEEE Computer Society, 2016.doi:10.1109/FOCS.2016

work page doi:10.1137/1.9781611976496.19 2016
[3]

Cut query algorithms with star contraction

[AEG+22] Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 507–518. IEEE,

work page 2022
[4]

Low treewidth embeddings of planar and minor-free metrics

doi:10.1109/FOCS54457.2022.00055. [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, span- ners, and subgraphs. InProceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 5–14. ACM, 2012.doi:10.1145/2213556.2213560. [AKL+22] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya...

work page doi:10.1109/focs54457.2022.00055 2022
[5]

An ˜O(mn) Gomory-Hu tree construction algorithm for unweighted graphs

[BHKP07] Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. An ˜O(mn) Gomory-Hu tree construction algorithm for unweighted graphs. In39th Annual ACM Sym- posium on Theory of Computing, STOC’07, pages 605–614, 2007.doi:10.1145/1250790. 1250879. [BK96] Andr´ as A. Bencz´ ur and David R. Karger. Approximatings−tminimum cuts in ˜O(n...

work page doi:10.1145/1250790 2007
[6]

Mančinska and D

URL:http://papers.nips.cc/paper_files/paper/2023/hash/ d8a7f2f7e346410e8ac7b39d9ff28c4a-Abstract-Conference.html. [CGL+20] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Sara- nurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In61st IEEE Annual Symposium on Fo...

work page doi:10.1109/focs46700.2020.00111 2023
[7]

[FKN+22] Asaf Ferber, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney

doi:10.4230/LIPICS.ITCS.2023.50. [FKN+22] Asaf Ferber, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney. Friendly bisections of random graphs.Communications of the American Mathematical So- ciety, 2(10):380–416,

work page doi:10.4230/lipics.itcs.2023.50 2023
[8]

Frederickson

[Fre97] Greg N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees.SIAM J. Comput., 26(2):484–538, 1997.doi:10.1137/ S0097539792226825. [GH61] Ralph E. Gomory and Tien Chung Hu. Multi-terminal network flows.Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570,

work page 1997
[9]

Fully dynamic exact edge connectivity in sublinear time

[GHN+23] Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, and Christian Wulff-Nilsen. Fully dynamic exact edge connectivity in sublinear time. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 70–86. SIAM, 2023.doi:10.1137/1.9781611977554.CH3. [GHP20] Gramoz Goranci, Monika Henz...

work page doi:10.1137/1.9781611977554.ch3 2023
[10]

03427,arXiv:2510.03427

URL:https://arxiv.org/abs/2510. 03427,arXiv:2510.03427. [GK00] Michael U. Gerber and Daniel Kobler. Algorithmic approach to the satisfactory graph par- titioning problem.Eur. J. Oper. Res., 125(2):283–291, 2000.doi:10.1016/S0377-2217(99) 00459-2. [GKYY25] Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, and Wuwei Yuan. A simple and fast reduction f...

work page doi:10.1016/s0377-2217(99 2000
[11]

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Accepted to SODA 2026.arXiv:2509.02520,doi:10.48550/ARXIV.2509.02520. [GMT20] Ajinkya Gaikwad, Soumen Maity, and Shuvam Kant Tripathi. The satisfactory partition problem.CoRR, abs/2007.14339,

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2509.02520 2026
[12]

[GNT20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup

URL:https://arxiv.org/abs/2007.14339,arXiv: 2007.14339. [GNT20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connec- tivity via random 2-out contractions. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1260–1279. SIAM,

work page arXiv 2007
[13]

Matthew Weinberg

[GPRW20] Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg. New query lower bounds for submodular function minimization. In11th Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 ofLIPIcs, pages 64:1–64:16. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2020.doi:10.4230/LIPICS.ITCS.2020.64. 24 [GRST2...

work page doi:10.4230/lipics.itcs.2020.64 2020
[14]

[HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup

doi:10.1137/1.9781611976465.132. [HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, 2001.doi:10.1145/502090.502095. [HK99] Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph ...

work page doi:10.1137/1.9781611976465.132 2001
[15]

[HRW20] Monika Henzinger, Satish Rao, and Di Wang

URL:http://dl.acm.org/citation.cfm?id=1283383.1283398. [HRW20] Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connec- tivity.SIAM J. Comput., 49(1):1–36, 2020.doi:10.1137/18M1180335. [Iva25] Paata Ivanisvili. A local sufficient condition for the superadditivity that is strictly more general than the convexity. MathOverflow,

work page doi:10.1137/18m1180335 2020
[16]

[JNS25] Yonggang Jiang, Danupon Nanongkai, and Pachara Sawettamalya

URL:https://mathoverflow.net/q/490528 (version: 2025-04-04), AUTHOR PROFILE:https://mathoverflow.net/users/50901/paata-ivanisvili. [JNS25] Yonggang Jiang, Danupon Nanongkai, and Pachara Sawettamalya. Minimums–tcuts with fewer cut queries.CoRR, abs/2510.18274,

work page arXiv 2025
[17]

Severson, Przemyslaw Uznanski, and Grzegorz Stachowiak

URL:https: //arxiv.org/abs/2510.18274,arXiv:2510.18274. [JS21] Wenyu Jin and Xiaorui Sun. Fully dynamics−tedge connectivity in subpolynomial time. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 861–872. IEEE, 2021.doi:10.1109/FOCS52979.2021.00088. [JST24] Wenyu Jin, Xiaorui Sun, and Mikkel Thorup. Fully dynamic min-cut o...

work page doi:10.1109/focs52979.2021.00088 2021
[18]

[KK25a] Yotam Kenneth-Mordoch and Robert Krauthgamer

URL:https://arxiv.org/abs/2112.06916,arXiv:2112.06916. [KK25a] Yotam Kenneth-Mordoch and Robert Krauthgamer. All-pairs minimum cut using ˜O(n7/4) cut queries.CoRR, abs/2510.16741,

work page arXiv
[19]

23 Sergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas, and Henning Urbat

URL:https://arxiv.org/ abs/2510.16741,arXiv:2510.16741. [KK25b] Yotam Kenneth-Mordoch and Robert Krauthgamer. Cut-query algorithms with few rounds. In33rd Annual European Symposium on Algorithms, ESA 2025, volume 351 ofLIPIcs, pages 100:1–100:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025.doi:10.4230/LIPICS. ESA.2025.100. [KK25c] Yotam Kenn...

work page doi:10.4230/lipics 2025
[20]

01567,arXiv:2106.01567

URL:https://arxiv.org/abs/2106. 01567,arXiv:2106.01567. [MN20] Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 496–509. ACM, 2020.doi:10.1145/3357713.3384334. [MN21] Sagnik Mukhopadhyay and Danupon Na...

work page doi:10.1145/3357713.3384334 2020
[21]

[PRW24] Orestis Plevrakis, Seyoon Ragavan, and S

doi:10.1007/BF01758778. [PRW24] Orestis Plevrakis, Seyoon Ragavan, and S. Matthew Weinberg. On the cut-query complexity of approximating max-cut. In51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, volume 297 ofLIPIcs, pages 115:1–115:20. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024.doi:10.4230/LIPICS.ICALP.20...

work page doi:10.1007/bf01758778 2024

[1] [1]

Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics , year =

[ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna. Polynomial pass lower bounds for graph streaming algorithms. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 265–276. ACM, 2019.doi:10.1145/3313276.3316361. [AD21] Sepehr Assadi and Aditi Dudeja. A simple semi-streaming algorithm for global minimum cuts. In4...

work page doi:10.1145/3313276.3316361 2019

[2] [2]

[ADK+16] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng

doi:10.1137/1.9781611976496.19. [ADK+16] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. InIEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pages 335–344. IEEE Computer Society, 2016.doi:10.1109/FOCS.2016

work page doi:10.1137/1.9781611976496.19 2016

[3] [3]

Cut query algorithms with star contraction

[AEG+22] Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. In63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 507–518. IEEE,

work page 2022

[4] [4]

Low treewidth embeddings of planar and minor-free metrics

doi:10.1109/FOCS54457.2022.00055. [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, span- ners, and subgraphs. InProceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 5–14. ACM, 2012.doi:10.1145/2213556.2213560. [AKL+22] Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya...

work page doi:10.1109/focs54457.2022.00055 2022

[5] [5]

An ˜O(mn) Gomory-Hu tree construction algorithm for unweighted graphs

[BHKP07] Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi. An ˜O(mn) Gomory-Hu tree construction algorithm for unweighted graphs. In39th Annual ACM Sym- posium on Theory of Computing, STOC’07, pages 605–614, 2007.doi:10.1145/1250790. 1250879. [BK96] Andr´ as A. Bencz´ ur and David R. Karger. Approximatings−tminimum cuts in ˜O(n...

work page doi:10.1145/1250790 2007

[6] [6]

Mančinska and D

URL:http://papers.nips.cc/paper_files/paper/2023/hash/ d8a7f2f7e346410e8ac7b39d9ff28c4a-Abstract-Conference.html. [CGL+20] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Sara- nurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In61st IEEE Annual Symposium on Fo...

work page doi:10.1109/focs46700.2020.00111 2023

[7] [7]

[FKN+22] Asaf Ferber, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney

doi:10.4230/LIPICS.ITCS.2023.50. [FKN+22] Asaf Ferber, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawhney. Friendly bisections of random graphs.Communications of the American Mathematical So- ciety, 2(10):380–416,

work page doi:10.4230/lipics.itcs.2023.50 2023

[8] [8]

Frederickson

[Fre97] Greg N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees.SIAM J. Comput., 26(2):484–538, 1997.doi:10.1137/ S0097539792226825. [GH61] Ralph E. Gomory and Tien Chung Hu. Multi-terminal network flows.Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570,

work page 1997

[9] [9]

Fully dynamic exact edge connectivity in sublinear time

[GHN+23] Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, and Christian Wulff-Nilsen. Fully dynamic exact edge connectivity in sublinear time. InProceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 70–86. SIAM, 2023.doi:10.1137/1.9781611977554.CH3. [GHP20] Gramoz Goranci, Monika Henz...

work page doi:10.1137/1.9781611977554.ch3 2023

[10] [10]

03427,arXiv:2510.03427

URL:https://arxiv.org/abs/2510. 03427,arXiv:2510.03427. [GK00] Michael U. Gerber and Daniel Kobler. Algorithmic approach to the satisfactory graph par- titioning problem.Eur. J. Oper. Res., 125(2):283–291, 2000.doi:10.1016/S0377-2217(99) 00459-2. [GKYY25] Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, and Wuwei Yuan. A simple and fast reduction f...

work page doi:10.1016/s0377-2217(99 2000

[11] [11]

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Accepted to SODA 2026.arXiv:2509.02520,doi:10.48550/ARXIV.2509.02520. [GMT20] Ajinkya Gaikwad, Soumen Maity, and Shuvam Kant Tripathi. The satisfactory partition problem.CoRR, abs/2007.14339,

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2509.02520 2026

[12] [12]

[GNT20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup

URL:https://arxiv.org/abs/2007.14339,arXiv: 2007.14339. [GNT20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connec- tivity via random 2-out contractions. InProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1260–1279. SIAM,

work page arXiv 2007

[13] [13]

Matthew Weinberg

[GPRW20] Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg. New query lower bounds for submodular function minimization. In11th Innovations in Theoretical Computer Science Conference, ITCS 2020, volume 151 ofLIPIcs, pages 64:1–64:16. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2020.doi:10.4230/LIPICS.ITCS.2020.64. 24 [GRST2...

work page doi:10.4230/lipics.itcs.2020.64 2020

[14] [14]

[HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup

doi:10.1137/1.9781611976465.132. [HdLT01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, 2001.doi:10.1145/502090.502095. [HK99] Monika Rauch Henzinger and Valerie King. Randomized fully dynamic graph ...

work page doi:10.1137/1.9781611976465.132 2001

[15] [15]

[HRW20] Monika Henzinger, Satish Rao, and Di Wang

URL:http://dl.acm.org/citation.cfm?id=1283383.1283398. [HRW20] Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connec- tivity.SIAM J. Comput., 49(1):1–36, 2020.doi:10.1137/18M1180335. [Iva25] Paata Ivanisvili. A local sufficient condition for the superadditivity that is strictly more general than the convexity. MathOverflow,

work page doi:10.1137/18m1180335 2020

[16] [16]

[JNS25] Yonggang Jiang, Danupon Nanongkai, and Pachara Sawettamalya

URL:https://mathoverflow.net/q/490528 (version: 2025-04-04), AUTHOR PROFILE:https://mathoverflow.net/users/50901/paata-ivanisvili. [JNS25] Yonggang Jiang, Danupon Nanongkai, and Pachara Sawettamalya. Minimums–tcuts with fewer cut queries.CoRR, abs/2510.18274,

work page arXiv 2025

[17] [17]

Severson, Przemyslaw Uznanski, and Grzegorz Stachowiak

URL:https: //arxiv.org/abs/2510.18274,arXiv:2510.18274. [JS21] Wenyu Jin and Xiaorui Sun. Fully dynamics−tedge connectivity in subpolynomial time. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 861–872. IEEE, 2021.doi:10.1109/FOCS52979.2021.00088. [JST24] Wenyu Jin, Xiaorui Sun, and Mikkel Thorup. Fully dynamic min-cut o...

work page doi:10.1109/focs52979.2021.00088 2021

[18] [18]

[KK25a] Yotam Kenneth-Mordoch and Robert Krauthgamer

URL:https://arxiv.org/abs/2112.06916,arXiv:2112.06916. [KK25a] Yotam Kenneth-Mordoch and Robert Krauthgamer. All-pairs minimum cut using ˜O(n7/4) cut queries.CoRR, abs/2510.16741,

work page arXiv

[19] [19]

23 Sergey Goncharov, Stefan Milius, Lutz Schröder, Stelios Tsampas, and Henning Urbat

URL:https://arxiv.org/ abs/2510.16741,arXiv:2510.16741. [KK25b] Yotam Kenneth-Mordoch and Robert Krauthgamer. Cut-query algorithms with few rounds. In33rd Annual European Symposium on Algorithms, ESA 2025, volume 351 ofLIPIcs, pages 100:1–100:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2025.doi:10.4230/LIPICS. ESA.2025.100. [KK25c] Yotam Kenn...

work page doi:10.4230/lipics 2025

[20] [20]

01567,arXiv:2106.01567

URL:https://arxiv.org/abs/2106. 01567,arXiv:2106.01567. [MN20] Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: sequential, cut-query, and streaming algorithms. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 496–509. ACM, 2020.doi:10.1145/3357713.3384334. [MN21] Sagnik Mukhopadhyay and Danupon Na...

work page doi:10.1145/3357713.3384334 2020

[21] [21]

[PRW24] Orestis Plevrakis, Seyoon Ragavan, and S

doi:10.1007/BF01758778. [PRW24] Orestis Plevrakis, Seyoon Ragavan, and S. Matthew Weinberg. On the cut-query complexity of approximating max-cut. In51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, volume 297 ofLIPIcs, pages 115:1–115:20. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024.doi:10.4230/LIPICS.ICALP.20...

work page doi:10.1007/bf01758778 2024