pith. sign in

arxiv: 2509.02520 · v2 · submitted 2025-09-02 · 💻 cs.DS

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

Maximilian Probst Gutenberg , Rasmus Kyng , Weixuan Yuan , Wuwei Yuan This is my paper

Pith reviewed 2026-05-18 19:40 UTC · model grok-4.3

classification 💻 cs.DS
keywords Gomory-Hu treesmax-flowgraph algorithmsreductionsmin-cutshypergraphs
0
0 comments X

The pith

A simple reduction computes Gomory-Hu trees from polylog many max-flow calls on auxiliary graphs of total near-linear size.

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

The paper gives a direct reduction that turns the construction of a Gomory-Hu tree, a structure that records every pairwise min-cut in an undirected graph, into a short sequence of ordinary max-flow problems. On unweighted graphs the auxiliary instances together have size roughly linear in the number of edges, and the overhead outside the max-flow calls is also nearly linear. The same construction extends to weighted graphs at quadratic cost and to hypergraphs while remaining tight up to polylog factors. A reader cares because max-flow is a well-studied primitive and any problem reducible to a few calls on small instances immediately inherits its speed.

Core claim

We present a simple, efficient reduction from Gomory-Hu trees to polylog maxflow computations. On unweighted graphs, our reduction reduces to maxflow computations on graphs of total instance size Õ(m) and the algorithm requires only Õ(m) additional time. Our reduction is the first that is tight up to polylog factors. The reduction also seamlessly extends to weighted graphs, however, instance sizes and runtime increase to Õ(n²). Finally, we show how to extend our reduction to reduce Gomory-Hu trees for unweighted hypergraphs to maxflow in hypergraphs.

What carries the argument

A sequence of auxiliary graphs constructed so that max-flow values on them can be combined to decide the parent and cut values in the Gomory-Hu tree while preserving all original min-cuts.

If this is right

  • Gomory-Hu tree computation on unweighted graphs becomes equivalent in complexity to polylog max-flow calls plus linear work.
  • The same reduction works on weighted graphs, paying an Õ(n²) size overhead.
  • Gomory-Hu trees on unweighted hypergraphs reduce to hypergraph max-flow with the same near-linear total size guarantee.

Where Pith is reading between the lines

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

  • Any future improvement to max-flow that runs in near-linear time would immediately yield a near-linear Gomory-Hu tree algorithm for unweighted graphs.
  • The construction may suggest similar reductions for other global cut structures such as cut trees or cactus representations.
  • Practical implementations could test the reduction on large sparse graphs to measure how the polylog factor behaves in practice.

Load-bearing premise

Max-flow algorithms run on the auxiliary graphs must return cut values and partitions that match the cuts they would have produced inside the original graph.

What would settle it

An explicit graph and a run of the reduction that outputs a tree failing to preserve at least one min-cut present in the input.

Figures

Figures reproduced from arXiv: 2509.02520 by Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, Wuwei Yuan.

Figure 1
Figure 1. Figure 1: Illustration of Algorithm 1. We exploit a simple, but powerful fact: for any τ -CC C and Gomory-Hu tree T on G, we have that T[C] is still spanning C. The same is true for the set UC = C ∩ U, i.e. any Gomory-Hu U-Steiner tree TU has TU [UC] spanning UC. We can thus hope to compute a Gomory-Hu tree on the terminals of C and then ‘attach’ the missing subtrees over terminals in V \ C, i.e. the terminals UV \C… view at source ↗
read the original abstract

Given an undirected graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree on $V$ that preserves all-pairs mincuts of $G$ exactly. We present a simple, efficient reduction from Gomory-Hu trees to polylog maxflow computations. On unweighted graphs, our reduction reduces to maxflow computations on graphs of total instance size $\tilde{O}(m)$ and the algorithm requires only $\tilde{O}(m)$ additional time. Our reduction is the first that is tight up to polylog factors. The reduction also seamlessly extends to weighted graphs, however, instance sizes and runtime increase to $\tilde{O}(n^2)$. Finally, we show how to extend our reduction to reduce Gomory-Hu trees for unweighted hypergraphs to maxflow in hypergraphs. Again, our reduction is the first that is tight up to polylog factors.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript presents a reduction that constructs a Gomory-Hu tree for an undirected graph G by performing a polylogarithmic number of max-flow computations on a sequence of auxiliary graphs. For unweighted graphs the total size of the auxiliary instances is Õ(m) and the reduction uses only Õ(m) additional time outside the max-flow calls; the authors claim the reduction is the first to be tight up to polylog factors. The same framework is extended to weighted graphs (with Õ(n²) total size) and to unweighted hypergraphs (again tight up to polylog factors).

Significance. If the cut-preservation argument holds, the result would be a notable algorithmic contribution: it reduces Gomory-Hu tree construction to essentially the cost of a polylog number of max-flow instances whose aggregate size matches the input size up to polylog factors. This is the first such tight reduction and would immediately improve the complexity of any algorithm that relies on all-pairs min-cuts, while remaining simple enough to be of practical interest once fast max-flow implementations are available.

major comments (2)
  1. §3 (Unweighted reduction): The central correctness claim is that each auxiliary graph preserves the exact min-cut values between the relevant vertex pairs of the original graph G. The manuscript treats the max-flow routine as a black-box oracle; however, the construction (vertex/edge additions and capacity assignments) must be shown to introduce neither spurious min-cuts nor capacity alterations that depend on the internal behavior of the oracle. A formal invariant or lemma establishing one-to-one correspondence between min-cuts of the auxiliary graph and the relevant cuts of G is required; without it the reduction’s validity for both the unweighted Õ(m) and weighted Õ(n²) regimes remains unverified.
  2. §4 (Hypergraph extension): The same cut-preservation issue arises when the reduction is lifted to hypergraphs. The manuscript should explicitly state how the auxiliary hypergraph construction maintains exact min-cut equivalence and whether the polylog bound on the number of max-flow calls continues to hold under the hypergraph max-flow primitive.
minor comments (2)
  1. The notation Õ(m) and Õ(n²) should be accompanied by an explicit statement of the hidden polylog factors (base of the logarithm, dependence on n or m) so that tightness claims can be compared directly with prior work.
  2. A short table summarizing the size and number of max-flow calls for the unweighted, weighted, and hypergraph cases would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive overall assessment, and constructive suggestions for strengthening the formal presentation of our reduction. We agree that a more explicit lemma on cut preservation will improve clarity and verifiability. Below we respond point-by-point to the major comments and outline the revisions we will make.

read point-by-point responses

  1. Referee: §3 (Unweighted reduction): The central correctness claim is that each auxiliary graph preserves the exact min-cut values between the relevant vertex pairs of the original graph G. The manuscript treats the max-flow routine as a black-box oracle; however, the construction (vertex/edge additions and capacity assignments) must be shown to introduce neither spurious min-cuts nor capacity alterations that depend on the internal behavior of the oracle. A formal invariant or lemma establishing one-to-one correspondence between min-cuts of the auxiliary graph and the relevant cuts of G is required; without it the reduction’s validity for both the unweighted Õ(m) and weighted Õ(n²) regimes remains unverified.

    Authors: We thank the referee for highlighting this point. The manuscript contains an informal argument that the auxiliary graphs preserve min-cuts (by setting capacities of added edges to infinity for contracted supernodes and using the original capacities otherwise), but we agree that an explicit invariant or lemma would make the one-to-one correspondence rigorous and independent of any internal details of the max-flow oracle. In the revision we will insert a new Lemma 3.1 stating that, for every auxiliary graph G' constructed during the reduction, (i) every min-cut in G' between two terminals corresponds exactly to a min-cut in the original G between the underlying vertex sets, and (ii) no spurious finite-capacity cuts are created because all auxiliary edges have capacities either equal to the original edge capacities or set to infinity (preventing cuts that cross the auxiliary structure). The proof proceeds by induction on the recursion depth of the Gomory-Hu construction and relies solely on the correctness of the returned max-flow value, treating the oracle as a black box. The same lemma will cover the weighted Õ(n²) regime, where the construction is identical except for the initial instance size. revision: yes

  2. Referee: §4 (Hypergraph extension): The same cut-preservation issue arises when the reduction is lifted to hypergraphs. The manuscript should explicitly state how the auxiliary hypergraph construction maintains exact min-cut equivalence and whether the polylog bound on the number of max-flow calls continues to hold under the hypergraph max-flow primitive.

    Authors: We agree that the hypergraph case requires an explicit statement. In the revised manuscript we will add a dedicated subsection (or Lemma 4.1) showing that the auxiliary hypergraph is obtained by replacing each original hyperedge with a star gadget whose capacities are set identically to the original hyperedge weight; this gadget ensures that any min-cut in the auxiliary hypergraph corresponds exactly to a min-cut in the original hypergraph (no new finite cuts are introduced across gadget edges). Because the reduction algorithm itself is unchanged—only the underlying max-flow primitive is replaced by a hypergraph max-flow routine—the number of calls remains O(log² n) and the total size of auxiliary instances stays Õ(m) for unweighted hypergraphs. The polylog bound is therefore independent of the concrete implementation of the hypergraph max-flow oracle, provided the oracle returns exact min-cut values. revision: yes

Circularity Check

0 steps flagged

Reduction to external max-flow primitive is self-contained with no circularity

full rationale

The paper defines a reduction that transforms Gomory-Hu tree construction into a sequence of polylog many max-flow calls on explicitly constructed auxiliary graphs whose total size is Õ(m) for unweighted inputs. The abstract and provided text treat the max-flow routine as a black-box external primitive whose correctness and complexity are taken as given; no equation or step equates the final tree back to fitted parameters, self-referential quantities, or a self-citation chain. The cited Gomory-Hu 1961 result is an external historical definition, not a load-bearing self-citation. This matches the default expectation of a non-circular algorithmic reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard properties of min-cuts and max-flows in undirected graphs together with the existence of a black-box max-flow algorithm; no new entities or fitted parameters are introduced in the abstract.

axioms (2)
  • standard math Min-cut values between all pairs of vertices are preserved exactly by a Gomory-Hu tree.
    This is the defining property of a Gomory-Hu tree as stated in the abstract and is a standard fact from the 1961 reference.
  • domain assumption Max-flow computations can be performed on auxiliary graphs constructed from the original graph.
    The reduction treats max-flow as an oracle on modified instances whose total size is bounded by Õ(m).

pith-pipeline@v0.9.0 · 5713 in / 1440 out tokens · 40288 ms · 2026-05-18T19:40:29.518281+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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

    cs.DS 2025-11 conditional novelty 8.0

    A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [1]

    Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time

    Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi. Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in nearly quadratic time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 884--895. IEEE, 2022

    work page 2022

  2. [2]

    Deterministic almost-linear-time gomory-hu trees

    Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst, Thatchaphol Saranurak, Weixuan Yuan, and Wuwei Yuan. Deterministic almost-linear-time gomory-hu trees. In Accepted to 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS) , 2025

    work page 2025

  3. [3]

    APMF apsp? gomory-hu tree for unweighted graphs in almost-quadratic time

    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. APMF apsp? gomory-hu tree for unweighted graphs in almost-quadratic time. In Foundations of Computer Science (FOCS), 2021 IEEE 62nd Annual Symposium on , 2021

    work page 2021

  4. [4]

    Subcubic algorithms for gomory-hu tree in unweighted graphs

    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Subcubic algorithms for gomory-hu tree in unweighted graphs. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pages 1725--1737. ACM , 2021

    work page 2021

  5. [5]

    Friendly cut sparsifiers and faster gomory-hu trees

    Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Friendly cut sparsifiers and faster gomory-hu trees. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022 , pages 3630--3649. SIAM , 2022

    work page 2022

  6. [6]

    All-pairs max-flow is no harder than single-pair max-flow: Gomory-hu trees in almost-linear time

    Amir Abboud, Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. All-pairs max-flow is no harder than single-pair max-flow: Gomory-hu trees in almost-linear time. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2204--2212. IEEE, 2023

    work page 2023

  7. [7]

    Ahuja, T.L

    R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows . Prentice Hall, 1993

    work page 1993

  8. [8]

    Cook, W.H

    W.J. Cook, W.H. Cunningham, W.R Pulleybank, and A. Schrijver. Combinatorial Optimization . Wiley, 1997

    work page 1997

  9. [9]

    Maximum flow and minimum-cost flow in almost-linear time

    Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) , pages 612--623. IEEE, 2022

    work page 2022

  10. [10]

    Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, s - t shortest path, and minimum-cost flow

    Li Chen, Rasmus Kyng, Yang P Liu, Simon Meierhans, and Maximilian Probst Gutenberg. Almost-linear time algorithms for incremental graphs: Cycle detection, sccs, s - t shortest path, and minimum-cost flow. STOC'24 , 2024

    work page 2024

  11. [11]

    Isolating cuts,(bi-) submodularity, and faster algorithms for connectivity

    Chandra Chekuri and Kent Quanrud. Isolating cuts,(bi-) submodularity, and faster algorithms for connectivity. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , 2021

    work page 2021

  12. [12]

    Multi-terminal network flows

    Ralph E Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics , 9(4):551--570, 1961

    work page 1961

  13. [13]

    Deterministic min-cut in poly-logarithmic max-flows

    Jason Li and Debmalya Panigrahi. Deterministic min-cut in poly-logarithmic max-flows. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 85--92. IEEE, 2020

    work page 2020

  14. [14]

    Approximate gomory--hu tree is faster than n--1 max-flows

    Jason Li and Debmalya Panigrahi. Approximate gomory--hu tree is faster than n--1 max-flows. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1738--1748, 2021

    work page 2021

  15. [15]

    A nearly optimal all-pairs min-cuts algorithm in simple graphs

    Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. A nearly optimal all-pairs min-cuts algorithm in simple graphs. In Foundations of Computer Science (FOCS), 2021 IEEE 62nd Annual Symposium on , 2021

    work page 2021

  16. [16]

    A note on isolating cut lemma for submodular function minimization

    Sagnik Mukhopadhyay and Danupon Nanongkai. A note on isolating cut lemma for submodular function minimization. arXiv preprint arXiv:2103.15724 , 2021

    work page arXiv 2021

  17. [17]

    Schrijver

    A. Schrijver. Combinatorial Optimization . Springer, 2003

    work page 2003

  18. [18]

    Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality

    Jan van den Brand, Li Chen, Rasmus Kyng, Yang P Liu, Simon Meierhans, Maximilian Probst Gutenberg, and Sushant Sachdeva. Almost-linear time algorithms for decremental graphs: Min-cost flow and more via duality. to appear at FOCS'24 , 2024

    work page 2024

  19. [19]

    A deterministic almost-linear time algorithm for minimum-cost flow

    Jan Van Den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 503--514. IEEE, 2023

    work page 2023

  20. [20]

    Gomory-hu trees in quadratic time

    Tianyi Zhang. Gomory-hu trees in quadratic time. arXiv preprint arXiv:2112.01042 , 2021

    work page arXiv 2021