A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
Pith reviewed 2026-05-18 03:19 UTC · model grok-4.3
The pith
A randomized reduction computes Gomory-Hu trees using polylog many max-flow calls on nearly-linear total size for unweighted graphs.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Given an undirected graph G=(V,E,w), a Gomory-Hu tree T on vertex set V preserves all-pairs min-cut values of G exactly. The authors give a simple randomized reduction that builds such a tree from polylog many max-flow computations. On unweighted graphs the calls have total instance size Õ(m) and the procedure uses only Õ(m) additional time. The reduction is the first whose overhead is tight up to polylog factors. It extends directly to weighted graphs at Õ(n²) size and to unweighted hypergraphs by reducing to max-flow in hypergraphs.
What carries the argument
A randomized reduction that combines expander decompositions with polylogarithmic max-flow calls to assemble a tree preserving every min-cut value.
If this is right
- Any improvement in max-flow or expander decomposition time immediately yields a matching improvement for Gomory-Hu trees.
- All-pairs min-cut queries become reducible to black-box max-flow in the unweighted case with only polylog overhead.
- The same reduction pipeline applies to weighted graphs and to hypergraphs without changing the high-level structure.
- Algorithms that previously built Gomory-Hu trees from scratch can now delegate the core work to existing fast max-flow implementations.
Where Pith is reading between the lines
- If a nearly-linear-time max-flow algorithm appears, the reduction would immediately give nearly-linear-time Gomory-Hu trees on unweighted graphs.
- The expander-decomposition step may be reusable for simplifying reductions in other global cut problems such as multiway cuts.
- Practical implementations could become simpler by calling optimized max-flow libraries rather than coding custom cut routines.
Load-bearing premise
The reduction assumes that max-flow and expander decomposition can be treated as black-box oracles that run in nearly linear time on the graphs the reduction itself produces.
What would settle it
Construct a small unweighted graph, run the reduction, and verify whether the returned tree reports the exact min-cut value between every pair of vertices; any mismatch falsifies the preservation claim.
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 and efficient randomized 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.
Referee Report
Summary. The paper presents a randomized reduction that computes a Gomory-Hu tree for an undirected graph G=(V,E,w) by invoking a polylogarithmic number of max-flow computations. For unweighted graphs the total size of the generated max-flow instances is Õ(m) and the additional non-max-flow work is Õ(m); the reduction treats expander decomposition as a black box. The same framework extends to weighted graphs (with Õ(n²) total instance size) and to unweighted hypergraphs while preserving the tight-up-to-polylog guarantee.
Significance. If correct, the result supplies the first reduction from Gomory-Hu trees to max-flow whose size and time overhead is tight up to polylog factors, improving on earlier work that incurred larger blow-ups. The black-box use of nearly-linear-time max-flow and expander-decomposition primitives, the clean extension to hypergraphs, and the explicit size bounds constitute the main technical contributions.
major comments (1)
- [§3] §3, the main reduction: the claimed Õ(m) total instance size for unweighted graphs relies on the expander decomposition producing cuts whose total measure across all recursive calls sums to Õ(m). The manuscript should explicitly bound the number of recursive levels and the measure of the cut edges removed at each level to confirm that no hidden linear-factor blow-up occurs.
minor comments (2)
- [Title and §1] The title states 'Deterministic Reduction' while the abstract and §1 describe a randomized reduction that invokes randomized expander decomposition. This mismatch should be reconciled.
- [§5] The hypergraph extension in §5 is stated at a high level; a short paragraph clarifying how the hyperedge weights are handled inside the max-flow calls would improve readability.
Simulated Author's Rebuttal
We thank the referee for their careful reading, positive evaluation, and constructive suggestion for improving the clarity of our main reduction. We address the single major comment below and will revise the manuscript accordingly.
read point-by-point responses
-
Referee: [§3] §3, the main reduction: the claimed Õ(m) total instance size for unweighted graphs relies on the expander decomposition producing cuts whose total measure across all recursive calls sums to Õ(m). The manuscript should explicitly bound the number of recursive levels and the measure of the cut edges removed at each level to confirm that no hidden linear-factor blow-up occurs.
Authors: We agree that an explicit accounting of the recursion depth and the aggregate cut measure would make the Õ(m) size bound fully transparent. In the revised manuscript we will insert a short lemma (or dedicated paragraph) in Section 3 that (i) bounds the depth of the recursion by O(log n) using the standard guarantee that each expander decomposition step reduces the expansion parameter or component size by a constant factor, and (ii) shows that the total measure of all cut edges removed across every level and every recursive call is O(m log n). Because the Õ notation already absorbs polylogarithmic factors, this establishes that the sum of the sizes of all generated max-flow instances remains Õ(m) with no hidden linear blow-up. We thank the referee for highlighting this presentational gap. revision: yes
Circularity Check
No significant circularity in the reduction
full rationale
The paper frames its contribution as a black-box reduction from Gomory-Hu tree construction to a polylog number of max-flow and expander-decomposition calls whose total size is Õ(m) (unweighted case) plus Õ(m) additional work. No equations, fitted parameters, or self-citations are shown to define the output in terms of the input; the reduction is presented as invoking independent, externally assumed primitives for max-flow and expander decomposition. The derivation chain therefore remains self-contained against those external benchmarks and does not reduce to self-definition or renaming of known results.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Existence of nearly-linear-time max-flow and expander decomposition algorithms for undirected graphs
- standard math Standard properties of Gomory-Hu trees preserving all-pairs min-cuts exactly
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.