Introduction

Imagine you need to broadcast a signal from one hub to every city in a network. The links are directed — a cable from A to B doesn't help traffic going the other way — and each link has a cost. You want to spend as little as possible while still reaching every city from that hub.

What you're looking for is called a minimum arborescence: a directed spanning tree rooted at the hub, where every edge points away from the root (or, equivalently, every node has a unique directed path back to the root), and the total edge cost is minimized.

For undirected graphs, Kruskal's greedy algorithm solves the minimum spanning tree problem in O(mlog⁡m)O(m \log m) by just sorting edges and picking the cheapest non-cycle-forming one. But the moment edges have directions, that greedy fails. The same edge set can form a valid arborescence or a dead end depending on which way the arrows point.

The key insight took until 1965, when Y. J. Chu and T. H. Liu (and independently Jack Edmonds in 1967) published an algorithm elegant enough to teach in a single lecture: pick the cheapest incoming edge for every non-root node, and if the result is a valid arborescence you're done. If not, it contains a directed cycle — and the algorithm contracts that cycle into a single super-node, adjusts edge weights to account for what you'd replace, and recurses.

Try It: Find the Cheapest Tree

The graph below has 6 nodes (node 0 is the root, shown in blue) and directed weighted edges. Toggle edges on or off to build your own arborescence — every non-root node needs exactly one incoming edge, and there must be no directed cycles.

<p class="hint">Node <b>0</b> (blue) is the root. Toggle edges on/off to build your own arborescence — each non-root node needs exactly one incoming active edge, with no directed cycles. Then press <b>Run Chu–Liu/Edmonds</b> to find the optimal tree.</p>
<div id="graph-wrap">
  <svg id="graph" viewBox="0 0 420 280" xmlns="http://www.w3.org/2000/svg"></svg>
</div>
<div class="controls">
  <button id="btn-run" type="button">Run Chu–Liu/Edmonds</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status"></div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#graph-wrap { background: #f4f7fa; border-radius: 10px; border: 1px solid #d5dde5; overflow: hidden; }
#graph { width: 100%; display: block; }
.edge-path { stroke: #adb5bd; stroke-width: 2; fill: none; cursor: pointer; transition: stroke .15s; }
.edge-path.active { stroke: #1d6fa0; stroke-width: 2.6; }
.edge-path.optimal { stroke: #0a7d33; stroke-width: 3; }
.edge-path:hover { stroke: #7aacc8; }
.arrow-poly { transition: fill .15s; }
.arrow-poly.none { fill: #adb5bd; }
.arrow-poly.active { fill: #1d6fa0; }
.arrow-poly.optimal { fill: #0a7d33; }
.edge-lbl { font: 600 11px system-ui; fill: #666; pointer-events: none; }
.edge-lbl.active { fill: #1d6fa0; }
.edge-lbl.optimal { fill: #0a7d33; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin: .7rem 0 .4rem; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .93rem; font-weight: 600; min-height: 1.4em; margin: .2rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d6fa0; }
.log { font-size: .78rem; color: #555; line-height: 1.6; white-space: pre-wrap;
       max-height: 80px; overflow-y: auto; margin-top: .2rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimum Arborescence demo – Chu-Liu/Edmonds algorithm.
// Node 0 is the root. User toggles edges; algorithm finds optimal arborescence.

const ROOT = 0;
const N = 6;

// SVG positions for nodes (viewBox 0 0 420 280)
const POS = [
  [55,  140],  // 0 root
  [170,  50],  // 1
  [320,  50],  // 2
  [170, 230],  // 3
  [320, 230],  // 4
  [390, 140],  // 5
];

// Directed edges: [from, to, weight]
const EDGES = [
  [0, 1, 4],
  [0, 3, 7],
  [1, 2, 3],
  [1, 3, 6],
  [2, 5, 5],
  [3, 1, 2],
  [3, 4, 4],
  [4, 2, 3],
  [4, 5, 6],
  [3, 5, 9],
];

let active = new Set();   // edge indices toggled by user
let optimal = null;       // Set of edge indices from algorithm

const svg = document.getElementById('graph');
const NR = 18; // node radius
const AS = 7;  // arrowhead size

function norm(dx, dy) {
  const len = Math.sqrt(dx*dx + dy*dy) || 1;
  return [dx/len, dy/len];
}

// Quadratic bezier offset (perpendicular) to avoid overlap with reverse edges
function edgePath(fi, ti) {
  const [fx,fy] = POS[fi], [tx,ty] = POS[ti];
  const [ux,uy] = norm(tx-fx, ty-fy);
  const px = -uy, py = ux;
  // slight curve offset
  const off = 10;
  const mx = (fx+tx)/2 + px*off, my = (fy+ty)/2 + py*off;
  // end point: back from node circle
  const ex = tx - ux*(NR+1), ey = ty - uy*(NR+1);
  return { d: `M${fx},${fy} Q${mx},${my} ${ex},${ey}`,
           tipX: ex, tipY: ey, ux, uy,
           lblX: (fx+tx)/2 + px*(off+10), lblY: (fy+ty)/2 + py*(off+10) };
}

function arrowPoints(tipX, tipY, ux, uy) {
  const bx = tipX - ux*AS, by = tipY - uy*AS;
  const px = -uy*3.5, py = ux*3.5;
  return `${bx+px},${by+py} ${tipX},${tipY} ${bx-px},${by-py}`;
}

function cls(i) {
  if (optimal && optimal.has(i)) return 'optimal';
  if (active.has(i)) return 'active';
  return 'none';
}

function render() {
  svg.innerHTML = '';

  // Edges
  EDGES.forEach(([fi,ti,w], i) => {
    const {d, tipX, tipY, ux, uy, lblX, lblY} = edgePath(fi, ti);
    const c = cls(i);

    const path = document.createElementNS('http://www.w3.org/2000/svg','path');
    path.setAttribute('d', d);
    path.setAttribute('class', 'edge-path ' + c);
    path.addEventListener('click', () => {
      if (optimal) return;
      active.has(i) ? active.delete(i) : active.add(i);
      render(); setStatus('');
    });
    svg.appendChild(path);

    const poly = document.createElementNS('http://www.w3.org/2000/svg','polygon');
    poly.setAttribute('points', arrowPoints(tipX, tipY, ux, uy));
    poly.setAttribute('class', 'arrow-poly ' + c);
    poly.style.pointerEvents = 'none';
    svg.appendChild(poly);

    const lbl = document.createElementNS('http://www.w3.org/2000/svg','text');
    lbl.setAttribute('x', lblX); lbl.setAttribute('y', lblY);
    lbl.setAttribute('text-anchor','middle');
    lbl.setAttribute('dominant-baseline','middle');
    lbl.setAttribute('class', 'edge-lbl ' + c);
    lbl.textContent = w;
    svg.appendChild(lbl);
  });

  // Nodes
  POS.forEach(([x,y], i) => {
    const circle = document.createElementNS('http://www.w3.org/2000/svg','circle');
    circle.setAttribute('cx',x); circle.setAttribute('cy',y); circle.setAttribute('r',NR);
    circle.setAttribute('fill', i===ROOT ? '#1d3557' : '#e8eef3');
    circle.setAttribute('stroke', i===ROOT ? '#1d3557' : '#8a9bb0');
    circle.setAttribute('stroke-width','2');
    svg.appendChild(circle);

    const lbl = document.createElementNS('http://www.w3.org/2000/svg','text');
    lbl.setAttribute('x',x); lbl.setAttribute('y',y);
    lbl.setAttribute('text-anchor','middle'); lbl.setAttribute('dominant-baseline','middle');
    lbl.setAttribute('font','700 13px system-ui');
    lbl.setAttribute('fill', i===ROOT ? '#fff' : '#1d3557');
    lbl.style.pointerEvents = 'none';
    lbl.textContent = i;
    svg.appendChild(lbl);
  });
}

function setStatus(msg, c) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + (c||'');
}
function setLog(t) { document.getElementById('log').textContent = t; }

// ── Chu-Liu/Edmonds (recursive contraction) ────────────────────────────────────────────
// Returns Set of origIdx values, or null if no arborescence exists.
function chuLiuEdmonds(n, root, edges) {
  const logLines = [];
  function solve(n, r, edges) {
    if (n <= 1) return [];
    // Pick cheapest incoming edge per non-root node
    const inEdge = new Array(n).fill(null);
    for (const e of edges) {
      if (e.to === r) continue;
      if (!inEdge[e.to] || e.w < inEdge[e.to].w) inEdge[e.to] = e;
    }
    for (let v = 0; v < n; v++) {
      if (v !== r && !inEdge[v]) return null; // node unreachable
    }
    // Find directed cycle in chosen edges
    const succ = new Array(n).fill(-1);
    for (let v = 0; v < n; v++) if (v !== r && inEdge[v]) succ[v] = inEdge[v].from;
    const color = new Array(n).fill(0);
    let cycleNode = -1;
    function dfs(v) {
      if (color[v] === 2) return;
      if (color[v] === 1) { cycleNode = v; return; }
      color[v] = 1;
      if (succ[v] !== -1) dfs(succ[v]);
      color[v] = 2;
    }
    for (let v = 0; v < n && cycleNode === -1; v++) dfs(v);
    if (cycleNode === -1) {
      // No cycle — done
      return edges.filter(e => e.to !== r && inEdge[e.to] === e);
    }
    // Collect cycle
    const cycle = [cycleNode];
    let cur = succ[cycleNode];
    while (cur !== cycleNode) { cycle.push(cur); cur = succ[cur]; }
    logLines.push(fmt('Contract cycle: [%cycle%→%v%]', { cycle: cycle.join('→'), v: cycle[0] }));
    const cycleSet = new Set(cycle);
    const superNode = cycle[0]; // representative node
    // Build contracted edge list (adjust weights for edges entering cycle)
    const newEdges = [];
    for (const e of edges) {
      const nf = cycleSet.has(e.from) ? superNode : e.from;
      const nt = cycleSet.has(e.to)   ? superNode : e.to;
      if (nf === nt) continue;
      const nw = cycleSet.has(e.to) ? e.w - inEdge[e.to].w : e.w;
      newEdges.push({ from:nf, to:nt, w:nw, origIdx:e.origIdx,
                      entersCycleAt: cycleSet.has(e.to) ? e.to : -1,
                      replacedIdx: cycleSet.has(e.to) ? inEdge[e.to].origIdx : -1 });
    }
    // Compact node ids (remove non-representative cycle nodes)
    const kept = [];
    for (let v = 0; v < n; v++) if (!cycleSet.has(v) || v === superNode) kept.push(v);
    const remap = {}; kept.forEach((v,i) => remap[v] = i);
    const newN = kept.length;
    const newR = remap[r];
    const compEdges = newEdges.map(e => ({ ...e, from:remap[e.from], to:remap[e.to] }));
    // Recurse
    const sub = solve(newN, newR, compEdges);
    if (!sub) return null;
    // Expand: which cycle nodes are entered from outside in the sub-result?
    const enteredAt = new Set();
    for (const e of sub) if (e.entersCycleAt >= 0) enteredAt.add(e.entersCycleAt);
    // Add cycle edges, excluding the one that was replaced at each entered node
    const excludedOrigIdx = new Set();
    for (const v of enteredAt) excludedOrigIdx.add(inEdge[v].origIdx);
    const cycleEdges = cycle
      .filter(v => v !== r && !excludedOrigIdx.has(inEdge[v].origIdx))
      .map(v => inEdge[v]);
    return [...sub, ...cycleEdges];
  }
  const initEdges = edges.map((e,i) => ({ from:e[0], to:e[1], w:e[2], origIdx:i,
                                           entersCycleAt:-1, replacedIdx:-1 }));
  const result = solve(n, root, initEdges);
  setLog(logLines.length ? logLines.join('\n') : '(no cycle contraction needed)');
  if (!result) return null;
  return new Set(result.map(e => e.origIdx));
}

function userArborescenceStatus() {
  const inDeg = Array(N).fill(0);
  for (const i of active) inDeg[EDGES[i][1]]++;
  for (let v = 1; v < N; v++) if (inDeg[v] !== 1) return null;
  // reachability check
  const adj = {};
  for (const i of active) { const[f,t]=EDGES[i]; if(!adj[f])adj[f]=[]; adj[f].push(t); }
  const vis = new Set([ROOT]); const q = [ROOT];
  while (q.length) { const v=q.shift(); if(adj[v])adj[v].forEach(u=>{if(!vis.has(u)){vis.add(u);q.push(u);}}); }
  if (vis.size !== N) return null;
  let c = 0; active.forEach(i => c += EDGES[i][2]);
  return c;
}

document.getElementById('btn-run').addEventListener('click', () => {
  optimal = null; render();
  setStatus('Running…', 'info');
  const result = chuLiuEdmonds(N, ROOT, EDGES);
  if (!result) { setStatus('No arborescence exists from root 0.', 'bad'); return; }
  let cost = 0;
  result.forEach(i => cost += EDGES[i][2]);
  optimal = result;
  render();
  const userCost = userArborescenceStatus();
  let extra = '';
  if (userCost !== null) {
    extra = userCost === cost
      ? " " + fmt('Your tree also costs %userCost% — optimal!', { userCost: userCost })
      : " " + fmt('Your tree costs %userCost%; optimal saves %v%.', { userCost: userCost, v: userCost-cost });
  }
  setStatus(fmt('Optimal cost: %cost%.%extra%', { cost: cost, extra: extra }), 'ok');
});

document.getElementById('btn-reset').addEventListener('click', () => {
  active.clear(); optimal = null;
  render(); setStatus('Toggle edges, then run the algorithm!', 'info'); setLog('');
});

render();
setStatus('Toggle edges, then run the algorithm!', 'info');
Result
Console

When you press Run Chu–Liu/Edmonds, the algorithm greedily picks the cheapest incoming edge for each non-root node. If it finds a cycle, it contracts it into one super-node, adjusts weights, and repeats — until a valid arborescence emerges. The total cost is guaranteed to be optimal. Compare it to your hand-picked tree!

The Real Complexity

Unlike many problems that gain hardness when you add constraints, minimum arborescence remains solvable in polynomial time even with directed edges.

  • Naïve approach: try every spanning tree. A complete directed graph on nn nodes has nn−1n^{n-1} arborescences (Cayley-like counting), hopeless for large nn.
  • Chu–Liu/Edmonds algorithm (1965/1967): the proven optimal algorithm. At each phase, pick the cheapest incoming edge per non-root node (O(m)O(m)). If the chosen edges form a valid arborescence, done. Otherwise, find a directed cycle, contract it into one node, re-weight edges to capture the "swap cost," and recurse. Each contraction reduces the node count by at least 1, so at most n−1n-1 rounds happen.
  • Complexity: the basic version runs in O(mn)O(mn). With a Fibonacci heap (Tarjan, 1977), it reaches O(m+nlog⁡n)O(m + n \log n). The algorithm is exact and deterministic — it always finds the globally optimal arborescence.
  • Status: solved (Chu & Liu 1965; Edmonds 1967). There is no open problem here — unlike P vs NP, we know minimum arborescence is in P and have a beautiful algorithm that proves it.

The reason direction doesn't make the problem NP-hard is that the cycle-contraction idea preserves the substructure property. Contracting a greedy cycle and re-weighting is enough to reduce the problem to a strictly smaller instance, which is the hallmark of a polynomial algorithm. Compare this with problems like the Steiner tree, where the undirected version is already NP-hard.

Where It Matters

The moment you have a directed network and need to reach every node cheaply from one source, you need an arborescence:

  • Network broadcast and multicast: internet routers build distribution trees to deliver video streams from a single source to all subscribers at minimum bandwidth cost. The links are directional by nature.
  • Dependency resolution: build systems (Make, Bazel, Gradle) implicitly solve arborescence-like problems when ordering tasks — each task must be reachable from the build root with directed dependency edges.
  • Phylogenetic trees: biologists reconstruct evolutionary histories as directed trees (rooted at a common ancestor). Minimum-cost arborescences appear in maximum-parsimony methods where edge costs encode mutation counts.
  • Compiler dataflow: control-flow graphs have directed edges. Finding a dominator tree — a key structure in optimizing compilers — is closely related to arborescence problems.
  • Distributed systems: leader-election and spanning-tree protocols in distributed databases (e.g., Paxos-like systems) construct directed spanning structures where the elected node is the root.

The algorithm also has theoretical importance: it was one of the first to show that a natural combinatorial optimization problem on directed graphs could be solved efficiently, foreshadowing the rich theory of matroids and submodular functions that underpins much of modern combinatorial optimization. See also minimum spanning tree for the undirected cousin.

Conclusion

The minimum arborescence problem is a reminder that direction does not always mean hardness. Where undirected spanning trees bend to a simple greedy sort-and-add, directed trees need a smarter idea — but that idea, cycle contraction, is clean enough to implement in an afternoon and efficient enough to run on massive real networks.

Chu–Liu and Edmonds gave us a proven optimal, polynomial-time algorithm in the 1960s. It remains the textbook answer today, and its core idea — contract a bad structure, re-weight, recurse — echoes through dozens of algorithms in combinatorial optimization.

Next time you stream a video or build a software project, there's a good chance a directed spanning tree is quietly working behind the scenes, keeping the cost low. Now you know the algorithm that finds it.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/minimum-arborescence/Content licensed under CC BY-NC 4.0.