Out-degree reducing partitions of digraphs

Abstract Let k be a fixed integer. We determine the complexity of finding a p -partition ( V 1 , … , V p ) of the vertex set of a given digraph such that the maximum out-degree of each of the digraphs induced by V i , ( 1 ≤ i ≤ p ) is at least k smaller than the maximum out-degree of D . We show that this problem is polynomial-time solvable when p ≥ 2 k and NP -complete otherwise. The result for k = 1 and p = 2 answers a question posed in [3] . We also determine, for all fixed non-negative integers k 1 , k 2 , p , the complexity of deciding whether a given digraph of maximum out-degree p has a 2-partition ( V 1 , V 2 ) such that the digraph induced by V i has maximum out-degree at most k i for i ∈ [ 2 ] . It follows from this characterization that the problem of deciding whether a digraph has a 2-partition ( V 1 , V 2 ) such that each vertex v ∈ V i has at least as many neighbours in the set V 3 − i as in V i , for i = 1 , 2 is NP -complete. This solves a problem from [6] on majority colourings.