Prof. Meirav Zehavi

In the Directed Feedback Vertex Set (DFVS) problem, given a digraph D and a positive integer k, the goal is to check if there exists a set of at most k vertices whose deletion from D results in a directed acyclic graph. The existence of a polynomial kernel for DFVS, parameterized by the solution size k, is a central open problem in kernelization. In this article, we give a polynomial kernel for DFVS parameterized by k plus the size of a treewidth- • modulator (of the underlying undirected graph), where • is any fixed positive integer. Since the status of the existence of a polynomial kernel for DFVS (parameterized by the solution size) has been open for a very long time now, and it is known to not admit a polynomial kernel when the parameter is the size of a treewidth-2 modulator, solution size plus the size of the treewidth- • modulator makes for an interesting choice of parameter to study. In fact, the polynomial kernelization complexity of DFVS parameterized by the size of the undirected feedback vertex set (treewidth-1 modulator) in the underlying undirected graph has already been studied in literature. Our choice of parameter strictly encompasses previous positive kernelization results on DFVS. Our result is based on a novel application of the tool of important separators embedded in state-of-the-art machinery such as protrusion decompositions.