# Edmonds’ algorithm

Posted by admin on February 13, 2018 in Uncategorized |

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

The algorithm takes as input a directed graph

${\displaystyle D=\langle V,E\rangle }$

D

=

V

,

E

{\displaystyle D=\langle V,E\rangle }

where

${\displaystyle V}$

V

{\displaystyle V}

is the set of nodes and

${\displaystyle E}$

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

${\displaystyle w(e)}$

w

(

e

)

{\displaystyle w(e)}

for each edge

${\displaystyle e\in E}$

e

E

{\displaystyle e\in E}

. It returns a spanning arborescence

${\displaystyle A}$

A

{\displaystyle A}

rooted at

${\displaystyle r}$

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

w

(

A

)

=

e

A

w

(

e

)

{\displaystyle w(A)=\sum _{e\in A}{w(e)}}

.

The algorithm has a recursive description. Let

${\displaystyle f(D,r,w)}$

f

(

D

,

r

,

w

)

{\displaystyle f(D,r,w)}

denote the function which returns a spanning arborescence rooted at

${\displaystyle r}$

r

{\displaystyle r}

of minimum weight. We first remove any edge from

${\displaystyle E}$

E

{\displaystyle E}

whose destination is

${\displaystyle r}$

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}$

v

{\displaystyle v}

other than the root, find the edge incoming to

${\displaystyle v}$

v

{\displaystyle v}

of lowest weight (with ties broken arbitrarily). Denote the source of this edge by

${\displaystyle \pi (v)}$

π

(

v

)

{\displaystyle \pi (v)}

. If the set of edges

${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$

P

=

{

(

π

(

v

)

,

v

)

v

V

{

r

}

}

{\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}

does not contain any cycles, then

${\displaystyle f(D,r,w)=P}$

f

(

D

,

r

,

w

)

=

P

{\displaystyle f(D,r,w)=P}

.

Otherwise,

${\displaystyle P}$

P

{\displaystyle P}

contains at least one cycle. Arbitrarily choose one of these cycles and call it

${\displaystyle C}$

C

{\displaystyle C}

. We now define a new weighted directed graph

${\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }$

D

=

V

,

E

{\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }

in which the cycle

${\displaystyle C}$

C

{\displaystyle C}

is “contracted” into one node as follows:

The nodes of

${\displaystyle V^{\prime }}$

V

{\displaystyle V^{\prime }}

are the nodes of

${\displaystyle V}$

V

{\displaystyle V}

not in

${\displaystyle C}$

C

{\displaystyle C}

plus a new node denoted

${\displaystyle v_{C}}$

v

C

{\displaystyle v_{C}}

.

For each edge in

${\displaystyle E^{\prime }}$

E

{\displaystyle E^{\prime }}

, we remember which edge in

${\displaystyle E}$

E

{\displaystyle E}

it corresponds to.

Now find a minimum spanning arborescence

${\displaystyle A^{\prime }}$

A

{\displaystyle A^{\prime }}

of

${\displaystyle D^{\prime }}$

D

{\displaystyle D^{\prime }}

using a call to

${\displaystyle f(D^{\prime },r,w^{\prime })}$

f

(

D

,

r

,

w

)

{\displaystyle f(D^{\prime },r,w^{\prime })}

. Since

${\displaystyle A^{\prime }}$

A

{\displaystyle A^{\prime }}

is a spanning arborescence, each vertex has exactly one incoming edge. Let

${\displaystyle (u,v_{C})}$

(

u

,

v

C

)

{\displaystyle (u,v_{C})}

be the unique incoming edge to

${\displaystyle v_{C}}$

v

C

{\displaystyle v_{C}}

in

${\displaystyle A^{\prime }}$

A

{\displaystyle A^{\prime }}

. This edge corresponds to an edge

${\displaystyle (u,v)\in E}$

(

u

,

v

)

E

{\displaystyle (u,v)\in E}

with

${\displaystyle v\in C}$

v

C

{\displaystyle v\in C}

. Remove the edge

${\displaystyle (\pi (v),v)}$

(

π

(

v

)

,

v

)

{\displaystyle (\pi (v),v)}

from

${\displaystyle C}$

C

{\displaystyle C}

, breaking the cycle. Mark each remaining edge in

${\displaystyle C}$

C

{\displaystyle C}

. For each edge in

${\displaystyle A^{\prime }}$

A

{\displaystyle A^{\prime }}

, mark its corresponding edge in

${\displaystyle E}$

E

{\displaystyle E}

. Now we define

${\displaystyle f(D,r,w)}$

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

f

(

D

,

r

,

w

)

{\displaystyle f(D,r,w)}

is defined in terms of

${\displaystyle f(D^{\prime },r,w^{\prime })}$

f

(

D

,

r

,

w

)

{\displaystyle f(D^{\prime },r,w^{\prime })}

, with

${\displaystyle D^{\prime }}$

D

{\displaystyle D^{\prime }}

having strictly fewer vertices than

${\displaystyle D}$

D

{\displaystyle D}

. Finding

${\displaystyle f(D,r,w)}$

f

(

D

,

r

,

w

)

{\displaystyle f(D,r,w)}

for a single-vertex graph is trivial (it is just

${\displaystyle D}$

D

{\displaystyle D}

itself), so the recursive algorithm is guaranteed to terminate.

The running time of this algorithm is

${\displaystyle O(EV)}$

O

(

E

V

)

{\displaystyle O(EV)}

. A faster implementation of the algorithm due to Robert Tarjan runs in time

${\displaystyle O(E\log V)}$

O

(

E

log

V

)

{\displaystyle O(E\log V)}

for sparse graphs and

${\displaystyle O(V^{2})}$

O

(

V

2

)

{\displaystyle O(V^{2})}

${\displaystyle O(E+V\log V)}$

O

(

E

+

V

log

V

)

{\displaystyle O(E+V\log V)}

.