Wannabe Bounded Treewidth Graphs Admit a Polynomial Kernel for Directed Feedback Vertex Set
Daniel Lokshtanov, Ramanujan Sridharan, Saket Saurabh, Roohani Sharma, Meirav Zehavi · ACM Transactions on Computation Theory · 2025
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.