Gomory-Hu Tree, in depth: all-pairs minimum cuts from n-1 max-flows with Gusfield's algorithm

The problem and two facts that shrink it

Write λ(u, v) for the value of a minimum u-v cut, which by the max-flow min-cut theorem equals the maximum flow between u and v. Two facts make a compact representation possible.

First, the triangle property: for any three vertices, λ(u, w) ≥ min(λ(u, v), λ(v, w)). Proof: take a minimum u-w cut. Vertex v is on one side of it. If v is with w, the cut also separates u from v, so λ(u, v) is at most its value; if v is with u, it separates v from w. Either way one of the two right-hand terms is at most λ(u, w). Applied along a path, this says the cut between path ends is at least the weakest link.

Second, few distinct values: those n(n−1)/2 numbers take at most n−1 distinct values. That already suggests a tree, which has exactly n−1 edges.

A Gomory-Hu tree makes both facts concrete. It has two properties, and it is worth keeping them apart:

1. Flow equivalence: for every pair u, v, λ(u, v) is the minimum weight on the tree path from u to v.
2. Cut property: removing any tree edge splits the vertices into two sets, and that partition is a minimum cut in the original graph between the edge's two endpoints, with value equal to the edge weight.

A tree with only the first property is a flow-equivalent tree; it answers value queries but cannot hand you the cut itself. A Gomory-Hu tree has both, so a query can return the partition, not just its value.

Why cuts form a tree

Why should cuts arrange themselves into a tree at all? The engine is the uncrossing lemma. Cut capacity in an undirected graph is submodular: for any vertex sets A and B, cap(A) + cap(B) ≥ cap(A ∩ B) + cap(A ∪ B), and also ≥ cap(A − B) + cap(B − A). If two minimum cuts cross, one of these inequalities lets you replace one of them with a non-crossing cut of the same value. So you can always choose a family of minimum cuts that are pairwise non-crossing, and a non-crossing family of n−1 cuts is exactly a tree.

The original Gomory-Hu algorithm uses this directly: keep a tree of super-vertices, pick a super-vertex holding two original vertices s and t, contract the rest of the tree's components, cut s from t in the contracted graph, and split the super-vertex along that cut. Contraction keeps cuts non-crossing but means building a new graph each step.

Gusfield's algorithm

Gusfield's algorithm keeps the same n−1 max-flow calls and drops the contraction. Every flow runs on the original graph. It stores the tree as a parent array p and weights fl, with vertex 0 as the root and every other vertex initially pointing at it.

p[v] = 0 for all v;  fl[v] = 0
for s = 1 .. n-1:
    t = p[s]
    (f, X) = min cut between s and t in the ORIGINAL graph, X = side containing s
    fl[s] = f
    for every vertex i != s:                  # all i, not only i > s
        if i in X and p[i] == t: p[i] = s     # i hangs below s now
    if p[t] in X:                             # t's own parent is on s's side
        p[s] = p[t];  p[t] = s                # s moves between t and its parent
        fl[s] = fl[t];  fl[t] = f
tree edges: (v, p[v], fl[v]) for v = 1 .. n-1

Read each step as a story about one tree edge. Vertex s currently hangs from t. The min cut between them is the weight of the edge s-t. Any sibling i that ended up on s's side of that cut should hang from s instead, so it does. The last step handles the case where the cut also put t's parent on s's side: then s belongs between t and its parent, and the two weights swap. Leave that step out and the tree is still flow-equivalent (every pair value comes out right in randomised tests), but removing an edge no longer reliably gives a minimum cut. The sets X must be the full source side of a minimum cut, which after a max-flow is simply the set of vertices reachable from s in the residual graph.

Python implementation

Here is a complete Python version, with Edmonds-Karp as the max-flow so the whole file stays short. It returns the tree edges and answers a query by walking the tree.

from collections import deque

def min_cut(n, edges, s, t):
    """Max flow s->t on an undirected graph; returns (value, source-side flags)."""
    cap = [[0] * n for _ in range(n)]
    for u, v, w in edges:
        cap[u][v] += w          # undirected edge = capacity both ways
        cap[v][u] += w
    flow = 0
    while True:
        par = [-1] * n
        par[s] = s
        q = deque([s])
        while q and par[t] == -1:
            u = q.popleft()
            for v in range(n):
                if par[v] == -1 and cap[u][v] > 0:
                    par[v] = u
                    q.append(v)
        if par[t] == -1:                       # no augmenting path left
            return flow, [par[v] != -1 for v in range(n)]
        b, v = float("inf"), t
        while v != s:
            b = min(b, cap[par[v]][v]); v = par[v]
        v = t
        while v != s:
            cap[par[v]][v] -= b; cap[v][par[v]] += b; v = par[v]
        flow += b

def gomory_hu(n, edges):
    p, fl = [0] * n, [0] * n
    for s in range(1, n):
        t = p[s]
        f, X = min_cut(n, edges, s, t)
        fl[s] = f
        for i in range(n):
            if i != s and X[i] and p[i] == t:
                p[i] = s
        if X[p[t]]:
            p[s], p[t] = p[t], s
            fl[s], fl[t] = fl[t], f
    return [(v, p[v], fl[v]) for v in range(1, n)]

def query(n, tree, u, v):
    adj = [[] for _ in range(n)]
    for a, b, w in tree:
        adj[a].append((b, w)); adj[b].append((a, w))
    stack = [(u, -1, float("inf"))]
    while stack:
        x, parent, m = stack.pop()
        if x == v:
            return m
        for y, w in adj[x]:
            if y != parent:
                stack.append((y, x, min(m, w)))

Test it the way you would test any clever algorithm: against brute force. For random graphs of up to eight vertices, compare query with a direct min_cut for every pair, and for every tree edge, check that the partition left by removing it has the edge's weight as its cut capacity in the original graph. That second check is the one that catches a missing swap step. The code above passes both on hundreds of random graphs.

Worked example, step by step

Run the algorithm on the graph in the figure. Every vertex starts with parent 0.

The last row is the interesting one. The minimum 5-2 cut isolates vertex 2 (its edges sum to 4 + 5 + 4 = 13), so everything else, including 2's parent 1, is on 5's side. The swap makes 5 the child of 1 with 2's old weight 10, and 2 the child of 5 with the new weight 13. The final tree has edges 1-0 (15), 4-0 (13), 5-1 (10), 2-5 (13) and 3-5 (12).

Check a query. The minimum cut between 4 and 3 is the smallest weight on the path 4-0-1-5-3, which is 10. Removing edge 5-1 leaves {0, 1, 4} and {2, 3, 5}; the graph edges crossing are 1-2 (4), 1-5 (3) and 4-5 (3), total 10, so the tree also hands you the cut. Every one of the 15 pairs checks out against a direct max-flow.

Note that minimum cuts are often not unique. Another max-flow implementation might return a different X in some step and build a different tree. Both trees are valid; only the values they report are guaranteed to agree.

Answering queries

Once built, the tree answers questions in several ways depending on volume.

• A few queries: walk the path, O(n) each, as in the code above.
• Many online queries: root the tree and use binary lifting, storing the minimum edge weight on each 2^k jump. Each query then costs O(log n) after O(n log n) preprocessing, the same structure as lowest common ancestor.
• All pairs at once: sort tree edges by weight, descending, and add them with union-find. When an edge of weight w joins components of sizes a and b, exactly a·b pairs get λ = w, because w is the smallest weight on their path. This produces the full value histogram in O(n log n), handy for reliability reports.
• Global minimum cut: the lightest tree edge, though Stoer-Wagner is simpler if that is all you need.

Cost and choice of max-flow

The cost is n−1 max-flow calls on the full graph, so the max-flow routine dominates everything. Edmonds-Karp is fine for teaching and small graphs; for real networks use Dinic or push-relabel, which are much faster in practice on unit-capacity and sparse graphs. Gusfield's version has a practical advantage over the contraction method here: every call sees the same graph, so you can build the adjacency structure once and only reset capacities between calls.

Each step reads the parent array written by earlier steps, so the loop is sequential; for most graphs the simple loop with a good max-flow is the right first answer.

Applications and limits

Network reliability is the classic use. Put link capacities on a backbone graph and the tree gives, for every pair of sites, how much capacity must fail before they are disconnected, plus which links form that cut. The union-find histogram tells you how many site pairs share each weakest cut.

Graph clustering is the second. Flake, Tarjan and Tsioutsiouliklis built cut clustering on minimum cut trees: add an artificial sink connected to every vertex with weight α, build the tree, remove the sink, and the remaining components are clusters, with α controlling their size. Removing the k−1 lightest tree edges also gives a classic approximation for the minimum k-cut problem, within a factor of 2 − 2/k.

One hard limit: all of this needs an undirected graph. Directed minimum cuts are not symmetric, and in general no tree can represent them.

Bugs that pass casual testing

Trade-offs

Gusfield or contraction? Gusfield is shorter and easier to get right; contraction runs each flow on a smaller graph, which can pay off on huge graphs if you are willing to implement it carefully. Tree or brute force? Below a few dozen vertices, all-pairs max-flow is simple enough. Exact or approximate? If capacities change constantly, recomputing n−1 flows per update may be too slow, and a sketch of only the cuts you care about may serve better.

To go deeper, start with the max-flow min-cut theorem, then the two max-flow routines worth knowing, Edmonds-Karp and Dinic's algorithm; advanced flow networks covers neighbouring problems, and union-find powers the all-pairs histogram.

What to do next

1. Implement min_cut and gomory_hu from this article and reproduce the example tree by hand.
2. Write the brute-force test: every pair's value, and every tree edge's cut capacity, on random small graphs.
3. Delete the swap step and watch the cut test fail while the value test still passes; some published snippets take that shortcut.
4. Swap Edmonds-Karp for Dinic and time both on a graph with a few thousand vertices.
5. Add binary-lifting queries, or the union-find histogram if you need all pairs.
6. Apply it to a real undirected network you own, such as a link-capacity graph, and list the five weakest site pairs.