Enumeration kernels for Vertex Cover and Feedback Vertex Set

Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creignou et al. [Theory Comput. Syst., 2017], and development in the area has started to accelerate with the work of Golovach et al. [J. Comput. Syst. Sci., 2022]. The latter introduced polynomial-delay enumeration kernels and applied them in the study of structural parameterizations of the $\text{textsc}MatchingCut$ problem and some variants. Few other results, mostly on $\text{textsc}LongestPath$ and some generalizations of $\text{textsc}MatchingCut$, have also been developed. However, little success has been seen in enumeration versions of $\text{textsc}VertexCover$ and $\text{textsc}FeedbackVertexSet$, some of the most studied problems in kernelization. In this paper, we address this shortcoming. Our first result is a polynomial-delay enumeration kernel with $2k$ vertices for $\text{textsc}EnumVertexCover$, where we wish to list all solutions with at most $k$ vertices. This is obtained by developing a non-trivial lifting algorithm for the classical crown decomposition reduction rule, and directly improves upon the kernel with $\mathcal{O}(k^2)$ vertices derived from the work of Creignou et al. Our other result is a polynomial-delay enumeration kernel with $\mathcal{O}(k^3)$ vertices and edges for $\text{textsc}EnumFeedbackVertexSet$; the proof is inspired by some ideas of Thomassé [TALG, 2010], but with a weaker bound on the kernel size due to difficulties in applying the $q$-expansion technique.