מירב זהבי

In the Directed Feedback Vertex Set (DFVS) problem, given a digraph D and k∈ N, the goal is to check if there exists a set of at most k vertices whose deletion from D leaves a directed acyclic graph. Resolving the existence of a polynomial kernel for DFVS parameterized by the solution size k is a central open problem in Kernelization. In this paper, we give a polynomial kernel for DFVS parameterized by k plus the size of a treewidth- η modulator. Our choice of parameter strictly encompasses previous positive kernelization results on DFVS. Our main result is based on a novel application of the tool of important separators embedded in state-of-the-art machinery such as protrusion decompositions.