Eiben, Eduard ;
Lochet, William ;
Saurabh, Saket
A Polynomial Kernel for PawFree Editing
Abstract
For a fixed graph H, the Hfree 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 NPcomplete 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, Hfree 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 3connected 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 Hfree 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 Hfree Edge Editing for these graphs does not admit a polynomial kernel, then the conjecture is true. Therefore, resolving the kernelization of Hfree 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 Pawfree 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 PawFree Editing}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {10:110:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13313},
URN = {urn:nbn:de:0030drops133136},
doi = {10.4230/LIPIcs.IPEC.2020.10},
annote = {Keywords: Kernelization, Pawfree graph, Hfree editing, graph modification problem}
}
04.12.2020
Keywords: 

Kernelization, Pawfree graph, Hfree editing, graph modification problem 
Seminar: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 