Finding good 2-partitions of digraphs I. Hereditary properties

We study the complexity of deciding whether a given digraph D   has a vertex-partition into two disjoint subdigraphs with given structural properties. Let HH and EE denote the following two sets of natural properties of digraphs: HH = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and EE = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k1,k2k1,k2, whether a given digraph has a vertex partition into two digraphs D1,D2D1,D2 such that |V(Di)|≥ki|V(Di)|≥ki and DiDi has property PiPi for i=1,2i=1,2 when P1∈HP1∈H and P2∈H∪EP2∈H∪E. We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P1P1 and P2P2 are in EE is determined in the companion paper [2].