Edmonds' algorithm

In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an ''optimum branching'').
It is the directed analog of the minimum spanning tree problem.
The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).

Algorithm

Description

The algorithm takes as input a directed graph $D = \langle V, E \rangle$ where $V$ is the set of nodes and $E$ is the set of directed edges, a distinguished vertex $r \in V$ called the ''root'', and a real-valued weight $w(e)$ for each edge $e \in E$.
It returns a spanning arborescence $A$ rooted at $r$ of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, $w(A) = \sum_$.

The algorithm has a recursive description.
Let $f(D, r, w)$ denote the function which returns a spanning arborescence rooted at $r$ of minimum weight.
We first remove any edge from $E$ whose destination is $r$.
We may also 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, find the edge incoming to $v$ of lowest weight (with ties broken arbitrarily).
Denote the source of this edge by $\pi(v)$.
If the set of edges $P = \$ does not contain any cycles, then $f(D,r,w) = P$.

Otherwise, $P$ contains at least one cycle.
Arbitrarily choose one of these cycles and call it $C$.
We now define a new weighted directed graph $D^\prime = \langle V^\prime, E^\prime \rangle$ in which the cycle $C$ is "contracted" into one node as follows:

The nodes of $V^\prime$ are the nodes of $V$ not in $C$ plus a ''new'' node denoted $v_C$.

* If $(u,v)$ is an edge in $E$ with $u\notin C$ and $v\in C$ (an edge coming into the cycle), then include in $E^\prime$ a new edge $e = (u, v_C)$, and define $w^\prime(e) = w(u,v) - w(\pi(v),v)$.
* If $(u,v)$ is an edge in $E$ with $u\in C$ and $v\notin C$ (an edge going away from the cycle), then include in $E^\prime$ a new edge $e = (v_C, v)$, and define $w^\prime(e) = w(u,v)$.
* If $(u,v)$ is an edge in $E$ with $u\notin C$ and $v\notin C$ (an edge unrelated to the cycle), then include in $E^\prime$ a new edge $e = (u, v)$, and define $w^\prime(e) = w(u,v)$.

For each edge in $E^\prime$, we remember which edge in $E$ it corresponds to.

Now find a minimum spanning arborescence $A^\prime$ of $D^\prime$ using a call to $f(D^\prime, r,w^\prime)$.
Since $A^\prime$ is a spanning arborescence, each vertex has exactly one incoming edge.
Let $(u, v_C)$ be the unique incoming edge to $v_C$ in $A^\prime$.
This edge corresponds to an edge $(u,v) \in E$ with $v \in C$.
Remove the edge $(\pi(v),v)$ from $C$, breaking the cycle.
Mark each remaining edge in $C$.
For each edge in $A^\prime$, mark its corresponding edge in $E$.
Now we define $f(D, r, w)$ to be the set of marked edges, which form a minimum spanning arborescence.

Observe that $f(D, r, w)$ is defined in terms of $f(D^\prime, r, w^\prime)$, with $D^\prime$ having strictly fewer vertices than $D$. Finding $f(D, r, w)$ for a single-vertex graph is trivial (it is just $D$ itself), so the recursive algorithm is guaranteed to terminate.

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)$.

References

*
*
*
*
*
* {{citation , first1=H. N. , last1=Gabow, author1-link=Harold N. Gabow , first2=Z., last2=Galil, author2-link=Zvi Galil , first3=T., last3=Spencer , first4=R. E., last4=Tarjan , author4-link=Robert Tarjan , title=Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, journal= Combinatorica , volume=6 , issue=2 , year=1986, pages= 109–122 , doi=10.1007/bf02579168, s2cid=35618095

External links

Edmonds's algorithm ( edmonds-alg )
– An implementation of Edmonds's algorithm written in C++ and licensed under the MIT License. This source is using Tarjan's implementation for the dense graph.
*NetworkX, a python library distributed under BSD, has an implementation o
Edmonds' Algorithm

Graph algorithms