{sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the {sc ${cal H}$-free SCC Deletion} problem. Here, one is given a digraph $D$, an integer $k$ and the objective is to decide whether there is a vertex set of size at most $k$ whose deletion leaves a digraph where every strong component excludes graphs in the fixed finite family ${cal H}$ as (not necessarily induced) subgraphs. When ${cal H}$ comprises only the digraph with a single arc, then this problem is precisely DFVS. Our main result is a proof that this problem is fixed-parameter tractable parameterized by the size of the deletion set if ${cal H}$ only contains rooted graphs or if ${cal H}$ contains at least one directed path. Along with generalizing the fixed-parameter tractability result for DFVS, our result also generalizes the recent results of G{o}ke et al. [CIAC 2019] for the {sc 1-Out-Regular Vertex Deletion} and {sc Bounded Size Strong Component Vertex Deletion} problems. Moreover, we design algorithms for the two above mentioned problems, whose running times are better and match with the best bounds for {sc DFVS}, without using the heavy machinery of shadow removal as is done by G{o}ke et al. [CIAC 2019].
Download