• Images
• Videos
• Documents
• Books
• Articles

Algorithm

Description

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

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

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

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

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

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

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

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

Running time

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

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

References

1. The algorithm is applicable to finding a minimum spanning forest with given roots. However, when searching for the minimum spanning forest among all k {\displaystyle k} -component spanning forests, a multiplier arises in the complexity of the algorithm C V k {\displaystyle C_{V}^{k}} , corresponding to the choice of a subset of vertices designated as roots. This makes it unsuitable for such a task. Even when constructing a minimum spanning tree, regardless of the root, the algorithm must be used V {\displaystyle V} times, sequentially assigning each vertex as the root. An efficient algorithm for finding minimum spanning forests that solves the root assignment problem is presented in (https://link.springer.com/article/10.1007/s10958-023-06666-w). It builds a sequence of minimal k {\displaystyle k} -component spanning forests for all k {\displaystyle k} up to the minimum spanning tree. The Chu-Liu/Edmonds algorithm is a component of it. https://link.springer.com/article/10.1007/s10958-023-06666-w ↩