A Polynomial Kernel for Paw-Free Editing
share
For a fixed graph H, the H-free-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 showed that the H-free-editing problem 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 1 edge missing. Their results suggest that if H is not independent set or a clique, then H-free-editing admits polynomial kernels only for few small graphs H, unless coNP∈NP/poly. Therefore, resolving the kernelization of H-free-editing for small graphs H 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 editing with O(k^6)vertices.
READ FULL TEXT