2026-07-25T12:07:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13313 2024-03-06T10:51:40Z ddc:004 open_access

A Polynomial Kernel for Paw-Free Editing Eiben, Eduard Lochet, William Saurabh, Saket Kernelization Paw-free graph H-free editing graph modification problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and William Lochet and Saket Saurabh 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.10 urn:nbn:de:0030-drops-133136 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.10 eng https://creativecommons.org/licenses/by/3.0/legalcode