A Polynomial Kernel for Diamond-Free Editing

Yixin Cao, Ashutosh Rai, R. B. Sandeep, Junjie Ye

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Given a fixed graph H, the H-free editing problem asks whether we can edit at most k edges to make a graph contain no induced copy of H. We obtain a polynomial kernel for this problem when H is a diamond. The incompressibility dichotomy for H being a 3-connected graph and the classical complexity dichotomy suggest that except for H being a complete/empty graph, H-free editing problems admit polynomial kernels only for a few small graphs H. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of H-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

Original languageEnglish
Pages (from-to)197-215
Number of pages19
JournalAlgorithmica
Volume84
Issue number1
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Diamond-free graph
  • Graph modification problem
  • H-free editing
  • Kernelization

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A Polynomial Kernel for Diamond-Free Editing'. Together they form a unique fingerprint.

Cite this