## Abstract

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
_{1},k
_{2}, whether a given digraph has a vertex partition into two digraphs D
_{1},D
_{2} such that |V(D
_{i})|≥k
_{i} and D
_{i} has property P
_{i} for i=1,2 when P
_{1}∈H and P
_{2}∈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
_{1} and P
_{2} are in E is determined in the companion paper [2].

Original language | English |
---|---|

Journal | Theoretical Computer Science |

Volume | 636 |

Issue number | C |

Pages (from-to) | 85-94 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 2016 |

## Keywords

- 2-partition
- Acyclic
- Feedback vertex set
- Minimum degree
- NP-complete
- Oriented
- Out-branching
- Partition
- Polynomial
- Semicomplete digraph
- Splitting digraphs
- Tournament