When I first came across the maximum branching problem, I realized it is basically the directed-graph cousin of the spanning tree problem I already knew from undirected graphs. I am writing this document to explain, in my own words, what a maximum branching is, why it matters, and how the classical algorithm (known as the Chu-Liu/Edmonds algorithm) actually finds one. A branching is a subgraph of a directed graph in which every node has at most one incoming edge and there are no cycles. When I pick the branching whose total edge weight is the largest possible, I call it a maximum branching. This idea shows up whenever I need to model hierarchical or dependency structures on directed data, such as dependency parsing in natural language processing, network routing trees, or optimal broadcast structures.
History and Background
The algorithm I am describing was developed independently by two groups of researchers. Y.J. Chu and T.H. Liu published their version in 1965, and Jack Edmonds published his in 1967. Because both arrived at essentially the same method for finding optimum (minimum or maximum) arborescences in directed graphs, the algorithm is commonly called the Chu-Liu/Edmonds algorithm. I find it interesting that this happened in the same decade as many other foundational graph algorithms, when combinatorial optimization was rapidly maturing as a field. Over the years, more efficient implementations were proposed, most notably by Tarjan in 1977, who brought the running time down using better data structures, and later by Gabow, Galil, Spencer, and Tarjan in 1986, who achieved a near-linear time bound.
Problem Statement
I want to find, in a directed, edge-weighted graph, a spanning arborescence (a directed tree rooted at a chosen vertex, where every other vertex has exactly one incoming edge and is reachable from the root) that maximizes the total weight of the selected edges. This is different from the undirected minimum/maximum spanning tree problem because edge direction matters here, and the greedy approach that works for undirected spanning trees does not directly work for directed graphs because of the possibility of cycles among the greedily chosen edges.
Core Concepts
Before I describe the mechanics, I want to lay down the terms I will keep using.
- Directed graph (digraph): a graph where edges have a direction, from one vertex to another.
- Branching: a subgraph where every vertex has in-degree at most one and no cycles exist.
- Arborescence: a branching where every vertex except a designated root has in-degree exactly one, and every vertex is reachable from the root. I think of it as a directed spanning tree.
- Maximum branching: the branching with the largest possible total edge weight, not necessarily spanning every vertex if some vertices cannot contribute positively.
- Cycle contraction: the central trick of the algorithm, where I collapse a cycle formed by greedily chosen edges into a single “super-node.”
How It Works
I approach the algorithm in the following stages, working on each vertex except the root.
- For every vertex other than the root, I select the incoming edge with the maximum weight among all its incoming edges.
- I check whether this selection of edges creates any cycles.
- If there are no cycles, I am done: the selected edges form the maximum branching.
- If a cycle exists, I contract that cycle into a single new vertex. I adjust the weights of edges entering and leaving the cycle so that they reflect the “cost” of breaking into or out of the cycle correctly.
- I repeat the process on the contracted graph until no cycles remain.
- Finally, I expand the contracted vertices back out, removing exactly one edge from each cycle (the one that gets replaced by the edge that entered the cycle from outside), to reconstruct the actual maximum branching in the original graph.
Working Principle
The internal logic rests on a simple but powerful idea: greedily picking the best incoming edge for each vertex is locally optimal, and the only way this local optimality can go wrong is if it creates a cycle. Cycles cannot appear in a valid branching, so I have to break them. Instead of naively removing an edge from the cycle (which could be suboptimal), I contract the entire cycle into a single node and let the algorithm decide, at the level of this contracted graph, which edge should “break into” the cycle from the outside. Because I adjusted the edge weights before contraction to account for what I would “give up” by not using the cycle’s own internal edge, the algorithm is guaranteed to make a globally optimal choice. This recursive contraction and re-selection is what makes the algorithm correct.
Mathematical Foundation
I formalize the graph as $G = (V, E)$ with weight function $w : E \rightarrow \mathbb{R}$. I want to find the arborescence $A \subseteq E$ rooted at $r$ that maximizes:
$$ W(A) = \sum_{e \in A} w(e) $$
subject to the constraint that every vertex $v \in V \setminus {r}$ has exactly one edge in $A$ entering it, and $A$ contains no cycles.
When I contract a cycle $C$ into a super-vertex, I adjust the weight of every edge $(u, v)$ where $v \in C$ using:
$$ w'(u, v) = w(u, v) – w(\pi(v), v) + \min_{e \in C} w(e) $$
where $\pi(v)$ is the current in-edge of $v$ within the cycle $C$. This formula preserves the relative advantage of breaking into the cycle at each possible point, which is what lets the recursive step remain correct.
Diagrams
flowchart TD
A[Start: pick best incoming edge for every non-root vertex] --> B{Does selection contain a cycle?}
B -- No --> C[Selected edges form the maximum branching]
B -- Yes --> D[Contract the cycle into a single super-vertex]
D --> E[Adjust weights of edges entering/leaving the cycle]
E --> A
Pseudocode
function MAXIMUM_BRANCHING(G, root):
for each vertex v in G, v != root:
select in-edge(v) = edge with maximum weight entering v
if selected edges form no cycle:
return selected edges as the branching
identify a cycle C among selected edges
contract C into single super-vertex vc
for each edge (u, v) entering C:
adjust weight: w'(u, v) = w(u, v) - w(in-edge(v)) + min_weight_in_cycle(C)
G' = graph after contraction
A' = MAXIMUM_BRANCHING(G', root)
expand vc back into cycle C in A'
remove the one cycle edge that is replaced by the entering edge
return expanded branching
Step-by-Step Example
I will walk through a small example with vertices {R, A, B, C} where R is the root.
Edges: R→A (weight 10), R→B (weight 2), A→B (weight 6), B→C (weight 8), C→A (weight 7).
- Best incoming edge for A: between R→A (10) and C→A (7), I pick R→A (10).
- Best incoming edge for B: between R→B (2) and A→B (6), I pick A→B (6).
- Best incoming edge for C: only B→C (8), I pick B→C (8).
- Checking for cycles: R→A, A→B, B→C — no cycle here since C→A was not selected. This already forms a valid arborescence.
- Total weight = 10 + 6 + 8 = 24, which is my maximum branching.
If instead C→A had been selected over R→A, I would have formed a cycle A→B→C→A, and I would have needed to contract that cycle and continue the algorithm recursively.
Time Complexity
The original Chu-Liu/Edmonds implementation runs in $O(VE)$ time, since in the worst case I might need to contract up to $V$ cycles, and each contraction pass costs $O(E)$ to scan all edges. Tarjan’s improved implementation using appropriate priority queue structures achieves $O(E \log V)$. The most refined version, by Gabow, Galil, Spencer, and Tarjan, achieves $O(E + V \log V)$, which is close to linear for sparse graphs.
Space Complexity
I need to store the graph itself, which takes $O(V + E)$ space. Additional space is required to track contracted super-vertices and the mapping back to original vertices, which adds another $O(V)$ in the worst case. So overall space usage is $O(V + E)$.
Correctness Analysis
The correctness of this algorithm rests on an exchange argument. I know that picking the maximum incoming edge for each vertex independently gives an upper bound on the total achievable weight, since no valid branching can do better than picking the best in-edge for every vertex. When cycles appear, I show that the contraction step preserves this upper bound property: any branching in the original graph corresponds to a branching in the contracted graph with an equivalent (or provably related) weight, because the weight adjustment formula accounts for the trade-off of using an external edge instead of an internal cycle edge. By induction on the number of contractions, the final expanded branching achieves the same weight as the optimal branching in the original graph.
Advantages
- I get an exact, optimal solution rather than an approximation.
- It generalizes the undirected maximum spanning tree problem to directed graphs.
- The near-linear time implementations make it practical even for fairly large graphs.
- It naturally handles both maximum and minimum branching problems with a simple sign flip on weights.
Disadvantages
- The basic implementation is more complex to code correctly compared to Kruskal’s or Prim’s algorithm.
- Cycle detection and contraction bookkeeping (tracking original vertices through multiple levels of contraction) adds implementation overhead.
- It is less intuitive to visualize than undirected spanning tree algorithms.
Applications
I have seen this algorithm used in dependency parsing for natural language processing, where each word in a sentence needs exactly one “head” word, and I want to maximize the total parsing score across the sentence. It is also used in network design problems where I need a directed hierarchical distribution structure, in phylogenetic tree reconstruction, and in optimal branching structures for broadcast or multicast networks where direction of data flow matters.
Implementation in C
#include <stdio.h>
#include <limits.h>
#define MAXV 100
#define INF INT_MIN
int weight[MAXV][MAXV]; /* weight[u][v] = weight of edge u->v, INF if no edge */
int n; /* number of vertices */
/* Finds the maximum branching weight using a simplified O(V^2) style
approach for teaching purposes. It repeatedly picks best in-edges
and detects/contracts cycles conceptually via union-find style marking. */
int parent[MAXV];
int visited[MAXV];
int find_best_incoming(int v, int excluded) {
int best = INF, bestU = -1;
for (int u = 0; u < n; u++) {
if (u == v || u == excluded) continue;
if (weight[u][v] > best) {
best = weight[u][v];
bestU = u;
}
}
parent[v] = bestU;
return best;
}
int has_cycle(int root) {
for (int i = 0; i < n; i++) visited[i] = 0;
for (int start = 0; start < n; start++) {
if (start == root) continue;
int v = start;
int steps = 0;
while (v != -1 && v != root && steps < n) {
if (visited[v] == start + 1) return 1; /* revisited in this walk: cycle */
visited[v] = start + 1;
v = parent[v];
steps++;
}
}
return 0;
}
int compute_maximum_branching(int root) {
int total = 0;
for (int v = 0; v < n; v++) {
if (v == root) continue;
int w = find_best_incoming(v, -1);
if (w != INF) total += w;
}
/* Note: a full production implementation contracts detected cycles and
recurses; this simplified version demonstrates the core in-edge
selection step, which is the heart of the algorithm. */
if (has_cycle(root)) {
printf("Cycle detected: full implementation would contract and recurse.\n");
}
return total;
}
int main() {
n = 4; /* vertices: 0=R, 1=A, 2=B, 3=C */
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
weight[i][j] = INF;
weight[0][1] = 10; /* R->A */
weight[0][2] = 2; /* R->B */
weight[1][2] = 6; /* A->B */
weight[2][3] = 8; /* B->C */
weight[3][1] = 7; /* C->A */
int result = compute_maximum_branching(0);
printf("Total weight of selected in-edges: %d\n", result);
return 0;
}
I kept this C implementation intentionally simplified: it shows the crucial “pick best incoming edge for each vertex” step and cycle detection, while noting where a production-grade version would perform contraction and recursion.
Sample Input and Output
Using the graph from my step-by-step example above (R→A=10, R→B=2, A→B=6, B→C=8, C→A=7), running the program gives:
Total weight of selected in-edges: 24
This matches the maximum branching weight I calculated by hand earlier.
Optimization Techniques
I can speed up the algorithm by using Fibonacci heaps or pairing heaps to maintain the incoming edges of each vertex, which is what allows Tarjan’s and later Gabow et al.’s implementations to reach near-linear time. I can also use union-find data structures with path compression to manage cycle contraction efficiently instead of rebuilding the graph explicitly at every contraction step. Lazy deletion of dominated edges (edges that can never be optimal because a better one exists into the same vertex) also reduces the amount of work per contraction.
Common Mistakes
I have noticed people often forget to adjust edge weights correctly when contracting a cycle, which silently produces a wrong answer instead of crashing, making it hard to debug. Another common mistake is not handling the case where a vertex has no incoming edges at all, which should exclude it from being spanned rather than causing an error. I also see people confuse this algorithm with the undirected minimum spanning tree algorithms and try to apply Kruskal’s greedy edge-sorting approach directly, which does not work because direction and in-degree constraints are fundamentally different here.
Further Reading
- Chu, Y.J. and Liu, T.H., “On the Shortest Arborescence of a Directed Graph,” Science Sinica, 1965.
- Edmonds, J., “Optimum Branchings,” Journal of Research of the National Bureau of Standards, 1967. https://nvlpubs.nist.gov/nistpubs/jres/71B/jresv71Bn4p233_A1b.pdf
- Tarjan, R.E., “Finding Optimum Branchings,” Networks, 1977.
- Gabow, H.N., Galil, Z., Spencer, T., Tarjan, R.E., “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica, 1986.
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., “Introduction to Algorithms,” MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Wikipedia overview of Edmonds’ algorithm: https://en.wikipedia.org/wiki/Edmonds%27_algorithm
