Minimum Spanning Arborescence, in depth: Chu-Liu/Edmonds from first principles with a tested implementation

Why undirected MST algorithms fail

It is tempting to reuse Kruskal's or Prim's algorithm. Both fail, for reasons that explain the directed algorithm.

Ignoring direction fails. Take edges r→a (1), b→a (2) and r→b (10). An undirected MST picks r–a and a–b, weight 3, but the only edge between a and b points into a, so b cannot be reached from r. The correct answer is r→a plus r→b, weight 11.

Growing greedily from the root fails. Take r→a (5), r→b (6) and b→a (1). Prim-style growth adds the cheapest edge leaving the tree: r→a (5), then r→b (6), total 11. The optimum is r→b then b→a, total 7. Greedy growth commits to a's parent before seeing that a cheaper path to a goes through b.

The cut property that makes undirected greedy algorithms correct does not hold here, because an edge's usefulness depends on its direction, and on whether its tail will itself be reachable.

Cheapest incoming edges and cycles

Start from the constraint instead of from the root. In any arborescence, every non-root vertex has exactly one incoming edge. So the cheapest conceivable answer gives each non-root vertex its cheapest incoming edge. Ignore self-loops and edges into the root, which can never be used. If some vertex has no incoming edge at all, no arborescence exists.

If these chosen edges contain no cycle, they form an arborescence: n − 1 edges, each vertex with one parent and no cycles, so following parents from any vertex reaches the root. It is optimal because no vertex could have a cheaper parent. If they do contain a cycle, the cycle cannot reach the root. Any valid answer must enter the cycle from outside at least once, which means replacing exactly one cycle vertex's chosen edge with an edge from outside.

An exchange argument shows there is always an optimal answer that keeps all of the cycle's edges except one. So the cycle can be treated as a single super-vertex. When an edge u→v enters the cycle at v, using it means giving up v's cycle edge, so its effective cost is w(u, v) − w(cycle edge into v). These are the reduced costs. Solve the smaller graph recursively, and the edge it chooses into the super-vertex tells you which cycle edge to drop. Edges leaving the cycle keep their weights. Each contraction removes at least one vertex, so there are at most n − 1 levels.

Worked example

Take root r and vertices a, b, c, d with edges r→a 9, r→b 10, r→d 12, a→b 3, b→c 4, c→a 2, c→d 7, d→b 5 and b→d 6.

1. Cheapest incoming edges: a gets c→a (2), b gets a→b (3), c gets b→c (4), d gets b→d (6). The edges a→b→c→a form a cycle of weight 9.
2. Contract {a, b, c} into C. Edges entering C get reduced costs: r→a becomes 9 − 2 = 7, r→b becomes 10 − 3 = 7, d→b becomes 5 − 3 = 2. Edges leaving C keep their weights: b→d 6 and c→d 7.
3. Repeat: C's cheapest entry is d→C (2) and d's is C→d (6). That is a new cycle, so contract {C, d} into one vertex. The entries from r cost 7 − 2 = 5 (via a or via b) or 12 − 6 = 6 (via d). Choose 5, using r→a.
4. Expand: r enters the outer cycle at C, so C's entry from d is dropped and d keeps b→d. Inside C, r→a enters at a, so the cycle edge into a, c→a, is dropped and a→b and b→c remain.

The result is r→a, a→b, b→c, b→d, with weight 9 + 3 + 4 + 6 = 22. Brute force over every choice of parents confirms 22 is optimal. The tie at step 3 is real: entering via r→b gives r→b, b→c, c→a, b→d, also 22. Minimum arborescences are often not unique, so tests should compare total weight, not edge sets.

Implementation

This implementation follows the description directly. It returns the total weight and the indices of the chosen edges, so callers can recover the tree, or None when some vertex is unreachable. Cycles are found by walking parent pointers, which is a special case of cycle detection in directed graphs.

def min_arborescence(n, edges, root):
    """edges: list of (u, v, w). Returns (total, [edge indices]) or None if no arborescence exists."""
    best = [None] * n                       # index of the cheapest edge entering each vertex
    for i, (u, v, w) in enumerate(edges):
        if u != v and v != root and (best[v] is None or w < edges[best[v]][2]):
            best[v] = i
    if any(best[v] is None for v in range(n) if v != root):
        return None                         # some vertex has no incoming edge at all

    comp, seen, cycles = [-1] * n, [-1] * n, 0
    for s in range(n):                      # walk parent pointers to find cycles
        x = s
        while x != root and seen[x] == -1 and comp[x] == -1:
            seen[x] = s
            x = edges[best[x]][0]
        if x != root and comp[x] == -1 and seen[x] == s:
            y = x
            while True:
                comp[y] = cycles
                y = edges[best[y]][0]
                if y == x:
                    break
            cycles += 1

    if cycles == 0:                         # cheapest in-edges already form a tree
        chosen = [best[v] for v in range(n) if v != root]
        return sum(edges[i][2] for i in chosen), chosen

    on_cycle = [comp[v] != -1 for v in range(n)]
    nxt = cycles
    for v in range(n):
        if comp[v] == -1:
            comp[v] = nxt
            nxt += 1

    sub_edges, origin = [], []              # contract: reduced cost w - (cycle edge into v)
    for i, (u, v, w) in enumerate(edges):
        if comp[u] != comp[v] and v != root:
            sub_edges.append((comp[u], comp[v], w - edges[best[v]][2]))
            origin.append(i)
    sub = min_arborescence(nxt, sub_edges, comp[root])
    if sub is None:
        return None

    chosen = [origin[j] for j in sub[1]]    # expand: keep cycle edges except at the entry vertex
    entered = {edges[i][1] for i in chosen}
    chosen += [best[v] for v in range(n) if on_cycle[v] and v not in entered]
    return sum(edges[i][2] for i in chosen), chosen

Reduced costs are subtracted for every vertex, including those not on a cycle. That only shifts each vertex's incoming edges by a constant, which does not change which edge is cheapest, and the final total is recomputed from the original weights. Negative weights are fine. The code was checked against an exhaustive search over all parent assignments on 20,000 random graphs with up to six vertices, including self-loops, parallel edges, edges into the root and unreachable vertices. Do the same with any version you adapt.

Complexity and choosing an implementation

Each level does O(E) work and there are at most V levels, so this version runs in O(VE) time, which is fine for thousands of vertices. Tarjan (1977) reduced this to O(E log V), or O(V²) for dense graphs, by keeping each super-vertex's incoming edges in mergeable heaps and tracking contractions with union-find. Gabow, Galil, Spencer and Tarjan (1986) reached O(E + V log V) with Fibonacci heaps. Choose O(VE) when clarity and auditability matter and graphs are modest. Choose O(V²) when the graph is dense, as in dependency parsing, where every word may point to every other. Choose the heap versions for large sparse graphs. The recursion is at most V deep, so convert it to a loop or raise the recursion limit before running Python on long chains.

Variants

• Maximum arborescence: negate every weight, or flip the comparison.
• Root not given: add a super-root s with an edge s→v of weight M to every vertex, where M exceeds the sum of all absolute weights. The optimum uses exactly one super-root edge whenever a single root works, and that edge's head is the best root.
• Optimum branching (a forest): for the maximum-weight branching, add a super-root with weight-0 edges to every vertex and find the maximum arborescence. The super-root's children are the forest's roots. The minimum branching is trivial with non-negative weights: no edges.
• Reachability first: if you only need to know whether an arborescence exists, a BFS from the root answers that in O(V + E).

Where it is used

Delta storage. Store n versions of a file. Add a root vertex representing nothing, an edge root→v whose cost is the full size of v, and an edge u→v whose cost is the size of a delta that rebuilds v from u. A minimum arborescence is the cheapest storage plan from which every version can be rebuilt. In practice, add a depth limit, because a long delta chain makes reads slow; Git caps chain length with pack.depth for this reason. The pure optimum ignores read cost.

Dependency parsing. McDonald and colleagues (2005) scored every possible head→dependent pair in a sentence and found the highest-scoring tree with Chu-Liu/Edmonds. This allows non-projective trees, with crossing arcs, which simpler parsers cannot produce. Neural parsers still often decode their score matrices this way.

Directed broadcast. When the cost of a link differs by direction, the cheapest structure for sending from one source to every node is a minimum arborescence rooted at the source.

Pitfalls and validation

A cheap validator catches most mistakes: check there are n − 1 chosen edges, every non-root vertex is the head of exactly one, and following parents from each vertex reaches the root within n steps. On large graphs, remember that every cycle lies inside one strongly connected component, so condensing the graph with Tarjan's SCC algorithm shows where contractions can happen at all.

What to do next

1. Work the five-vertex example by hand, contraction by contraction, until you get 22.
2. Run the implementation on that example and on the two counterexamples (expected 7 and 11).
3. Write the brute-force checker and compare on thousands of random small graphs, including self-loops and edges into the root.
4. Add the validator and run it on every result in production code.
5. Pick the variant you need: fixed root, super-root for an unknown root, or maximum branching.
6. If V reaches tens of thousands, switch to Tarjan's O(E log V) version or a tested library implementation.
7. For delta storage, add a chain-depth limit and measure read cost alongside storage.