A Polynomial Kernel for Paw-Free Editing
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/2763887/LIPIcs-IPEC-2020-10.pdf.jpg?sequence=6&isAllowed=y)
Åpne
Permanent lenke
https://hdl.handle.net/11250/2763887Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
- Department of Informatics [978]
- Registrations from Cristin [10237]
Originalversjon
Leibniz International Proceedings in Informatics. 2020, 180, 10. 10.4230/LIPIcs.IPEC.2020.10Sammendrag
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.