Introduction

Imagine a road network with capacities on every lane. You want to know: if a flood cuts the city in two, which partition minimizes the total disrupted flow? Now imagine someone asks you that question for every pair of neighbourhoods simultaneously.

In a graph with n nodes, there are n(n−1)/2 ordered pairs — and computing each pair's max-flow from scratch would cost at least n2n^{2} max-flow runs. In 1961, Ralph Gomory and T. C. Hu found a far better way.

Their insight: build a weighted tree on the same n nodes using only n−1 max-flow computations. This Gomory-Hu tree has a remarkable property — the minimum-weight edge on the unique path between any two nodes equals the max-flow between them in the original graph. All n(n−1)/2 answers, compressed into n−1 edges.

This is not an approximation. The tree is exact, and querying it takes only O(n)O(n) time — a linear scan along the path. It is one of the most elegant data-structure results in combinatorial optimization, sitting at the intersection of max-flow theory and spanning trees.

Query Any Pair

The demo below has a fixed 5-node flow network (left panel) with capacities on each edge. The Gomory-Hu tree built from it is shown on the right. Select a source and a target and the demo will highlight the tree path and report the minimum edge weight on that path — which equals the max-flow between those nodes in the original network.

<p class="hint">Select a <b>source</b> and a <b>target</b> node. The demo highlights
the path in the Gomory-Hu tree and shows the bottleneck edge weight — which
equals the max-flow between those two nodes in the original network.</p>
<div class="panels">
  <div class="panel">
    <div class="panel-title">Flow Network (capacities)</div>
    <svg id="net-svg" width="220" height="220" viewBox="0 0 220 220"></svg>
  </div>
  <div class="panel">
    <div class="panel-title">Gomory-Hu Tree (min-cuts)</div>
    <svg id="tree-svg" width="220" height="220" viewBox="0 0 220 220"></svg>
  </div>
</div>
<div class="controls">
  <label>Source <select id="src"></select></label>
  <label>Target <select id="tgt"></select></label>
  <button id="query" type="button">Query max-flow</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="result" id="result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .87rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.panels { display: flex; gap: 10px; flex-wrap: wrap; }
.panel { flex: 1 1 200px; }
.panel-title { font-size: .75rem; font-weight: 700; letter-spacing: .04em;
               text-transform: uppercase; color: #1d3557; margin-bottom: 4px; }
svg { background: #f0f4f8; border-radius: 10px; display: block; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin: .6rem 0 .3rem; }
label { font-size: .85rem; display: flex; align-items: center; gap: .3rem; }
select { font: inherit; padding: .22rem .4rem; border: 1px solid #bcc0c6; border-radius: 6px; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: .93rem; font-weight: 600; min-height: 1.4em; }
.result.ok { color: #0a7d33; }
.result.idle { color: #555; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Gomory-Hu Tree demo
// 5-node undirected flow network. Nodes: 0=A, 1=B, 2=C, 3=D, 4=E
// Network edges [u, v, capacity]
// Gomory-Hu tree edges [u, v, min-cut-value] computed via Gusfield’s algorithm.
// All 10 pairwise max-flows verified against Ford-Fulkerson ground truth.

var LABELS = ['A','B','C','D','E'];

// Network layout positions (cx, cy) in 220x220 SVG
var NET_POS = [ [110,28],[36,100],[184,100],[60,190],[160,190] ];
// Network edges [u, v, capacity]
var NET_EDGES = [
  [0,1,3],[0,2,5],[1,2,2],[1,3,4],[2,4,6],[3,4,2]
];

// Tree layout positions
// Gomory-Hu tree edges [u, v, min-cut value]
// B-A:7, C-A:8, D-B:6, E-C:8
var TREE_EDGES = [
  [1,0,7],[2,0,8],[3,1,6],[4,2,8]
];

var N = 5;

// Build tree adjacency
var treeAdj = Array.from({length:N}, function(){ return []; });
TREE_EDGES.forEach(function(e){
  treeAdj[e[0]].push({to:e[1],w:e[2]});
  treeAdj[e[1]].push({to:e[0],w:e[2]});
});

// BFS path in tree, returns array of {from, to, w} edges or []
function treePath(src, tgt) {
  if (src === tgt) return [];
  var parent = Array(N).fill(-1);
  var parentW = Array(N).fill(0);
  var visited = Array(N).fill(false);
  var queue = [src]; visited[src] = true;
  while (queue.length) {
    var u = queue.shift();
    for (var i = 0; i < treeAdj[u].length; i++) {
      var nb = treeAdj[u][i];
      if (!visited[nb.to]) {
        visited[nb.to] = true;
        parent[nb.to] = u;
        parentW[nb.to] = nb.w;
        queue.push(nb.to);
      }
    }
  }
  var path = [];
  var cur = tgt;
  while (cur !== src) {
    path.unshift({from: parent[cur], to: cur, w: parentW[cur]});
    cur = parent[cur];
  }
  return path;
}

function minOnPath(path) {
  var m = Infinity;
  path.forEach(function(e){ if (e.w < m) m = e.w; });
  return m;
}

// SVG helpers
function svgEl(tag, attrs) {
  var el = document.createElementNS('http://www.w3.org/2000/svg', tag);
  Object.keys(attrs).forEach(function(k){ el.setAttribute(k, attrs[k]); });
  return el;
}

function isHighlightedEdge(u, v, pathEdges) {
  for (var i = 0; i < pathEdges.length; i++) {
    var e = pathEdges[i];
    if ((e.from===u && e.to===v) || (e.from===v && e.to===u)) return true;
  }
  return false;
}

function drawGraph(svgId, positions, edges, pathEdges, hlSrc, hlTgt) {
  var svg = document.getElementById(svgId);
  svg.innerHTML = '';

  // Draw edges first
  edges.forEach(function(e){
    var u=e[0],v=e[1],w=e[2];
    var x1=positions[u][0],y1=positions[u][1],x2=positions[v][0],y2=positions[v][1];
    var hl = isHighlightedEdge(u, v, pathEdges);
    svg.appendChild(svgEl('line',{x1:x1,y1:y1,x2:x2,y2:y2,
      stroke: hl ? '#e63946' : '#94a8be',
      'stroke-width': hl ? 3.2 : 2,
      'stroke-linecap': 'round'}));
    // Weight label
    var mx=(x1+x2)/2, my=(y1+y2)/2;
    svg.appendChild(svgEl('rect',{x:mx-9,y:my-8,width:18,height:15,fill:'#f0f4f8',rx:3}));
    var lbl = svgEl('text',{x:mx,y:my+4.5,'text-anchor':'middle',
      'font-size':'12','font-family':'system-ui,sans-serif',
      'font-weight':'700', fill: hl ? '#c92f3c' : '#1d3557'});
    lbl.textContent = w;
    svg.appendChild(lbl);
  });

  // Draw nodes
  positions.forEach(function(pos, i){
    var cx=pos[0], cy=pos[1];
    var isSrc = i === hlSrc, isTgt = i === hlTgt;
    var fill = isSrc ? '#1d7a4d' : (isTgt ? '#c92f3c' : '#2f5a82');
    svg.appendChild(svgEl('circle',{cx:cx,cy:cy,r:17,fill:fill,stroke:'#fff','stroke-width':2.5}));
    var lbl = svgEl('text',{x:cx,y:cy+5,'text-anchor':'middle',
      'font-size':'13','font-family':'system-ui,sans-serif',
      'font-weight':'700',fill:'#fff'});
    lbl.textContent = LABELS[i];
    svg.appendChild(lbl);
  });
}

function populateSelects() {
  ['src','tgt'].forEach(function(id){
    var sel = document.getElementById(id);
    LABELS.forEach(function(l,i){
      var opt = document.createElement('option');
      opt.value = i; opt.textContent = l; sel.appendChild(opt);
    });
  });
  document.getElementById('tgt').value = 3; // default A->D
}

function render(pathEdges, src, tgt) {
  drawGraph('net-svg', NET_POS, NET_EDGES, [], src, tgt);
  drawGraph('tree-svg', NET_POS, TREE_EDGES.map(function(e){return e.slice();}), pathEdges, src, tgt);
}

function query() {
  var src = +document.getElementById('src').value;
  var tgt = +document.getElementById('tgt').value;
  var res = document.getElementById('result');
  if (src === tgt) {
    res.textContent = `Source and target are the same node.`;
    res.className = 'result idle';
    render([], src, tgt);
    return;
  }
  var path = treePath(src, tgt);
  var flow = minOnPath(path);
  var bottleneck = path.filter(function(e){ return e.w === flow; })[0];
  res.textContent = fmt(`max-flow(%v% → %v2%) = %flow%  (bottleneck: %v3%–%v4%, weight %flow%)`, { v: LABELS[src], v2: LABELS[tgt], flow: flow, v3: LABELS[bottleneck.from], v4: LABELS[bottleneck.to] });
  res.className = 'result ok';
  render(path, src, tgt);
  console.log(`max-flow`, LABELS[src], '->', LABELS[tgt], '=', flow, `| path edges:`, JSON.stringify(path));
}

function resetView() {
  document.getElementById('src').value = 0;
  document.getElementById('tgt').value = 3;
  document.getElementById('result').textContent = '';
  document.getElementById('result').className = 'result idle';
  render([], 0, 3);
}

populateSelects();
document.getElementById('query').addEventListener('click', query);
document.getElementById('reset').addEventListener('click', resetView);
render([], 0, 3);
Result
Console

Notice that the tree has only 4 edges for 5 nodes, yet it answers all 10 pairwise flow questions instantly. The bottleneck edge on the tree path is always the answer — this is the Gomory-Hu guarantee.

The Real Complexity

The Gomory-Hu tree is a solved, polynomial-time result — not NP-hard, not open. Here is the full picture:

  • Naive baseline: n(n−1)/2 max-flow runs — one per pair. For n = 100 that is 4950 max-flow calls.
  • Gomory-Hu construction: exactly n−1 max-flow computations, proved sufficient by induction on the tree structure. For n = 100 that is 99 calls — a 50× reduction.
  • Query time: O(n)O(n) — find the unique tree path between two nodes (BFS or DFS) and return the minimum edge weight on it.
  • Total cost: (n−1) × T(max-flow), where T(max-flow) is the cost of a single max-flow run (e.g. O(V⋅E)O(V \cdot E) with Dinic's algorithm).

Why it works. The key theorem (Gomory & Hu, 1961) states: for any edge (u, v) in the tree with weight w, removing that edge partitions the tree into two parts S and V\S, and this partition is a minimum s-t cut in the original graph with capacity w. Every tree edge encodes both the max-flow value and a witness cut.

In 1990, Dan Gusfield gave an even simpler algorithm that builds an equivalent structure (cut-equivalent tree) using the same n−1 max-flow calls but without requiring augmenting-path bookkeeping — making implementation straightforward.

Contrast this with max-flow itself, which is also polynomial but has seen decades of refinement. The Gomory-Hu tree adds a structural layer on top: once the tree is built, the expensive per-pair computation is replaced by a cheap tree traversal.

Where It Matters

Any system that needs all-pairs flow or cut information benefits from the Gomory-Hu tree:

  • Network reliability: engineers ask "what is the worst-case failure mode between every pair of data centres?" The Gomory-Hu tree answers all pairs at the cost of n−1 flow runs, then stores the answers compactly.
  • Hierarchical clustering: the tree naturally defines a dendrogram — cutting its minimum-weight edge partitions the graph into the two groups with the smallest max-flow, which is the tightest bottleneck. This is used in community detection on social graphs.
  • Image segmentation: pixel graphs are huge, but the Gomory-Hu tree lets algorithms find all-pairs min-cuts without quadratic recomputation — speeding up interactive segmentation tools.
  • VLSI design: checking connectivity requirements across chip regions uses all-pairs cut queries answered by the tree.
  • Competitive programming: problems that ask "for each query (s, t), what is the maximum flow?" are solved in O(nlog⁡n)O(n \log n) build + O(n)O(n) per query using the Gomory-Hu tree.

The underlying idea — reduce quadratic queries to linear tree traversals — also inspired related structures like the Cactus representation of all minimum cuts (Dinits, Karzanov, Lomonosov, 1976), which extends the tree to capture all min-cut partitions, not just one per pair.

Conclusion

The Gomory-Hu tree is a reminder that structure, not brute force, is usually the key to efficiency. Computing all n(n−1)/2 pairwise max-flows independently seems to demand quadratic work — yet n−1 carefully chosen max-flow runs are enough, and the results fit in a single spanning tree.

Every edge in that tree is both a value and a proof: the minimum weight on the tree path between s and t is the exact max-flow, and the partition induced by removing that edge is a valid min-cut. No approximation, no heuristic.

If you have enjoyed this result, you will find related elegance in max-flow theory and in the minimum spanning tree — another case where a tree encodes global optimality far more compactly than expected.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/gomory-hu-tree/Content licensed under CC BY-NC 4.0.