Zimo Sheng

A Polynomial Kernel for Planar Directed Feedback Vertex Set

The Directed Feedback Vertex Set problem (DFVS) asks whether a digraph can be made acyclic by deleting at most $k$ vertices. Whether DFVS admits a polynomial kernel parameterized by $k$ is a major open problem in kernelization, even for planar digraphs. We resolve the planar case by giving a deterministic kernel with $...