Feedback vertex set inspired kernel for chordal vertex deletion

From MaRDI portal
(Redirected from Feedback vertex set inspired kernel for chordal vertex deletion)
Feedback vertex set inspired kernel for chordal vertex deletion (scientific article; zbMATH DE number 7044615)



Abstract: Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset UsubseteqV(G) of size at most k that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size O(k161log58k), and asked whether one can design a kernel of size O(k10). While we do not completely resolve this question, we design a significantly smaller kernel of size O(k12log10k), inspired by the O(k2)-size kernel for Feedback Vertex Set. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.





Cited in
(23)








This page was built for publication: Feedback vertex set inspired kernel for chordal vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629981)