License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.10
URN: urn:nbn:de:0030-drops-133136
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13313/
Go to the corresponding LIPIcs Volume Portal

Eiben, Eduard ; Lochet, William ; Saurabh, Saket

A Polynomial Kernel for Paw-Free Editing

pdf-format:
LIPIcs-IPEC-2020-10.pdf (0.6 MB)

Abstract

For a fixed graph H, the H-free Edge Editing problem asks whether we can modify a given graph G by adding or deleting at most k edges such that the resulting graph does not contain H as an induced subgraph. The problem is known to be NP-complete for all fixed H with at least 3 vertices and it admits a 2^O(k)n^O(1) algorithm. Cai and Cai [Algorithmica (2015) 71:731–757] showed that, assuming coNP ⊈ NP/poly, H-free Edge Editing does not admit a polynomial kernel whenever H or its complement is a path or a cycle with at least 4 edges or a 3-connected graph with at least one edge missing. Based on their result, very recently Marx and Sandeep [ESA 2020] conjectured that if H is a graph with at least 5 vertices, then H-free Edge Editing has a polynomial kernel if and only if H is a complete or empty graph, unless coNP ⊆ NP/poly. Furthermore they gave a list of 9 graphs, each with five vertices, such that if H-free Edge Editing for these graphs does not admit a polynomial kernel, then the conjecture is true. Therefore, resolving the kernelization of H-free Edge Editing for graphs H with 4 and 5 vertices plays a crucial role in obtaining a complete dichotomy for this problem. In this paper, we positively answer the question of compressibility for one of the last two unresolved graphs H on 4 vertices. Namely, we give the first polynomial kernel for Paw-free Edge Editing with O(kâĥ) vertices.

BibTeX - Entry

@InProceedings{eiben_et_al:LIPIcs:2020:13313,
  author =	{Eduard Eiben and William Lochet and Saket Saurabh},
  title =	{{A Polynomial Kernel for Paw-Free Editing}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13313},
  URN =		{urn:nbn:de:0030-drops-133136},
  doi =		{10.4230/LIPIcs.IPEC.2020.10},
  annote =	{Keywords: Kernelization, Paw-free graph, H-free editing, graph modification problem}
}

Keywords: Kernelization, Paw-free graph, H-free editing, graph modification problem
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI