Mnich, MatthiasMatthiasMnichLeeuwen, Erik Jan vanErik Jan vanLeeuwen2020-01-242020-01-24201633rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)http://hdl.handle.net/11420/4574We consider the problem to find a set X of vertices (or arcs) with |X| <= k in a given digraph G such that D = G-X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains NP-hard, but we can obtain a kernel with k^{O(1)} vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.enhttps://creativecommons.org/licenses/by/3.0/directed feedback vertex/arc setparameterized algorithmskernelsInformatikConference Paperurn:nbn:de:gbv:830-882.06617510.15480/882.262510.4230/LIPIcs.STACS.2016.5510.15480/882.2625Other