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
⟩
where
V
is the set of nodes and
E
is the set of directed edges, a distinguished vertex
r
∈
V
called the root, and a real-valued weight
w
(
e
)
for each edge
e
∈
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
)
=
∑
e
∈
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
π
(
v
)
. If the set of edges
P
=
{
(
π
(
v
)
,
v
)
∣
v
∈
V
∖
{
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
′
=
⟨
V
′
,
E
′
⟩
in which the cycle
C
is "contracted" into one node as follows:
The nodes of
V
′
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
∉
C
and
v
∈
C
(an edge coming into the cycle), then include in
E
′
a new edge
e
=
(
u
,
v
C
)
, and define
w
′
(
e
)
=
w
(
u
,
v
)
−
w
(
π
(
v
)
,
v
)
.
If
(
u
,
v
)
is an edge in
E
with
u
∈
C
and
v
∉
C
(an edge going away from the cycle), then include in
E
′
a new edge
e
=
(
v
C
,
v
)
, and define
w
′
(
e
)
=
w
(
u
,
v
)
.
If
(
u
,
v
)
is an edge in
E
with
u
∉
C
and
v
∉
C
(an edge unrelated to the cycle), then include in
E
′
a new edge
e
=
(
u
,
v
)
, and define
w
′
(
e
)
=
w
(
u
,
v
)
.
For each edge in
E
′
, we remember which edge in
E
it corresponds to.
Now find a minimum spanning arborescence
A
′
of
D
′
using a call to
f
(
D
′
,
r
,
w
′
)
. Since
A
′
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
′
. This edge corresponds to an edge
(
u
,
v
)
∈
E
with
v
∈
C
. Remove the edge
(
π
(
v
)
,
v
)
from
C
, breaking the cycle. Mark each remaining edge in
C
. For each edge in
A
′
, 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
′
,
r
,
w
′
)
, with
D
′
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.
The running time of this algorithm is
O
(
E
V
)
. 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
)
.
