On the parameterized complexity of 2-partitions

Jonas Bamse Andersen; Jørgen Bang-Jensen; Anders Yeo

paper

On the parameterized complexity of 2-partitions

arXiv:2003.07190

Abstract

We give an FPT algorithm for deciding whether the vertex set a digraph $D$ can be partitioned into two disjoint sets $V_{1}, V_{2}$ such that the digraph $D [V_{1}]$ induced by $V_{1}$ has a vertex that can reach all other vertices by directed paths, the digraph $D [V_{2}]$ has no vertex of in-degree zero and $∣ V_{i} ∣ \geq k_{i}$ , where $k_{1}, k_{2}$ are part of the input. This settles an open problem from[1,4].