License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-133136
URL:

; ;

### A Polynomial Kernel for Paw-Free Editing

 pdf-format:

### 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 Seminar: 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