graph modification problem, fixed-parameter tractable, kernelization algorithm
Kernelization algorithms for graph modification problems are important ingredients in parameterized computation theory. In this paper, we survey the kernelization algorithms for four types of graph modification problems, which include vertex deletion problems, edge editing problems, edge deletion problems, and edge completion problems. For each type of problem, we outline typical examples together with recent results, analyze the main techniques, and provide some suggestions for future research in this field.
Tsinghua University Press
Yunlong Liu, Jianxin Wang, Jiong Guo. An Overview of Kernelization Algorithms for Graph Modification Problems. Tsinghua Science and Technology 2014, 19(04): 346-357.