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 H and E denote the following two sets of natural properties of digraphs: H = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E = {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 k ₁,k ₂, whether a given digraph has a vertex partition into two digraphs D ₁,D ₂ such that |V(D _i)|≥k _i and D _i has property P _i for i=1,2 when P ₁∈H and P ₂∈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 P ₁ and P ₂ are in E is determined in the companion paper [2].