Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion

Abstract

Given a graph G and a parameter k, the Chordal Vertex Deletion (CVD) problem asks whether there exists a subset U ⊆ V (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(k161 log58 k), 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(k25 log14 k), inspired by the O(k2)-size kernel for Feedback Vertex Set. To obtain this result, we first design an O(opt-log2 n)-factor approximation algorithm for CVD, which is central to our kernelization procedure. Thus, we improve upon both the kernelization algorithm and the approximation algorithm of Jansen and Pilipczuk. Next, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution. We believe that this notion could be useful in designing kernels for other problems.