{"ID":2872550,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.08475","arxiv_id":"2509.08475","title":"Enumeration kernels for Vertex Cover and Feedback Vertex Set","abstract":"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 \\textsc{Matching Cut} problem and some variants. Few other results, mostly on \\textsc{Longest Path} and some generalizations of \\textsc{Matching Cut}, have also been developed. However, little success has been seen in enumeration versions of \\textsc{Vertex Cover} and \\textsc{Feedback Vertex Set}, 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 \\textsc{Enum Vertex Cover}, 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 \\textsc{Enum Feedback Vertex Set}; 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.","short_abstract":"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....","url_abs":"https://arxiv.org/abs/2509.08475","url_pdf":"https://arxiv.org/pdf/2509.08475v1","authors":"[\"Marin Bougeret\",\"Guilherme C. M. Gomes\",\"Vinicius F. dos Santos\",\"Ignasi Sau\"]","published":"2025-09-10T10:27:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}