Two Edge Modification Problems without Polynomial Kernels

Given a graph G and an integer k, the Pi Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most k edges in G such that one obtains a graph that fulfills the property Pi. Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by k, many of these problems turned out to be fixed-parameter tractable and some are known to admit polynomial kernelizations, i.e., efficient preprocessing with a size guarantee that is polynomial in k. This paper answers an open problem posed by Cai (IWPEC 2006), namely, whether the Pi Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when Pi can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on recent work by Bodlaender et al. (ICALP 2008) which provided a framework for proving polynomial lower bounds for kernelizability. We present a graph H on seven vertices such that H-free Edge Deletion and H-free Edge Editing do not admit polynomial kernelizations, unless the polynomial hierarchy collapses. The application of the framework is not immediate and requires a lower bound for a Min Ones SAT problem that may be of independent interest