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 [1] gave these algorithms in 1973.
The algorithm is based on the following theorem.
Let S = ( ( a 1 , b 1 ) , … , ( a n , b n ) ) {\displaystyle S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))} be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let ( a i , b i ) {\displaystyle (a_{i},b_{i})} be a pair of nonnegative integers with b i > 0 {\displaystyle b_{i}>0} . List S {\displaystyle 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 ) ) {\displaystyle S'=((a_{1}-1,b_{1}),\dots ,(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}),\dots ,(a_{n},b_{n}))} has nonnegative integer pairs and is digraphic.
Note that the pair ( a i , b i ) {\displaystyle (a_{i},b_{i})} is arbitrarily with the exception of pairs ( a j , 0 ) {\displaystyle (a_{j},0)} . If the given list S {\displaystyle S} digraphic then the theorem will be applied at most n {\displaystyle n} times setting in each further step S := S ′ {\displaystyle S:=S'} . This process ends when the whole list S ′ {\displaystyle S'} consists of ( 0 , 0 ) {\displaystyle (0,0)} pairs. In each step of the algorithm one constructs the arcs of a digraph with vertices v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} , i.e. if it is possible to reduce the list S {\displaystyle S} to S ′ {\displaystyle 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 ) {\displaystyle (v_{i},v_{1}),(v_{i},v_{2}),\dots ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})} . When the list S {\displaystyle S} cannot be reduced to a list S ′ {\displaystyle S'} of nonnegative integer pairs in any step of this approach, the theorem proves that the list S {\displaystyle S} from the beginning is not digraphic.
Let S = ( ( a 1 , b 1 ) , … , ( a n , b n ) ) {\displaystyle S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))} be a finite list of nonnegative integers such that a 1 ≥ a 2 ≥ ⋯ ≥ a n {\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}} and let ( a i , b i ) {\displaystyle (a_{i},b_{i})} be a pair such that ( b i , a i ) {\displaystyle (b_{i},a_{i})} is maximal with respect to the lexicographical order under all pairs ( b 1 , a 1 ) , … , ( b n , a n ) {\displaystyle (b_{1},a_{1}),\dots ,(b_{n},a_{n})} . List S {\displaystyle 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 ) ) {\displaystyle S'=((a_{1}-1,b_{1}),\cdots ,(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}),\dots ,(a_{n},b_{n}))} has nonnegative integer pairs and is digraphic.
Note that the list S {\displaystyle S} must not be in lexicographical order as in the first version. If the given list S {\displaystyle S} is digraphic, then the theorem will be applied at most n {\displaystyle n} times, setting in each further step S := S ′ {\displaystyle S:=S'} . This process ends when the whole list S ′ {\displaystyle S'} consists of ( 0 , 0 ) {\displaystyle (0,0)} pairs. In each step of the algorithm, one constructs the arcs of a digraph with vertices v 1 , … , v n {\displaystyle v_{1},\dots ,v_{n}} , i.e. if it is possible to reduce the list S {\displaystyle S} to S ′ {\displaystyle 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 ) {\displaystyle (v_{i},v_{1}),(v_{i},v_{2}),\dots ,(v_{i},v_{b_{i}-1}),(v_{i},v_{b_{i}+1})} . When the list S {\displaystyle S} cannot be reduced to a list S ′ {\displaystyle S'} of nonnegative integer pairs in any step of this approach, the theorem proves that the list S {\displaystyle S} from the beginning is not digraphic.