In an edge modification problem, we are asked to modify at most k edges of a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we have the completion problems and the edge deletion problems. A great amount of efforts have been devoted to understanding the kernelization complexity of these problems. We revisit several well-studied edge modification problems, and develop improved kernels for them: - a 2 k-vertex kernel for the cluster edge deletion problem, - a 3 k²-vertex kernel for the trivially perfect completion problem, - a 5 k^{1.5}-vertex kernel for the split completion problem and the split edge deletion problem, and - a 5 k^{1.5}-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem. Moreover, our kernels for split completion and pseudo-split completion have only O(k^{2.5}) edges. Our results also include a 2 k-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion.

Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete.