Chu-Liu/Edmonds Algorithm

A Bit of History

Yoeng-Jin Chu and Tseng-Hong Liu published this algorithm in 1965, and Jack Edmonds — already met twice in this series, for the Blossom Algorithm and for helping define "polynomial time" itself — independently published an equivalent method in 1967. It solves the directed analogue of the minimum spanning tree problem from Part 11: given a directed graph and a chosen root, find the cheapest arborescence (a directed spanning tree where every edge points away from the root, and every vertex has exactly one incoming edge) — a natural fit for problems like broadcasting a signal outward from a single source with minimum total cable cost.

Working Principle

Kruskal's and Prim's greedy cut-property argument (see the Prim's algorithm deep dive) does not transfer directly to directed graphs, since a "cheapest edge crossing a cut" can create a directed cycle rather than safely extending a tree. Chu-Liu/Edmonds' algorithm handles this directly:

1. For every non-root vertex, select its single cheapest incoming edge.
2. If this selection contains no cycles, it is the minimum spanning arborescence — done.
3. If a cycle exists, contract it into a single super-vertex, adjusting the weight of every edge entering the cycle by subtracting the weight of the cycle-edge it would replace (this adjustment is what keeps later comparisons fair, since accepting an outside edge into the cycle means giving up exactly one already-selected cycle edge).
4. Recurse on this smaller contracted graph, then expand the cycle back out at the end, breaking it at exactly the one edge that the recursive solution's incoming arborescence edge corresponds to.

Worked Example

Consider 4 vertices where vertex \(B\)'s cheapest incoming edge is from \(C\), and \(C\)'s cheapest incoming edge is from \(B\) — a 2-cycle. Contracting \(\{B,C\}\) into a single super-vertex \(BC\), and reweighting any edge entering \(B\) or \(C\) from outside by subtracting whichever cycle-edge weight it would replace, produces a smaller acyclic problem. Solving that smaller problem and then expanding \(BC\) back out — breaking the original 2-cycle at exactly the point where the recursive solution's chosen incoming edge enters — produces the final, cycle-free minimum arborescence.

Why Cycle Contraction Works

The correctness argument shows that any optimal arborescence of the original graph, when restricted to a detected cycle, must use all-but-one of that cycle's edges (entering from exactly one outside edge, since removing exactly one edge is the minimum change needed to break a cycle into a valid tree-like path). The careful reweighting step guarantees that solving the contracted problem optimally, then re-expanding, reconstructs precisely this optimal choice — an inductive argument nearly identical in spirit to the greedy exchange arguments underlying Kruskal's and Prim's cut property, just adapted for directed cycles instead of undirected cuts.

Complexity Analysis

The original Chu-Liu/Edmonds formulation runs in \(O(VE)\); more sophisticated data structures (Tarjan's own 1977 refinement, again the same Tarjan behind Tarjan's SCC algorithm) improve this to \(O(E \log V)\):

$$\text{Time: } O(VE) \text{ (basic)} \qquad O(E\log V) \text{ (Tarjan's refinement)}$$

matching the complexity class of the undirected MST algorithms (Kruskal's, Prim's) from earlier in this series, despite the directed case requiring meaningfully more intricate bookkeeping to handle cycle contraction correctly.

Implementation

def chu_liu_edmonds(n, edges, root):
    """
    n: number of vertices. edges: list of (u, v, weight) directed edges (u -> v).
    root: the arborescence root. Returns the minimum arborescence total weight,
    or None if no arborescence rooted at `root` exists.
    """
    INF = float('inf')

    def solve(n, edges, root):
        # Step 1: cheapest incoming edge for every non-root vertex
        min_in = [INF] * n
        min_in_edge = [None] * n
        for u, v, w in edges:
            if v != root and w < min_in[v]:
                min_in[v] = w
                min_in_edge[v] = (u, v, w)

        for v in range(n):
            if v != root and min_in[v] == INF:
                return None  # unreachable, no valid arborescence

        # Step 2: detect cycles among the selected edges
        visited = [-1] * n
        cycle_id = [-1] * n
        num_cycles = 0
        for v in range(n):
            if v == root or cycle_id[v] != -1:
                continue
            path = []
            u = v
            while u != root and visited[u] == -1:
                visited[u] = v
                path.append(u)
                u = min_in_edge[u][0] if min_in_edge[u] else root
            if u != root and visited[u] == v:
                # found a new cycle
                while cycle_id[u] == -1:
                    cycle_id[u] = num_cycles
                    u = min_in_edge[u][0]
                num_cycles += 1

        if num_cycles == 0:
            return sum(min_in[v] for v in range(n) if v != root)

        # Step 3: contract cycles into super-vertices, reweight, recurse
        for v in range(n):
            if cycle_id[v] == -1:
                cycle_id[v] = num_cycles
                num_cycles += 1

        new_edges = []
        for u, v, w in edges:
            if cycle_id[u] != cycle_id[v]:
                new_w = w - (min_in[v] if min_in[v] != INF else 0)
                new_edges.append((cycle_id[u], cycle_id[v], new_w))

        base_cost = sum(min_in[v] for v in range(n) if v != root and min_in_edge[v] and cycle_id[min_in_edge[v][0]] == cycle_id[v])
        sub_result = solve(num_cycles, new_edges, cycle_id[root])
        if sub_result is None:
            return None
        return base_cost + sub_result

    return solve(n, edges, root)

edges = [(0,1,4), (0,2,8), (1,2,2), (2,1,1), (1,3,5), (2,3,3)]
print(chu_liu_edmonds(4, edges, 0))

// Simplified sketch illustrating the recursive contract-and-reweight structure.
// Production implementations (e.g. Tarjan's O(E log V) refinement) use more
// elaborate union-find and priority-queue data structures for efficiency.
#include <vector>
#include <tuple>
#include <limits>
#include <iostream>
using namespace std;

const double INF = numeric_limits<double>::infinity();

// See the Python panel for the full recursive contraction logic; the same
// three-step structure (cheapest-incoming-edge selection, cycle detection,
// contraction + reweighting + recursion) applies directly in C++.
double chuLiuEdmondsSketch(int n, vector<tuple<int,int,double>>& edges, int root) {
    vector<double> minIn(n, INF);
    vector<int> minInFrom(n, -1);
    for (auto& [u, v, w] : edges) {
        if (v != root && w < minIn[v]) { minIn[v] = w; minInFrom[v] = u; }
    }
    double total = 0;
    for (int v = 0; v < n; v++) if (v != root) total += minIn[v];
    return total;  // returns the no-cycle base case cost; full cycle handling omitted for brevity
}

int main() {
    vector<tuple<int,int,double>> edges = {
        {0,1,4},{0,2,8},{1,2,2},{2,1,1},{1,3,5},{2,3,3}
    };
    cout << chuLiuEdmondsSketch(4, edges, 0) << endl;
    return 0;
}

// Simplified sketch illustrating the recursive contract-and-reweight structure.
import java.util.*;

class ChuLiuEdmondsSketch {
    static double baseCaseCost(int n, List<int[]> edges, int root, double[] weights) {
        double[] minIn = new double[n];
        Arrays.fill(minIn, Double.POSITIVE_INFINITY);
        for (int i = 0; i < edges.size(); i++) {
            int[] e = edges.get(i);
            int u = e[0], v = e[1];
            if (v != root && weights[i] < minIn[v]) minIn[v] = weights[i];
        }
        double total = 0;
        for (int v = 0; v < n; v++) if (v != root) total += minIn[v];
        return total;  // no-cycle base case; full recursive cycle contraction omitted for brevity
    }

    public static void main(String[] args) {
        List<int[]> edges = Arrays.asList(
            new int[]{0,1}, new int[]{0,2}, new int[]{1,2},
            new int[]{2,1}, new int[]{1,3}, new int[]{2,3}
        );
        double[] weights = {4, 8, 2, 1, 5, 3};
        System.out.println(baseCaseCost(4, edges, 0, weights));
    }
}

Real-World Applications

Exercises

1. Trace through the worked example (the 2-cycle between \(B\) and \(C\)) by hand, identifying which single edge the final arborescence uses to break the cycle.
2. Explain why Kruskal's and Prim's undirected cut-property argument does not directly transfer to directed graphs, using a small example where "cheapest edge crossing a cut" creates a cycle.
3. Verify that the reweighting step (subtracting the replaced cycle edge's weight) is analogous to Johnson's algorithm's reweighting trick — what specifically is being "kept fair" in each case?
4. Challenge: Extend the base-case sketch implementation to handle a single level of cycle contraction and expansion, following the full Python implementation's logic.

Limitations