Two edge modification problems without polynomial kernels

Given a graph GG and an integer kk, the ΠΠ Edge Completion/Editing/Deletion problem asks whether it is possible to add, edit, or delete at most kk edges in GG such that one obtains a graph that fulfills the property ΠΠ. Edge modification problems have received considerable interest from a parameterized point of view. When parameterized by kk, 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 kk. This paper answers an open problem posed by Cai (IWPEC 2006) [11], namely, whether the ΠΠ Edge Deletion problem, parameterized by the number of deletions, admits a polynomial kernelization when ΠΠ can be characterized by a finite set of forbidden induced subgraphs. We answer this question negatively based on the framework for kernelization lower bounds of Bodlaender et al. (ICALP 2008, JCSS 2009) [15] and Fortnow and Santhanam (STOC 2008, JCSS 2011) [16]. We present a graph HH on seven vertices such that HH-free Edge Deletion and HH-free Edge Editing do not admit polynomial kernelizations, unless NP⊆coNP/poly. The application of the framework is not immediate and requires a lower bound for a Not-1-in-3 SAT problem that may be of independent interest.