Edmonds' algorithm

{{Short description|Algorithm for the directed version of the minimum spanning tree problem}}

{{about|the optimum branching algorithm|the maximum matching algorithm|Blossom 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). The algorithm is applicable to finding a minimum spanning forest with given roots. However, when searching for the minimum spanning forest among all $k$ -component spanning forests, a multiplier arises in the complexity of the algorithm

$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$ 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$ -component spanning forests for all $k$ up to the minimum spanning tree. The Chu-Liu/Edmonds algorithm is a component of it.

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_{e \in A}{w(e)}$ .

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 = \{(\pi(v),v) \mid v \in V \setminus \{ r \} \}$ 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=Yeong-Jin |last1=Chu |first2=Tseng-Hong |last2 = Liu |title= On the Shortest Arborescence of a Directed Graph |journal=Scientia Sinica |volume=XIV |issue=10 |year= 1965| pages=1396–1400 | url =https://github.com/jungyeul/chu-liu-1965/blob/main/chu-liu-1965.pdf}}
{{citation | first1=J. |last1=Edmonds |title=Optimum Branchings | journal= Journal of Research of the National Bureau of Standards Section B | volume=71B |issue=4 |year= 1967 |pages=233–240 | doi=10.6028/jres.071b.032|doi-access=free }}
{{citation | first1=R. E.|last1=Tarjan |author1-link=Robert Tarjan|title=Finding Optimum Branchings | journal =Networks | volume=7 |year=1977 | pages=25–35 | doi=10.1002/net.3230070103}}
{{citation | first1=P.M.|last1= Camerini |first2= L. |last2=Fratta | first3 =F. |last3= Maffioli |title=A note on finding optimum branchings | journal=Networks | volume=9 |issue= 4 |year= 1979| pages=309–312 | doi=10.1002/net.3230090403}}
{{citation | first1=Alan |last1= Gibbons |title=Algorithmic Graph Theory | publisher=Cambridge University press | year=1985 |isbn= 0-521-28881-9 }}
{{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}}
{{citation | first1=V. |last1=Buslov |title=Algorithm for Sequential Construction of Spanning Minimal Directed Forests | journal= Journal of Mathematical Sciences | volume=275 |year= 2023 |pages=117-129 | doi=10.1007/s10958-023-06666-w|doi-access=free }}

External links

[https://github.com/atofigh/edmonds-alg/ 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 [https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.tree.branchings.Edmonds.html Edmonds' Algorithm].
[https://pypi.org/project/spanning-forest-builder/ (spanning-forest-builder 0.0.2)] – Library for constructing oriented forests of minimum weight.

Category:Graph algorithms