Gomory–Hu Tree

Gomory–Hu tree (also known as a cut tree or all-pairs minimum-cut tree) is a combinatorial data structure in computation and algorithms that represents the minimum s–t cut capacities and vertex partitions for all V(V − 1)/2 unordered pairs of vertices in an undirected, edge-capacitated graph G = (V, E, c) within a single weighted tree T on the same vertex set V. Introduced in 1961 by Ralph E. Gomory and Te Chiang Hu, the structure demonstrates that although an undirected network on V vertices possesses V(V − 1)/2 distinct pairwise minimum-cut problems, their optimal cut capacities can take on at most V − 1 distinct numerical values and can be computed using V − 1 invocations of a maximum-flow subroutine such as the Ford–Fulkerson algorithm, Dinic's algorithm, or the push–relabel algorithm.

Within computational complexity theory and combinatorial optimization, the Gomory–Hu tree forms a foundational bridge between network flow theory, submodular function minimization, and hierarchical clustering. Removing the minimum-weight edge along the unique path between any two vertices u and v in T bipartitions V into two connected components (S_u, S_v) that form a true minimum u–v cut in the original graph G, while the weight of that tree edge equals the minimum cut capacity λ_G(u, v).

Pairwise Minimum Cuts and Flow Equivalence

Let G = (V, E, c) be an undirected graph with vertex count n = |V| and non-negative edge capacities c : E → ℝ_≥0. For any nonempty proper subset S ⊂ V, the cut capacity c(δ(S)) is the sum of capacities of all edges in E having one endpoint in S and the other in V \ S:

For any distinct vertices s, t ∈ V, a minimum s–t cut is a subset S ⊂ V with s ∈ S and t ∉ S that minimizes c(δ(S)). Denote this optimal capacity by λ_G(s, t). By the max-flow min-cut theorem, λ_G(s, t) equals the maximum value of a feasible s–t flow in G.

A weighted tree T = (V, E_T, w) on the identical vertex set V (where E_T need not be a subset of E) is called flow-equivalent to G if, for every pair u, v ∈ V, the minimum edge weight along the unique path P_T(u, v) in T equals λ_G(u, v):

A Gomory–Hu tree satisfies both this flow-equivalence property and the cut-equivalence property: for every tree edge e = {x, y} ∈ E_T, deleting e from T splits V into two connected vertex subsets (A_e, V \ A_e) such that c(δ_G(A_e)) = w(e) = λ_G(x, y). Consequently, the bottleneck edge e* on P_T(u, v) directly yields the explicit vertex partition of a minimum u–v cut in G.

Submodularity and the Non-Crossing Cut Property

The existence of a Gomory–Hu tree rests on the symmetry and submodularity of the undirected cut function f(S) = c(δ(S)). For any two vertex subsets A, B ⊆ V, the cut capacity function satisfies the submodular inequality:

Furthermore, because G is undirected, c(δ(A)) = c(δ(V \ A)), implying the posi-modular (symmetric submodular) inequality:

Two cuts A and B are said to cross if all four regions A ∩ B, A \ B, B \ A, and V \ (A ∪ B) are nonempty. Using the submodular and posi-modular inequalities, Gomory and Hu proved the uncrossing lemma: if A is a minimum s–t cut in G and x, y ∈ A are two vertices on the same side of A, then there exists a minimum x–y cut B that does not cross A (meaning either B ⊂ A or A ⊂ B). Because no two cuts in a laminar (non-crossing) family of bipartitions of V intersect transversely, any maximal laminar family of non-trivial bipartitions on n vertices contains at most n − 1 cuts and corresponds bijectively to the edges of a tree on V.

Ultrametric Triangle Inequality

Pairwise minimum-cut capacities in an undirected graph obey the ultrametric inequality (dual to the triangle inequality): for any three distinct vertices u, v, w ∈ V,

In the resulting triple of values {λ_G(u, v), λ_G(v, w), λ_G(u, w)}, the two smallest values must be equal. This algebraic condition is necessary and sufficient for a symmetric matrix of pairwise capacities to be realizable by a flow-equivalent tree, and a maximum-weight spanning tree computed via a minimum spanning tree solver on the complete graph of pairwise min-cut values always yields a flow-equivalent tree (though not necessarily a cut-equivalent Gomory–Hu tree without laminar cut selection).

Classical Gomory–Hu Contraction Algorithm

The original 1961 algorithm by Gomory and Hu constructs T iteratively over n − 1 refinement steps while maintaining a partition tree T_k whose nodes are disjoint supernodes V₁, V₂, …, V_k partitioning V:

1. Initialization: Start with a single supernode V₁ = V and an edgeless tree T₁.
2. Supernode Selection: While any supernode V_i contains at least two original vertices (s, t ∈ V_i), select s and t.
3. Contracted Graph Construction: Form a contracted graph G′ from G by contracting every connected component of T_k \ {V_i} into a single representative vertex, while keeping all vertices inside V_i uncontracted.
4. Minimum Cut and Uncrossing Split: Compute a minimum s–t cut (A, B) of capacity λ in G′ using a maximum-flow algorithm. Split the supernode V_i into V_i,s = V_i ∩ A and V_i,t = V_i ∩ B, join them in T_k+1 by an edge of weight λ, and reconnect each previously incident tree edge of V_i to V_i,s if its component lay in A or to V_i,t if its component lay in B.

After n − 1 iterations, every supernode is a singleton vertex in V, and T_n is a valid Gomory–Hu tree.

Gusfield's Contraction-Free Algorithm

Implementing explicit graph contractions and dynamic adjacency updates at each of the n − 1 phases introduces substantial bookkeeping overhead. In 1990, Dan Gusfield published a simplified algorithm that constructs a Gomory–Hu tree using n − 1 minimum s–t cut calls directly on the unmodified original graph G:

1. Initialize a star tree T in which vertex 1 is connected to every vertex i ∈ {2, …, n} by a tentative edge of weight 0; maintain an array p[i] = 1 recording each vertex's current tree neighbor.
2. For s = 2 to n:
   • Let t = p[s]. Compute a minimum s–t cut (S, V \ S) of capacity λ in the original graph G, with s ∈ S and t ∈ V \ S.
   • Set the weight of the tree edge {s, t} to λ.
   • For every vertex v ∈ {s + 1, …, n} such that v ∈ S and p[v] = t, update p[v] ← s.
   • If the previous neighbor p[t] belongs to S, swap the tree attachment of the edge (t, p[t]) so that s connects to p[t] and p[s] ← p[t], p[t] ← s.

Gusfield's method requires only two arrays of length n alongside an off-the-shelf max-flow solver, achieving identical O(n · T_max-flow(n, m)) time complexity without dynamic graph restructuring.

Comparative Complexity Across All-Pairs Minimum-Cut Methods

In a 2022 breakthrough, Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, and Ohad Trabelsi broke the sixty-year n − 1 max-flow barrier by combining isolating-cut lemmas with almost-linear L₁ interior-point flow solvers, constructing a Gomory–Hu tree in weighted undirected graphs in O(n^2+o(1)) time.

1. Image Segmentation and Computer Vision: In graph-based Markov Random Field (MRF) and conditional random field segmentation, pixels or superpixels form vertices connected by similarity-weighted edges. Computing a Gomory–Hu tree enables interactive multi-scale foreground/background partitioning and hierarchical clustering without recomputing max-flow for each seed pair.
2. Telecommunications and Power Grid Survivability: Network architects evaluate vulnerability to multi-link failures by querying the Gomory–Hu tree (often augmented with a heavy–light decomposition or Tarjan's off-line lowest common ancestors algorithm for O(1) bottleneck queries) to identify pairs of substations or routers separated by low-capacity cuts.
3. Bioinformatics and Protein Interaction Networks: In systems biology, interactome graphs weight protein–protein edges by experimental confidence scores. Gomory–Hu cut trees partition dense protein complexes from sparse inter-module linkers and solve the minimum k-cut heuristic in metabolic pathway decomposition.

Does every directed graph possess a Gomory–Hu tree?

No. In a directed capacitated graph, the minimum s–t cut capacity λ(s, t) need not equal λ(t, s), and a V-vertex directed graph can exhibit up to Ω(V²) distinct pairwise minimum-cut values. However, symmetric submodular functions and Eulerian directed graphs retain specialized cut-tree representations.

What is the difference between a flow-equivalent tree and a Gomory–Hu tree?

A flow-equivalent tree guarantees only that the minimum edge weight on the tree path between u and v equals the numerical value λ_G(u, v). A Gomory–Hu tree additionally guarantees that removing that bottleneck tree edge partitions V into two connected components (S, V \ S) whose cut capacity in G actually equals λ_G(u, v).

1. Gomory, R. E., & Hu, T. C. (1961). "Multi-terminal network flows." Journal of the Society for Industrial and Applied Mathematics, 9(4), 551–570. https://doi.org/10.1137/0109047
2. Gusfield, D. (1990). "Very simple methods for all pairs network flow analysis." SIAM Journal on Computing, 19(1), 143–155. https://doi.org/10.1137/0219009
3. Goldberg, A. V., & Tsioutsiouliklis, K. (2001). "Cut tree algorithms: An experimental study." Journal of Algorithms, 38(1), 51–83. https://doi.org/10.1006/jagm.2000.1136
4. Abboud, A., Krauthgamer, R., Li, J., Panigrahi, D., Saranurak, T., & Trabelsi, O. (2022). "Breaking the cubic barrier for all-pairs max-flow: Gomory–Hu tree in nearly quadratic time." Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 884–895. https://doi.org/10.1109/FOCS54457.2022.00088