Pith. sign in

REVIEW 5 minor 17 references

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut

T0 review · 0 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes a randomized algorithm that computes a global minimum vertex-cut in an undirected vertex-weighted graph in time O(min{m^{3/2+o(1)}, m n^{0.99+o(1)}} (log W)^{O(1)}), succeeding with probability at least 1-1/n.

desk verdict Genuine 28-year barrier break for weighted vertex-cut; proof coherent as far as verifiable, but load-bearing on almost-linear max-flow and with truncated sections. read the letter →

arxiv 2506.11926 v2 pith:CVQ6RFZN submitted 2025-06-13 cs.DS

Julia Chuzhoy , Ohad Trabelsi This is my paper · ORCID
classification cs.DS MSC 68W2068R1005C40
keywords globalminimumvertexcutvertex-weightedgraphsrandomizedalgorithmsmaximumflowsplitgraphlocalaugmentationsubgraphoracleconnectivity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims that global minimum vertex-cut in an undirected graph with integer vertex weights can be computed by a randomized algorithm in time O(min{$m^{{3/2+o(1)}}$, m $n^{{0.99+o(1)}}$} (log W)^{O(1)}), succeeding with probability at least 1-1/n. That breaks the O~(mn) bound, roughly mn up to logarithmic factors, that had stood for 28 years for the weighted problem. The result matters because vertex cuts are the capacitated version of vertex-connectivity, and they had resisted the techniques that made edge-cut problems almost linear-time. The paper's strategy is to sample a small set of terminals that, with polynomial probability, captures the two sides of an optimal cut, then compute isolating cuts and a sequence of local flow augmentations with carefully validated shortcut edges. A reader should care because this supplies the first strongly subquadratic dense-graph algorithm for a basic optimization problem that was previously stuck at mn.

What carries the argument

The load-bearing object is the split graph, which replaces each vertex v by a directed edge (v_in, v_out) of capacity w(v); naively, cuts in this split graph do not correspond to vertex cuts, so the paper adds a destination t and uses shortcut edges (u_out, t) that are only valid when u provably lies outside the small side L of the optimum. Over phases, the algorithm maintains an M-integral flow in this graph, augments it by local flows discovered in a sparse exploration of the residual network, and then sparsifies using a partition of the heavy vertices and a near-minimum cut in the residual graph. The subgraph oracle, which answers many approximate neighbor-count queries at once by listing triangles, keeps each phase below $n^{{2-4/45+o(1)}}$ time.

What would settle it

Run the algorithm with enough independent repetitions to exhaust the promised 1/n failure probability on a dense graph with a planted minimum vertex cut of known weight; if any returned cut has weight strictly above the planted optimum, or if the measured time on graphs with m near $n^{2}$ grows faster than $n^{{3+o(1)}}$, the central claim is false.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes Theorem 1.1: for every simple undirected n-vertex m-edge graph with integral vertex weights bounded by W, there is a randomized algorithm that returns a global minimum vertex-cut with probability at least 1-1/n in the stated running time. The proof fixes an optimal cut (L,S,R) with w(L) at most w(R) and splits into regimes by edge density and cut structure. For non-dense graphs, terminal sampling plus isolating cuts or simple degree-based selection suffices; for dense graphs, the hard case has the small side L containing at most about $n^{{1/45}}$ vertices, and the algorithm processes a sampled terminal set through a phased routine that maintains an s-to-t flow, adds shortcut edges only when they cannot change the optimum, and sparsifies the residual network until a final max-flow computation on the support of the flow yields the exact cut value.

Load-bearing premise

The paper assumes, without re-deriving it, that the recent almost-linear-time minimum-cost maximum-flow algorithm is correct, always returns an integral flow, and runs in the advertised time; if that black-box routine fails in any of these ways, the main theorem has no proof.

Editorial extensions

If this is right

  • For graphs with m=O(n) edges, the running time becomes n^{1.5+o(1)}, giving the first strongly subquadratic o(n^2) algorithm for weighted vertex cuts in sparse graphs.
  • For dense graphs with m near n^2, the m n^{0.99} bound gives n^{2.99+o(1)} time, below the previous O~(n^3).
  • Because the running time depends only polylogarithmically on the maximum weight W, the algorithm remains fast even when vertex weights are exponentially large.
  • The returned cut value is always a valid upper bound on the optimum, and it equals OPT with high probability, so the routine can also serve as a fast exact checker inside larger optimization loops.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The validity criterion for shortcut edges, connecting only out-copies that provably lie outside the small side of the optimum, looks transplantable to other vertex-capacitated cut problems where the classic split-graph reduction fails, such as vertex sparsest cut.
  • The m^{3/2+o(1)} bound is likely not the end of the line; the same phase-and-sparsify structure may be iterated further, and the tradeoff shape of the two bounds suggests room to push toward m^{4/3+o(1)} or beyond.
  • The bulk subgraph oracle, implemented through triangle listing, is a general design pattern: when a loop needs many approximate degree-count queries, answer them all at once rather than one by one, and this may accelerate other iterative graph algorithms.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper presents a randomized algorithm for the vertex-weighted global minimum vertex-cut problem, running in O(min{m^{3/2+o(1)}, m n^{0.99+o(1)}} (log W)^{O(1)}) time. The algorithm is built from three regimes: Alg 1 uses weighted isolating cuts after subsampling one weight class; Alg 2 handles large |S| in non-dense graphs by sampling a destination vertex with probability proportional to its weight; Alg 3 handles dense graphs with small |L| via split graphs, good terminal pairs, local flow augmentations, min-cost-flow-based bad-batch detection, and a triangle-listing subgraph oracle. Theorem 1.1 is assembled from these pieces with repetition and union bounds. The proof is organized theorem-by-theorem; the core Sections 3 through 6 are detailed and internally consistent on the parts I could check. The copy provided to me truncates the latter part of Section 6 and all of Section 7.

Significance. If correct, this breaks the 28-year-old O(mn) barrier for the general weighted vertex-cut problem, extending the recent almost-linear unweighted result to the weighted setting. The main contribution is constructive and does not rely on fitted parameters or circular derivations; the weighted local-flow augmentation and the bulk subgraph oracle via triangle listing are likely to be reusable. The strongest external dependency is the deterministic almost-linear minimum-cost maximum-flow algorithm of van den Brand et al. and Chen et al., used as a black box; the paper does not rederive it, but this is a standard published result rather than an internal weakness. The paper provides detailed theorem-by-theorem proofs and a clear high-level map of the algorithm. I did not find a load-bearing technical error in the sections I could verify.

minor comments (5)
  1. [§7 (and end of §6)] The supplied text truncates after Claim 6.10, so I could not independently verify the Step 3 sparsification and the proof that Invariants I3--I5 close at the end of each phase. This is a completeness caveat of the review copy rather than a demonstrated error; the final manuscript should ensure that the Step 3 proof, including the construction and properties of H', is complete and self-contained.
  2. [Theorems 3.1 and 3.5] The stated failure probability of 1 - 1/n^4 appears to require absorbing a union bound over O(log W' log n) applications of the inner lemmas; the constants as written are slightly optimistic. This is easily fixed by increasing the repetition factor by a poly-logarithmic factor and does not affect the running-time exponent.
  3. [Observation 3.4] In the displayed sum in the proof, the notation 'Pr[E_i]' should be 'Pr[E(v)]'; the surrounding text defines the events E(v), not E_i.
  4. [Figure 3, Step 3b] The procedure says the Heavy Vertex algorithm returns 'τ+1 vertices', while Claim 2.15 returns τ vertices; the subsequent text uses only τ of them. The wording should be harmonized.
  5. [Section 2.4] The paper does not explicitly discuss disconnected input graphs, where the minimum vertex-cut has value 0 with S = ∅. The algorithm appears to handle this case implicitly, but a one-sentence note in the preliminaries would remove ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivation is a constructive algorithm built on independent external flow and cut primitives.

full rationale

No circular step is present. The paper proves an algorithmic theorem, and every load-bearing reduction is by construction rather than by assuming its conclusion. Algorithm Alg1 samples a terminal set and invokes the isolating-cuts routine (Theorem 2.7, proved in Appendix A): the success event gives |T∩L_i|=1 and T∩S_i=∅, so the unique terminal in L is separated from T\{x}⊆R by the global cut (L,S,R), forcing the computed value to be OPT; this is a direct property of the definition of OPT, not a fitted or renamed target. Algorithm Alg2 proves L∩T≠∅ by an edge-counting argument and uses Claim 2.2, proved independently, to show that a random vertex y lies in R with constant probability; no parameter is fitted to the output. Algorithm Alg3's good-pair definition implies T_x⊆R and therefore the minimum x-T_x cut equals OPT whenever the pair is good; the long phase analysis maintains invariants I1-I5 whose purpose is to show that the flow value computed is at least OPT_s, and at most OPT_s under the good-pair event. The main external dependencies are the almost-linear minimum-cost maximum-flow algorithm (Theorem 2.4, citing [vdBCP+23] and [CKL+22]) and the triangle-listing bound of [BPWZ14]; these are independent prior results, not self-citations, and the paper does not reduce its target theorem to a subsequent unverified claim by the same authors. The supplied text is truncated inside Section 7, so the full per-phase sparsification and invariant I3 cannot be machine-checked from the available passage; that is a completeness limitation, not circular reasoning. No instance was found of a definition that encodes the conclusion, a fitted quantity renamed as a prediction, or a load-bearing uniqueness theorem imported from the authors' own prior work.

Assumptions & free parameters 3 free parameters · 3 assumptions · 0 invented entities

There are no empirical free parameters; the listed parameters are algorithmic constants chosen to make the proof work. The main external assumptions are the recent max-flow algorithm and matrix-multiplication bounds. No new physical or mathematical entities are introduced; the subgraph oracle, shortcut operations, and local flow augmentations are algorithmic tools, not invented entities.

free parameters (3)
  • epsilon = 1/45 (and 1/100 in the non-dense case)
    Chosen to balance running times between sparse and dense cases; the choice implies delta = 4*epsilon = 4/45 and gamma approximately n^{7/9}.
  • gamma = smallest power of 2 at least n^{7/9}
    Determines the scaling of Mi phases and ensures inequalities n^{14*epsilon} <= gamma <= 2 n^{1-10*epsilon}.
  • delta = 4/45 - log(4000 log n)/log n = 4/45 - o(1)
    Parameter for the subgraph oracle; set so that n^delta = n^{4*epsilon}/(4000 log n).
assumptions (3)
  • domain assumption Almost-linear deterministic min-cost max-flow algorithm (Theorem 2.4 from van den Brand et al. 2023 and Chen et al. 2022)
    The paper uses this as a black box for all flow computations (Section 2.5). Its correctness and running time are assumed.
  • standard math Max-Flow/Min-Cut theorem
    Used throughout to equate min cuts with max flows, e.g., at the start of Section 4.
  • domain assumption Current matrix multiplication exponent omega <= 2.371552
    Used in Lemma 3.17 to bound the triangle-listing based subgraph oracle running time.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut." pith.science (2026). https://pith.science/paper/CVQ6RFZN

@misc{pith2026250611926,
  author       = {Pith},
  title        = {Pith review of: Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CVQ6RFZN}},
  note         = {Machine review of arXiv:2506.11926}
}
abstract

We consider the Global Minimum Vertex-Cut problem: given an undirected vertex-weighted graph $G$, compute a minimum-weight subset of its vertices whose removal disconnects $G$. The problem is closely related to Global Minimum Edge-Cut, where the weights are on the graph edges instead of vertices, and the goal is to compute a minimum-weight subset of edges whose removal disconnects the graph. Global Minimum Cut is one of the most basic and extensively studied problems in combinatorial optimization and graph theory. While an almost-linear time algorithm was known for the edge version of the problem for awhile (Karger, STOC 1996 and J. ACM 2000), the fastest previous algorithm for the vertex version (Henzinger, Rao and Gabow, FOCS 1996 and J. Algorithms 2000) achieves a running time of $\tilde{O}(mn)$, where $m$ and $n$ denote the number of edges and vertices in the input graph, respectively. For the special case of unit vertex weights, this bound was broken only recently (Li {et al.}, STOC 2021); their result, combined with the recent breakthrough almost-linear time algorithm for Maximum $s$-$t$ Flow (Chen {et al.}, FOCS 2022, van den Brand {et al.}, FOCS 2023), yields an almost-linear time algorithm for Global Minimum Vertex-Cut with unit vertex weights. In this paper we break the $28$ years old bound of Henzinger {et al.} for the general weighted Global Minimum Vertex-Cut, by providing a randomized algorithm for the problem with running time $O(\min\{mn^{0.99+o(1)},m^{1.5+o(1)}\})$.

Figures

Figures reproduced from arXiv: 2506.11926 by the authors.

Figure 1
Figure 1. An illustration of the classic split-graph reduction from undirected vertex-weighted graphs [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The local transformation for vertex v for computing the split graph. Observe that, for every pair s, t ∈ V (G) of vertices, the value of minimum s-t vertex-cut in G is equal to the value of the minimum s out–t in edge-cut in G′ , which, in turn, is equal to the value of the maximum s out–t in flow in G′ from the Max-Flow/Min-Cut theorem. In particular, the value of the global minimum vertex-cut in G is equal to maxi… view at source ↗
Figure 3
Figure 3. Procedure Explore H′ 45 [PITH_FULL_IMAGE:figures/full_fig_p048_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: A schematic view of graph Z. Let Z be the graph obtained from H˜ ′′ by adding a single destination vertex t, and adding an edge (t1, t) of capacity F ∗−r, and an edge (t2, t) of capacity F ′−F ∗+r (see [PITH_FULL_IMAGE:figures/full_fig_p070_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 12 canonical work pages

  1. [2]

    Available from:https://arxiv.org/abs/2406. 03648. [BDD+82] M. Becker, W. Degenhardt, J. Doenhardt, S. Hertel, G. Kaninke, W. Kerber, K. Mehlhorn, S. N¨ aher, H. Rohnert, and T. Winter. A probabilistic algorithm for ver- tex connectivity of graphs.Inf. Process. Lett., 15(3):135–136, 1982.doi:10.1016/ 0020-0190(82)90046-1. [BPWZ14] A. Bj¨ orklund, R. Pagh, ...

    work page 1982

  2. [14]

    [Kle69] D

    Announced at STOC 1996.doi:10.1145/331605.331608. [Kle69] D. J. Kleitman. Methods for investigating connectivity of large graphs.IEEE Transac- tions on Circuit Theory, 16(2):232–233, 1969.doi:10.1109/TCT.1969.1082941. [KP15] D. Kang and J. Payor. Flow rounding.CoRR,

    work page arXiv 1996

  3. [126]

    [FPZ23] K. Fox, D. Panigrahi, and F. Zhang. Minimum cut and minimumk-cut in hypergraphs via branching contractions.ACM Trans. Algorithms, 19(2):13:1–13:22, 2023.doi:10. 1145/3570162. [Gab95] H. N. Gabow. A matroid approach to finding edge connectivity and packing arbores- cences.J. Comput. Syst. Sci., 50(2):259–273,

    work page 2023

  4. [1927]

    [MN21] S

    Available from:http://eudml.org/doc/211191. [MN21] S. Mukhopadhyay and D. Nanongkai. A note on isolating cut lemma for submodular function minimization.arXiv preprint arXiv:2103.15724,

    arXiv

  5. [1956]

    [FNY+20] S

    Available from:http://www.rand.org/pubs/ papers/P605/. [FNY+20] S. Forster, D. Nanongkai, L. Yang, T. Saranurak, and S. Yingchareonthawornchai. Com- puting and testing small connectivity in near-linear time and queries via fast local cut algorithms. In S. Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2020, pages ...

    doi:10.1137/1.9781611975994 2020

  6. [1973]

    [ST83] D

    Avail- able from:https://cir.nii.ac.jp/crid/1371694371159352077. [ST83] D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees.J. Comput. Syst. Sci., 26(3):362–391, 1983.doi:10.1016/0022-0000(83)90006-5. [SY22] T. Saranurak and S. Yingchareonthawornchai. Deterministic small vertex connectivity in almost linear time. In63rd IEEE Annual Symposiu...

    work page arXiv 1983

  7. [1990]

    [Kar00] D

    Available from: http://dl.acm.org/citation.cfm?id=320176.320227. [Kar00] D. R. Karger. Minimum cuts in near-linear time.J. ACM, 47(1):46–76,

    work page arXiv

  8. [1994]

    [HRG00] M

    Announced at SODA 1992.doi:10.1006/ JAGM.1994.1043. [HRG00] M. R. Henzinger, S. Rao, and H. N. Gabow. Computing vertex connectivity: New bounds from old techniques.J. Algorithms, 34(2):222–250,

    work page arXiv 1992

Show all 17 references
  1. [1995]

    [Gab06] H. N. Gabow. Using expander graphs to find vertex connectivity.J. ACM, 53(5):800–844, 2006.doi:10.1145/1183907.1183912. [GT88] A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem.J. ACM, 35(4):921–940, 1988.doi:10.1145/48014.61051. 87 [HHS24] Z....

    2006

  2. [2000]

    [HR W17] M

    Announced at FOCS 1996.doi:10.1006/JAGM.1999.1055. [HR W17] M. Henzinger, S. Rao, and D. Wang. Local flow partitioning for faster edge con- nectivity. In P. N. Klein, editor,Proceedings of the Twenty-Eighth Annual ACM- SIAM Symposium on Discrete Algorithms, SODA 2017, pages 19...

    1996

  3. [2009]

    [ET75] S

    Available from:http: //www.cambridge.org/gb/knowledge/isbn/item2327542/. [ET75] S. Even and R. E. Tarjan. Network flow and testing graph connectivity.SIAM J. Comput., 4(4):507–518, 1975.doi:10.1137/0204043. [Eve75] S. Even. An algorithm for determining whether the connectivity...

    1975 doi

  4. [2014]

    [CCPS21] R. Cen, Y. Cheng, D. Panigrahi, and K. Sun. Sparsification of Directed Graphs via Cut Balance. In48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198, pages 45:1–45:21, 2021.doi:10.4230/LIPIcs.ICALP.2021

    2021 doi

  5. [2015]

    org/pdf/1507.08139

    Available from:https://arxiv. org/pdf/1507.08139. [KS93] D. R. Karger and C. Stein. An ˜O(n2) algorithm for minimum cuts. In S. R. Kosaraju, D. S. Johnson, and A. Aggarwal, editors,Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pages 75...

    1993 arXiv

  6. [2016]

    [CKL+22] L

    Available from:http://arxiv.org/abs/1602.02629. [CKL+22] L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva. Max- imum flow and minimum-cost flow in almost-linear time. In2022 IEEE 63rd An- nual Symposium on Foundations of Computer Science (FOCS), pages 612–623,

    arXiv

  7. [2021]

    Nagamochi and T

    [NI92] H. Nagamochi and T. Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph.Algorithmica, 7(5&6):583–596, 1992.doi: 10.1007/BF01758778. [NSY19] D. Nanongkai, T. Saranurak, and S. Yingchareonthawornchai. Breaking quadrat...

    1992

  8. [2022]

    86 [CKT93] J

    doi:10.1109/FOCS54457.2022.00064. 86 [CKT93] J. Cheriyan, M. Kao, and R. Thurimella. Scan-first search and sparse certificates: An improved parallel algorithms for k-vertex connectivity.SIAM J. Comput., 22(1):157–174, 1993.doi:10.1137/0222013. [CLN+21] R. Cen, J. Li, D. Nanong...

    2022

  9. [2024]

    [AKT21a] A

    Available from:http: //arxiv.org/abs/2408.01798. [AKT21a] A. Abboud, R. Krauthgamer, and O. Trabelsi. APMF<APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, pages 1135–1146, 2021.doi...

    2021 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.