## Abstract

Given a network modeled by a directed graph D=(V,A), it is natural to ask whether we can partition the vertex set of D into two disjoint subsets V_{1},V_{2} (called a 2-partition), such that the digraphs D[V_{1}],D[V_{2}] induced by each of these has one of the two properties of interest. This question gives rise to a rich realm of combinatorial problems. The complexity of many such problems was determined in [2,3]. We analyze a subset of those problems from the viewpoint of parameterized complexity, and present a complete dichotomy of basic, natural properties. More precisely, given a directed graph D=(V,A) and two non-negative integers k_{1} and k_{2}, we seek a 2-partition (V_{1},V_{2}) of the vertex set V such that |V_{1}|≥k_{1}, |V_{2}|≥k_{2}, and each of the subdigraphs induced by V_{1} and V_{2} has a structural property as defined by the problem at hand—for example, D[V_{1}] is acyclic and D[V_{2}] is strongly connected. Specifically, we consider the following eight structural properties: being strongly connected; being connected; having an out-branching; having an in-branching; having minimum degree at least one; having minimum semi-degree at least one; being acyclic; and being complete.

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

Journal | Theoretical Computer Science |

Volume | 795 |

Pages (from-to) | 108-114 |

Number of pages | 7 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 26. Nov 2019 |

## Keywords

- 2-Partition
- Digraph partitioning
- Directed graphs
- Parameterized complexity