Göke, AlexanderAlexanderGökeMarx, DánielDánielMarxMnich, MatthiasMatthiasMnich2020-01-282020-01-28201911th International Conference on Algorithms and Complexity (CIAC 2019)http://hdl.handle.net/11420/4604The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp’s 21 -complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. in 2008 showed its fixed-parameter tractability via a -time algorithm, where. Here we show fixed-parameter tractability of two generalizations of DFVS: Find a smallest vertex set S such that every strong component of has size at most s: we give an algorithm solving this problem in time. Find a smallest vertex set S such that every non-trivial strong component of is 1-out-regular: we give an algorithm solving this problem in time. We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.enInformatikConference Paper10.1007/978-3-030-17402-6_21Other