2019/11/09 by Eiben, Eduard, Lochet, William, Saurabh, Saket
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.03683
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 2O(k)nO(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 \textsfcoNP ∈ \textsfNP/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(k6)vertices.