Kernelization for edge modification problems

Abstract

Graph modification problems are significant problems in computer science that have gained considerable attention in recent decades. In this thesis, we focus on edge modification problems, whose task is to make an input graph satisfy some required properties by making small changes to the edges in the graph. We study kernelization algorithms for edge modification problems toward sev­eral graph classes that can be characterized by a finite set of forbidden induced sub­graphs and provide small kernels for these problems. A kernelization algorithm is a preprocessing algorithm that reduces the input instances to an equivalent instance with a smaller size in polynomial time. We show that the edge deletion problem toward cluster graphs and the edge addition problem toward paw-free graphs ad­mit linear kernels, a 2k-vertex kernel for the former one and a 38k-vertex kernel for the latter one. In addition, we prove that the edge addition problem toward triv­ially perfect graphs admits a quadratic kernel. We also prove that the edge addition problem and the edge deletion problem toward (pseudo-) split graphs have a kernel with O(K1.5) vertices.