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 [math]\displaystyle{ D = \langle V, E \rangle }[/math] where [math]\displaystyle{ V }[/math] is the set of nodes and [math]\displaystyle{ E }[/math] is the set of directed edges, a distinguished vertex [math]\displaystyle{ r \in V }[/math] called the root, and a real-valued weight [math]\displaystyle{ w(e) }[/math] for each edge [math]\displaystyle{ e \in E }[/math]. It returns a spanning arborescence [math]\displaystyle{ A }[/math] rooted at [math]\displaystyle{ r }[/math] of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, [math]\displaystyle{ w(A) = \sum_{e \in A}{w(e)} }[/math].
The algorithm has a recursive description. Let [math]\displaystyle{ f(D, r, w) }[/math] denote the function which returns a spanning arborescence rooted at [math]\displaystyle{ r }[/math] of minimum weight. We first remove any edge from [math]\displaystyle{ E }[/math] whose destination is [math]\displaystyle{ r }[/math]. 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 [math]\displaystyle{ v }[/math] other than the root, find the edge incoming to [math]\displaystyle{ v }[/math] of lowest weight (with ties broken arbitrarily). Denote the source of this edge by [math]\displaystyle{ \pi(v) }[/math]. If the set of edges [math]\displaystyle{ P = \{(\pi(v),v) \mid v \in V \setminus \{ r \} \} }[/math] does not contain any cycles, then [math]\displaystyle{ f(D,r,w) = P }[/math].
Otherwise, [math]\displaystyle{ P }[/math] contains at least one cycle. Arbitrarily choose one of these cycles and call it [math]\displaystyle{ C }[/math]. We now define a new weighted directed graph [math]\displaystyle{ D^\prime = \langle V^\prime, E^\prime \rangle }[/math] in which the cycle [math]\displaystyle{ C }[/math] is "contracted" into one node as follows:
The nodes of [math]\displaystyle{ V^\prime }[/math] are the nodes of [math]\displaystyle{ V }[/math] not in [math]\displaystyle{ C }[/math] plus a new node denoted [math]\displaystyle{ v_C }[/math].
- If [math]\displaystyle{ (u,v) }[/math] is an edge in [math]\displaystyle{ E }[/math] with [math]\displaystyle{ u\notin C }[/math] and [math]\displaystyle{ v\in C }[/math] (an edge coming into the cycle), then include in [math]\displaystyle{ E^\prime }[/math] a new edge [math]\displaystyle{ e = (u, v_C) }[/math], and define [math]\displaystyle{ w^\prime(e) = w(u,v) - w(\pi(v),v) }[/math].
- If [math]\displaystyle{ (u,v) }[/math] is an edge in [math]\displaystyle{ E }[/math] with [math]\displaystyle{ u\in C }[/math] and [math]\displaystyle{ v\notin C }[/math] (an edge going away from the cycle), then include in [math]\displaystyle{ E^\prime }[/math] a new edge [math]\displaystyle{ e = (v_C, v) }[/math], and define [math]\displaystyle{ w^\prime(e) = w(u,v) }[/math].
- If [math]\displaystyle{ (u,v) }[/math] is an edge in [math]\displaystyle{ E }[/math] with [math]\displaystyle{ u\notin C }[/math] and [math]\displaystyle{ v\notin C }[/math] (an edge unrelated to the cycle), then include in [math]\displaystyle{ E^\prime }[/math] a new edge [math]\displaystyle{ e = (u, v) }[/math], and define [math]\displaystyle{ w^\prime(e) = w(u,v) }[/math].
For each edge in [math]\displaystyle{ E^\prime }[/math], we remember which edge in [math]\displaystyle{ E }[/math] it corresponds to.
Now find a minimum spanning arborescence [math]\displaystyle{ A^\prime }[/math] of [math]\displaystyle{ D^\prime }[/math] using a call to [math]\displaystyle{ f(D^\prime, r,w^\prime) }[/math]. Since [math]\displaystyle{ A^\prime }[/math] is a spanning arborescence, each vertex has exactly one incoming edge. Let [math]\displaystyle{ (u, v_C) }[/math] be the unique incoming edge to [math]\displaystyle{ v_C }[/math] in [math]\displaystyle{ A^\prime }[/math]. This edge corresponds to an edge [math]\displaystyle{ (u,v) \in E }[/math] with [math]\displaystyle{ v \in C }[/math]. Remove the edge [math]\displaystyle{ (\pi(v),v) }[/math] from [math]\displaystyle{ C }[/math], breaking the cycle. Mark each remaining edge in [math]\displaystyle{ C }[/math]. For each edge in [math]\displaystyle{ A^\prime }[/math], mark its corresponding edge in [math]\displaystyle{ E }[/math]. Now we define [math]\displaystyle{ f(D, r, w) }[/math] to be the set of marked edges, which form a minimum spanning arborescence.
Observe that [math]\displaystyle{ f(D, r, w) }[/math] is defined in terms of [math]\displaystyle{ f(D^\prime, r, w^\prime) }[/math], with [math]\displaystyle{ D^\prime }[/math] having strictly fewer vertices than [math]\displaystyle{ D }[/math]. Finding [math]\displaystyle{ f(D, r, w) }[/math] for a single-vertex graph is trivial (it is just [math]\displaystyle{ D }[/math] itself), so the recursive algorithm is guaranteed to terminate.
Running time
The running time of this algorithm is [math]\displaystyle{ O(EV) }[/math]. A faster implementation of the algorithm due to Robert Tarjan runs in time [math]\displaystyle{ O(E \log V) }[/math] for sparse graphs and [math]\displaystyle{ O(V^2) }[/math] 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 [math]\displaystyle{ O(E + V \log V) }[/math].
References
- Chu, Yeong-Jin; Liu, Tseng-Hong (1965), "On the Shortest Arborescence of a Directed Graph", Scientia Sinica: Chung-kuo k`o hsueh XIV (10): 1396–1400, https://github.com/jungyeul/chu-liu-1965/blob/main/chu-liu-1965.pdf
- 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
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.
![]() | Original source: https://en.wikipedia.org/wiki/Edmonds' algorithm.
Read more |