Chu-Liu/Edmonds: Minimum Spanning Arborescence on Directed Graphs

The problem: why directed graphs need their own MST

A spanning arborescence rooted at r is a subgraph with exactly n-1 edges where every non-root vertex has exactly one incoming edge and every vertex is reachable from r by following edges in their direction. It is the directed analogue of a spanning tree, but the direction constraint changes everything.

• Undirected MST algorithms fail. Kruskal/Prim treat edges as bidirectional. On a digraph they may select an edge (u,v) that gives v an in-edge but leaves v unreachable from r, or give a vertex two in-edges.
• The naive greedy fails too. Picking the cheapest incoming edge for each vertex minimizes local cost, but those choices can form a directed cycle — a group of vertices pointing at each other, disconnected from the root.

This last failure is precisely what Chu-Liu/Edmonds is engineered to repair. The problem is also called finding an optimum branching (Edmonds' term). A related variant drops the fixed root and seeks the minimum arborescence over all possible roots, solvable by adding a virtual root.

How it works: cheapest in-edge, then contract cycles

The algorithm has three phases per level of recursion.

1. Discard root in-edges. Delete every edge pointing into r; the root has no parent.
2. Greedy selection. For each non-root vertex v, pick its minimum-weight incoming edge π(v). If this selection is acyclic, it is the optimal arborescence — return it.
3. Contract and reweight. If the selected edges contain a cycle C, collapse C into a single super-node. Every edge (u,v) entering the cycle (u∉C, v∈C) is reweighted:

w'(u,v) = w(u,v) - w(π(v), v)

That is, subtract the cost of the in-cycle edge that currently feeds v. Then recurse on the smaller contracted graph. When the recursion returns an arborescence, expand each super-node: the entering edge that survived tells you which single cycle edge to drop, breaking the cycle and leaving a tree. The correctness rests on one invariant: adding a constant to all in-edges of a vertex shifts every arborescence's weight by that same constant, so the optimum is preserved.

Complexity and a worked step-trace

Each contraction removes at least one vertex, so there are at most V levels of recursion; each level scans O(E) edges to find cheapest in-edges and reweight. That gives the classic O(VE) bound with O(V+E) space.

• Tarjan (1977): using efficient priority queues and disjoint-set union, O(min(V², E log V)) — optimal at both dense and sparse extremes.
• Gabow, Galil, Spencer, Tarjan (1986): O(E + V log V), the fastest known, beating Tarjan by a log factor in the mid-density regime.

Trace: root r; edges r→a=10, r→b=5, a→b=2, b→a=3. Greedy in-edges: a takes b→a=3, b takes a→b=2. That is the cycle a↔b. Contract to super-node S. Reweight root edges entering the cycle: r→a becomes 10-3=7; r→b becomes 5-2=3. Cheapest into S is r→b=3. Expanding, we keep r→b and drop a→b, keeping b→a=3. Final arborescence: r→b (5), b→a (3), total 8.

Where it's used in real systems

The arborescence problem is common wherever a rooted, cost-minimal directed tree is needed.

• NLP dependency parsing. This is the flagship use. In graph-based parsers (McDonald et al., 2005), each sentence is a complete digraph over words; edge scores come from an ML model; the maximum spanning arborescence rooted at a virtual ROOT is the parse tree. Modern neural parsers (e.g. the Dozat-Manning biaffine parser) run Chu-Liu/Edmonds as the decoding step to guarantee a well-formed tree. Maximization uses the same algorithm with negated weights.
• Network multicast and broadcast. Building a minimum-cost distribution tree from a source over directed, asymmetric links (satellite uplinks, one-way overlays).
• Phylogenetics and network reconstruction. Inferring rooted evolutionary or causal trees from directed pairwise scores.
• Operations research. Optimum branching appears in scheduling and hierarchical clustering with directed dissimilarities.

Because it is a polynomial exact solver, it is preferred over heuristics whenever the tree constraint must hold exactly.

Comparison to alternatives and the key tradeoff

The crucial distinction is what is being minimized.

• vs. Prim/Kruskal (undirected MST): those minimize total edge weight ignoring direction and cannot express the root-reachability constraint. Chu-Liu/Edmonds is strictly more general; it degenerates to no simple analogue because the directed structure needs contraction.
• vs. Dijkstra (shortest-path arborescence): Dijkstra's tree minimizes the path cost from root to each vertex. Chu-Liu/Edmonds minimizes the sum of chosen edge weights. These differ: a shortest-path tree can be much heavier in total weight, and the min-arborescence can have long root-to-leaf paths. Choose based on whether you care about per-node latency or total infrastructure cost.

The tradeoff: Chu-Liu/Edmonds is exact and polynomial but its cycle-contraction bookkeeping is markedly more intricate to implement correctly than Prim's heap loop or Dijkstra's relaxation. Getting the reweighting and super-node expansion right — mapping contracted edges back to originals — is where implementations most often go wrong.

Pitfalls, failure modes, and significance

Common implementation and usage traps:

• Forgetting to delete root in-edges. If the root is allowed a parent, the greedy step can build a cycle through the root and produce a non-arborescence.
• Reachability precondition. A finite-weight arborescence exists only if every vertex is reachable from r. If some vertex has no incoming edge from the reachable set, the problem is infeasible — detect this rather than returning garbage.
• Edge-identity loss during contraction. Each contracted edge must remember its original endpoint so expansion can restore the real tree; storing only reweighted values silently corrupts the output.
• Max vs. min sign errors. Parsers want the maximum arborescence; negate weights, but then be careful the greedy step picks max, not min.
• Ties and cycle length 1/self-loops. Handle self-loops and 2-cycles explicitly.

Its significance: Chu-Liu/Edmonds is a canonical example of the local-repair-by-contraction paradigm (echoed in Edmonds' blossom algorithm for matching), and it is the exact, correct answer to a problem where the intuitive greedy visibly fails.

Chu-Liu/Edmonds vs. undirected MST algorithms and its own optimized variants

Algorithm	Problem solved	Time complexity	Notes
Chu-Liu/Edmonds (naive)	Min spanning arborescence (directed, rooted)	O(VE)	Recursive cycle contraction; V rounds worst case
Tarjan (1977)	Same, optimized	O(min(V², E log V))	Optimal for very dense and very sparse graphs
Gabow-Galil-Spencer-Tarjan (1986)	Same, fastest known	O(E + V log V)	Uses Fibonacci-heap-style meldable priority queues
Prim	Undirected MST	O(E + V log V)	Fails on digraphs — ignores edge direction
Kruskal	Undirected MST	O(E log V)	Global-cheapest-edge greedy is wrong for arborescences
Dijkstra	Shortest-path tree (directed)	O(E + V log V)	Minimizes path costs, not total tree weight