Out-degree reducing partitions of digraphs

Let k be a fixed integer. We determine the complexity of finding a p-partition (V₁,…,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≥2k 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₁,k₂,p, the complexity of deciding whether a given digraph of maximum out-degree p has a 2-partition (V₁,V₂) 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₁,V₂) 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.