The Kleitman–Wang algorithms are two different algorithms in graph theory solving the digraph realization problem, i.e. the question if there exists for a finite list of nonnegative integer pairs a simple directed graph such that its degree sequence is exactly this list. For a positive answer the list of integer pairs is called digraphic. Both algorithms construct a special solution if one exists or prove that one cannot find a positive answer. These constructions are based on recursive algorithms. Kleitman and Wang gave these algorithms in 1973.
The algorithm is based on the following theorem.
Let
S
=
(
(
a
1
,
b
1
)
,
…
,
(
a
n
,
b
n
)
)
be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let
(
a
i
,
b
i
)
be a pair of nonnegative integers with
b
i
>
0
. List
S
is digraphic if and only if the finite list
S
′
=
(
(
a
1
−
1
,
b
1
)
,
…
,
(
a
b
i
−
1
−
1
,
b
b
i
−
1
)
,
(
a
b
i
,
0
)
,
(
a
b
i
+
1
,
b
b
i
+
1
)
,
(
a
b
i
+
2
,
b
b
i
+
2
)
,
…
,
(
a
n
,
b
n
)
)
has nonnegative integer pairs and is digraphic.
Note that the pair
(
a
i
,
b
i
)
is arbitrarily with the exception of pairs
(
a
j
,
0
)
. If the given list
S
digraphic then the theorem will be applied at most
n
times setting in each further step
S
:=
S
′
. This process ends when the whole list
S
′
consists of
(
0
,
0
)
pairs. In each step of the algorithm one constructs the arcs of a digraph with vertices
v
1
,
…
,
v
n
, i.e. if it is possible to reduce the list
S
to
S
′
, then we add arcs
(
v
i
,
v
1
)
,
(
v
i
,
v
2
)
,
…
,
(
v
i
,
v
b
i
−
1
)
,
(
v
i
,
v
b
i
+
1
)
. When the list
S
cannot be reduced to a list
S
′
of nonnegative integer pairs in any step of this approach, the theorem proves that the list
S
from the beginning is not digraphic.
The algorithm is based on the following theorem.
Let
S
=
(
(
a
1
,
b
1
)
,
…
,
(
a
n
,
b
n
)
)
be a finite list of nonnegative integers such that
a
1
≥
a
2
≥
⋯
≥
a
n
and let
(
a
i
,
b
i
)
be a pair such that
(
b
i
,
a
i
)
is maximal with respect to the lexicographical order under all pairs
(
b
1
,
a
1
)
,
…
,
(
b
n
,
a
n
)
. List
S
is digraphic if and only if the finite list
S
′
=
(
(
a
1
−
1
,
b
1
)
,
⋯
,
(
a
b
i
−
1
−
1
,
b
b
i
−
1
)
,
(
a
b
i
,
0
)
,
(
a
b
i
+
1
,
b
b
i
+
1
)
,
(
a
b
i
+
2
,
b
b
i
+
2
)
,
…
,
(
a
n
,
b
n
)
)
has nonnegative integer pairs and is digraphic.
Note that the list
S
must not be in lexicographical order as in the first version. If the given list
S
is digraphic, then the theorem will be applied at most
n
times, setting in each further step
S
:=
S
′
. This process ends when the whole list
S
′
consists of
(
0
,
0
)
pairs. In each step of the algorithm, one constructs the arcs of a digraph with vertices
v
1
,
…
,
v
n
, i.e. if it is possible to reduce the list
S
to
S
′
, then one adds arcs
(
v
i
,
v
1
)
,
(
v
i
,
v
2
)
,
…
,
(
v
i
,
v
b
i
−
1
)
,
(
v
i
,
v
b
i
+
1
)
. When the list
S
cannot be reduced to a list
S
′
of nonnegative integer pairs in any step of this approach, the theorem proves that the list
S
from the beginning is not digraphic.