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

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

.

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.

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

$$

O

(

E

+

V

log

V

)

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

.