TY - JOUR

T1 - The parameterized complexity landscape of finding 2-partitions of digraphs

AU - Bang-Jensen, J.

AU - Knudsen, Kristine V.K.

AU - Saurabh, Saket

AU - Zehavi, Meirav

PY - 2019/11/26

Y1 - 2019/11/26

N2 - 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 V1,V2 (called a 2-partition), such that the digraphs D[V1],D[V2] 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 k1 and k2, we seek a 2-partition (V1,V2) of the vertex set V such that |V1|≥k1, |V2|≥k2, and each of the subdigraphs induced by V1 and V2 has a structural property as defined by the problem at hand—for example, D[V1] is acyclic and D[V2] 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.

AB - 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 V1,V2 (called a 2-partition), such that the digraphs D[V1],D[V2] 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 k1 and k2, we seek a 2-partition (V1,V2) of the vertex set V such that |V1|≥k1, |V2|≥k2, and each of the subdigraphs induced by V1 and V2 has a structural property as defined by the problem at hand—for example, D[V1] is acyclic and D[V2] 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.

KW - 2-Partition

KW - Digraph partitioning

KW - Directed graphs

KW - Parameterized complexity

U2 - 10.1016/j.tcs.2019.05.037

DO - 10.1016/j.tcs.2019.05.037

M3 - Journal article

AN - SCOPUS:85068543239

SN - 0304-3975

VL - 795

SP - 108

EP - 114

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -