DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2018.10

A Polynomial Kernel for Diamond-Free Editing

Authors: Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

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.

Cite as

Yixin Cao, Ashutosh Rai, R. B. Sandeep, and Junjie Ye. A Polynomial Kernel for Diamond-Free Editing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cao_et_al:LIPIcs.ESA.2018.10,
  author =	{Cao, Yixin and Rai, Ashutosh and Sandeep, R. B. and Ye, Junjie},
  title =	{{A Polynomial Kernel for Diamond-Free Editing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.10},
  URN =		{urn:nbn:de:0030-drops-94732},
  doi =		{10.4230/LIPIcs.ESA.2018.10},
  annote =	{Keywords: Kernelization, Diamond-free, H-free editing, Graph modification problem}
}

Search Results

Documents authored by Ye, Junjie

A Polynomial Kernel for Diamond-Free Editing

Abstract

Cite as

Thanks for your feedback!

Could not send message