Let H be a graph. The H-free Edge Deletion problem asks whether we can delete at most k edges from an input graph such that the resulting graph does not contain H as an induced subgraph. The H-free Edge Deletion problem, especially for the cases of H being a connected graph of 4 vertices have been extensively studied in parameterized algorithms and kernelization. In this paper, we consider the case that H is a diamond (a graph obtained by removing exactly one edge from a clique of 4 vertices). We show that the Diamond-free Edge Deletion problem allows a kernel of quadratic vertices, improving the previous cubic-vertex kernel.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Quadratic Vertex Kernel for Diamond-Free Edge Deletion

  • Kangyi Tian,
  • Haotian Pan,
  • Mingyu Xiao

摘要

Let H be a graph. The H-free Edge Deletion problem asks whether we can delete at most k edges from an input graph such that the resulting graph does not contain H as an induced subgraph. The H-free Edge Deletion problem, especially for the cases of H being a connected graph of 4 vertices have been extensively studied in parameterized algorithms and kernelization. In this paper, we consider the case that H is a diamond (a graph obtained by removing exactly one edge from a clique of 4 vertices). We show that the Diamond-free Edge Deletion problem allows a kernel of quadratic vertices, improving the previous cubic-vertex kernel.