•  
  •  
 
Tsinghua Science and Technology

Keywords

graph modification problem, fixed-parameter tractable, kernelization algorithm

Abstract

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.

Publisher

Tsinghua University Press

Share

COinS