2021/04/29 by Cao, Yixin, Ke, Yuping
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2104.14510
In an edge modification problem, we are asked to modify at most k edges to 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: \beginitemize \item a 2 k-vertex kernel for the cluster edge deletion problem, \item a 3 k2-vertex kernel for the trivially perfect completion problem, \item a 5 k1.5-vertex kernel for the split completion problem and the split edge deletion problem, and \item a 5 k1.5-vertex kernel for the pseudo-split completion problem and the pseudo-split edge deletion problem. \enditemize Moreover, our kernels for split completion and pseudo-split completion have only O(k2.5) edges. Our results also include a 2 k-vertex kernel for the strong triadic closure problem, which is related to cluster edge deletion.