Prof. Meirav Zehavi

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 re- solve 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(optlog2 n)-factor approximation al- gorithm for CVD, which is central to our kernelization procedure. Thus, we improve upon both the kernel- ization 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.