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).^[1] 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).

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

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

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

The nodes of ${\displaystyle V^{\prime }}${\displaystyle V^{\prime }} are the nodes of ${\displaystyle V}${\displaystyle V} not in ${\displaystyle C}${\displaystyle C} plus a new node denoted ${\displaystyle v_{C}}${\displaystyle v_{C}}.

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

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

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

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

The running time of this algorithm is ${\displaystyle O(EV)}${\displaystyle O(EV)}. A faster implementation of the algorithm due to Robert Tarjan runs in time ${\displaystyle O(E\log V)}${\displaystyle O(E\log V)} for sparse graphs and ${\displaystyle O(V^{2})}${\displaystyle 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 ${\displaystyle O(E+V\log V)}${\displaystyle O(E+V\log V)}.

• Chu, Yeong-Jin; Liu, Tseng-Hong (1965), "On the Shortest Arborescence of a Directed Graph" (PDF), Scientia Sinica, XIV (10): 1396–1400
• Edmonds, J. (1967), "Optimum Branchings", Journal of Research of the National Bureau of Standards Section B, 71B (4): 233–240, doi:10.6028/jres.071b.032
• Tarjan, R. E. (1977), "Finding Optimum Branchings", Networks, 7: 25–35, doi:10.1002/net.3230070103
• Camerini, P.M.; Fratta, L.; Maffioli, F. (1979), "A note on finding optimum branchings", Networks, 9 (4): 309–312, doi:10.1002/net.3230090403
• 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 (2): 109–122, doi:10.1007/bf02579168, S2CID 35618095
• Buslov, V. (2023), "Algorithm for Sequential Construction of Spanning Minimal Directed Forests", Journal of Mathematical Sciences, 275: 117–129, doi:10.1007/s10958-023-06666-w

• 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 of Edmonds' Algorithm.
• (spanning-forest-builder 0.0.2) – Library for constructing oriented forests of minimum weight.

• Graph algorithms

• Articles with short description
• Short description is different from Wikidata