Abstract
We give an FPT algorithm for deciding whether the vertex set of 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|≥k i, where k 1,k 2 are part of the input. This settles an open problem from [1,4].
Originalsprog | Engelsk |
---|---|
Tidsskrift | Theoretical Computer Science |
Vol/bind | 844 |
Sider (fra-til) | 97-105 |
ISSN | 0304-3975 |
DOI | |
Status | Udgivet - 6. dec. 2020 |