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.
