# Edmonds' algorithm

In graph theory, a branch of mathematics, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a maximum or minimum optimum branchings. This is similar to the minimum spanning tree problem which concerns undirected graphs. However, when nodes are connected by weighted edges that are directed, a minimum spanning tree algorithm cannot be used.

The optimum branching algorithm was proposed independently first by Yoeng-jin Chu and Tseng-hong Liu (1965) and then by Edmonds (1967). To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased. A minimum path length is found by starting from the smallest value.

## Running time

The running time of this algorithm is $O(EV)$. A faster implementation of the algorithm due to Robert Tarjan runs in time $O(E \log V)$ for sparse graphs and $O(V^2)$ for dense graphs. This is as fast as Prim's algorithm for an undirected minimum spanning tree. In 1986, Gabow, Galil, Spencer, and Tarjan produced a faster implementation, with running time $O(E + V \log V)$.

## Algorithm

### Description

The algorithm has a conceptual recursive description. We will denote by $f$ the function which, given a weighted directed graph $D$ with a distinguished vertex $r$ called the root, returns a spanning tree rooted at $r$ of minimal cost.

The precise description is as follows. Given a weighted directed graph $D$ with root $r$ we first replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges.

Now, for each node $v$ other than the root, mark an (arbitrarily chosen) incoming edge of lowest cost. Denote the other endpoint of this edge by $\pi(v)$. The edge is now denoted as $(\pi(v),v)$ with associated cost $w(\pi(v),v)$. If the marked edges form an SRT (Shortest Route Tree), $f(D)$ is defined to be this SRT. Otherwise, the set of marked edges form at least one cycle. Call (an arbitrarily chosen) one of these cycles $C$. We now define a weighted directed graph $D^\prime$ having a root $r^\prime$ as follows. The nodes of $D^\prime$ are the nodes of $D$ not in $C$ plus a new node denoted $v_C$.

If $(u,v)$ is an edge in $D$ with $u\notin C$ and $v\in C$, then include in $D^\prime$ the edge $e = (u, v_C)$, and define $w(e) = w(u,v) - w(\pi(v),v)$.

If $(u,v)$ is an edge in $D$ with $u\in C$ and $v\notin C$, then include in $D^\prime$ the edge $e = (v_C, v)$, and define $w(e) = w(u,v)$.

If $(u,v)$ is an edge in $D$ with $u\notin C$ and $v\notin C$, then include in $D^\prime$ the edge $e = (u, v)$, and define $w(e) = w(u,v)$.

We include no other edges in $D^\prime$.

The root $r^\prime$ of $D^\prime$ is simply the root $r$ in $D$.

Using a call to $f(D^\prime)$, find an SRT of $D^\prime$. First, mark in $D$ all shared edges with $D^\prime$ that are marked in the SRT of $D^\prime$. Also, mark in $D$ all the edges in $C$. Now, suppose that in the SRT of $D^\prime$, the (unique) incoming edge at $v_C$ is $(u, v_C)$. This edge comes from some pair $(u,v)$ with $u\notin C$ and $v\in C$. Unmark $(\pi(v),v)$ and mark $(u,v)$. Also, for each marked $(v_C,v)$ in the SRT of $D^\prime$ and coming from an edge $(u,v)$ in $D$ with $u\in C$ and $v\notin C$, mark the edge $(u,v)$. Now the set of marked edges do form an SRT, which we define to be the value of $f(D)$.

Observe that $f(D)$ is defined in terms of $f(D^\prime)$ for weighted directed rooted graphs $D^\prime$ having strictly fewer vertices than $D$, and finding $f(D)$ for a single-vertex graph is trivial.

### Implementation

Let BV be a vertex bucket and BE be an edge bucket. Let v be a vertex and e be an edge of maximum positive weight that is incident to v. Ci is a circuit. G0 = (V0,E0) is the original digraph. ui is a replacement vertex for Ci.

$BV \leftarrow BE \leftarrow \varnothing$
i=0A:
if $BV = V_i$ then goto B
for some vertex $v \notin BV$ and $v \in V_i$ {
$BV \leftarrow BV \cup \lbrace v\rbrace$
find an edge $e = (x,v)$ such that w(e) = max{ w(y,v)|(y,v) $\in$ Ei}
if w(e) ≤ 0 then goto A
}
if $BE \cup \lbrace e\rbrace$ contains a circuit {
i=i+1
construct $G_i$ by shrinking $C_i$ to $u_i$
modify BE, BV and some edge weights
}
$BE \leftarrow BE \cup {e}$
goto AB:
while i ≠ 0 {
reconstruct $G_{i-1}$ and rename some edges in BE
if $u_i$ was a root of an out-tree in BE {
$BE \leftarrow BE \cup \lbrace e|e \in C_i$ and $e \ne e_0^i\rbrace$
}else{
$BE \leftarrow BE \cup \lbrace e|e \in C_i$ and $e \ne \tilde{e}_i\rbrace$
}
i=i-1
}
Maximum branching weight = $\sum_{e \in BE} w(e)$



## References

• Chu, Y. J.; Liu, T. H. (1965), "On the Shortest Arborescence of a Directed Graph", Science Sinica 14: 1396–1400
• Edmonds, J. (1967), "Optimum Branchings", J. Res. Nat. Bur. Standards 71B: 233–240
• Tarjan, R. E. (1977), "Finding Optimum Branchings", Networks 7: 25–35
• Camerini, P.M.; Fratta, L.; Maffioli, F. (1979), "A note on finding optimum branchings", Networks 9: 309–312
• Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University press, ISBN 0-521-28881-9
• Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986), "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs", Combinatorica 6: 109–122