Skip to content
Tutorials Center
My learning

Topics

Lesson 133 of 225 ยท Graphs

Gomory-Hu Tree

Build a Gomory-Hu tree with Gusfield's algorithm in Python: n-1 max-flow runs give every pairwise minimum cut, and the lightest tree edge is the global min cut.

Suppose a network has 1,000 servers and you want to know, for any two of them, the smallest total capacity of links you would have to cut to separate them. That is the minimum s-t cut from network flow, and there are about 500,000 pairs. Running a max-flow for every pair is slow.

A Gomory-Hu tree (Gomory and Hu, 1961) is a remarkable shortcut. For an undirected graph with n vertices, a weighted tree on the same vertices can be built with only n - 1 max-flow computations, and it answers every pair at once: the minimum cut between a and b in the original graph equals the smallest edge weight on the tree path from a to b. Even better, removing that lightest tree edge splits the tree into two parts that form an actual minimum cut of the original graph.

This lesson builds the tree with Gusfield's algorithm, a simple variant that needs no graph contraction, and checks it against brute force. You should know Edmonds-Karp max flow first.

What the tree promises

For every pair of vertices s, t, the tree has two properties:

  1. Value: the minimum s-t cut value in the graph = the minimum edge weight on the tree path between s and t.
  2. Cut: if that lightest path edge is (x, y) with weight w, deleting it from the tree leaves two components. Those two vertex sets, taken in the original graph, form a minimum s-t cut of size w.

The tree edges are not necessarily edges of the original graph. The tree only summarises cut values.

flowchart LR
    subgraph G["Original graph (8 edges)"]
      g0((0)) --- g1((1))
      g0 --- g2((2))
      g1 --- g2
      g1 --- g3((3))
      g2 --- g4((4))
      g3 --- g4
      g3 --- g5((5))
      g4 --- g5
    end
    subgraph T["Gomory-Hu tree (5 edges)"]
      t2((2)) ---|12| t0((0))
      t0 ---|16| t1((1))
      t1 ---|9| t3((3))
      t3 ---|14| t4((4))
      t4 ---|11| t5((5))
    end
    G --> T

A tree always has exactly n - 1 edges, even when the graph has many more.

Gusfield's algorithm

Keep two arrays: parent[v] (initially 0 for everyone) and weight[v]. For each vertex s from 1 to n - 1:

  1. Let t = parent[s]. Compute a max flow from s to t in the original graph and note the minimum cut's source side S (the vertices still reachable from s in the residual graph).
  2. Set weight[s] to the flow value. The tree edge is (s, parent[s]).
  3. For every later vertex v > s that is on the S side and has parent[v] == t, set parent[v] = s.

Step 3 is the clever part: a later vertex that sits with s on the near side of this cut should hang below s rather than t, so future flows compare it with a closer neighbour. After the loop, the edges (s, parent[s], weight[s]) for s = 1..n-1 are a Gomory-Hu tree.

Python Build the tree and verify all 15 pairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree has five edges but we compared fifteen pairs: five max-flow runs (the algorithm) against fifteen (the check) agree on every pair. The three queries at the bottom all print 9, because the lightest edge on each path is the tree edge (3, 1). Removing it separates {0, 1, 2} from {3, 4, 5} in the tree, and in the original graph the edges crossing that split are (1, 3) with capacity 5 and (2, 4) with capacity 4: total 9.

Reading the global minimum cut

The global minimum cut (see Karger's algorithm) is the smallest s-t cut over all pairs. Every cut separates some pair, so the global minimum is simply the lightest edge of the Gomory-Hu tree. Deleting it gives the two sides.

Python Global min cut and a full pairwise table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The lightest tree edge is (3, 1) with weight 9. Its two sides, {0, 1, 2} and {3, 4, 5}, are the same split as before, and the original graph agrees with a crossing capacity of 9. The table is symmetric, and each entry is the bottleneck on a tree path, found with one BFS per row.

Cost and use

  • Build: n - 1 max-flow runs. With Edmonds-Karp each is O(V E^2), but any max-flow algorithm works, and fast ones such as push-relabel make this practical for thousands of vertices.
  • Query: one bottleneck query on a tree. Walk the path in O(n), or preprocess with binary lifting to answer in O(log n).
  • Applications: network reliability (which pairs are most fragile), image segmentation with many seed pairs, cluster analysis, and any "minimum cut for many pairs" problem.
  • Directed graphs: the tree does not exist. Asymmetric cuts break the property, so this works only for undirected graphs.

Common mistakes

  • Running the flows on the shrinking tree instead of the original graph. Every flow in Gusfield's algorithm uses the full original graph.
  • Reading weight for pairs that are not tree-adjacent. For non-adjacent pairs you need the minimum along the whole path.
  • Assuming tree edges exist in the graph. the tree edge (4, 3) with weight 14 is bigger than the capacity of the real edge (3, 4), which is only 7, because the tree edge records the flow through all routes. In general a tree edge may not exist in the graph at all.
  • Forgetting to restrict step 3 to later vertices. Only v > s with parent[v] == t change; touching earlier vertices breaks the tree.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many max-flow computations does Gusfield's algorithm need for n vertices?

    One flow for each vertex from 1 to n - 1, always against the original graph, produces the n - 1 tree edges.
  2. 2. How do you find the minimum cut between a and b from the tree?

    The bottleneck (minimum-weight edge) of the tree path equals the minimum a-b cut value in the original graph.
  3. 3. Where is the global minimum cut in a Gomory-Hu tree?

    Every cut separates some pair, and the lightest tree edge is the smallest pair value, so it equals the global minimum cut.
  4. 4. Which graphs have a Gomory-Hu tree?

    The construction relies on the symmetry of undirected cuts; directed graphs do not have such a tree.

Summary

  • A Gomory-Hu tree of an undirected graph has n - 1 edges and encodes all pairwise minimum cuts.
  • The min cut between two vertices is the lightest edge on their tree path; removing that edge reveals the cut itself.
  • Gusfield's algorithm builds it with n - 1 max-flow runs on the original graph and a simple parent update.
  • The lightest tree edge is the global minimum cut.
  • It works for undirected graphs only.

Next: Counting Spanning Trees, a different view of graph structure with matrices and codes.