A Polynomial Kernel for Funnel Arc Deletion Set

AbstractIn Directed Feedback Arc Set (DFAS) we search for a set of at most k arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider $$\mathcal {C}$$ C -Arc Deletion Set ($$\mathcal {C}$$ C -ADS), a variant of DFAS where we want to remove at most k arcs from the input digraph in order to turn it into a digraph of a class $$\mathcal {C}$$ C . In this work, we choose $$\mathcal {C}$$ C to be the class of funnels. Funnel-ADS is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to k. So far no polynomial kernels for this problem were known. Our main result is a kernel for Funnel-ADS with $$\mathcal {O}(k^6)$$ O ( k 6 ) many vertices and $$\mathcal {O}(k^7)$$ O ( k 7 ) many arcs, computable in $$\mathcal {O}(nm)$$ O ( n m ) time, where n is the number of vertices and m the number of arcs in the input digraph.