# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Two Edge Modification Problems without Polynomial Kernels

##### External Ressource

No external resources are shared

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kratsch, S., & Wahlström, M. (2009). Two Edge Modification Problems without Polynomial
Kernels. In J. Chen, & F. V. Fomin (*Parameterized
and Exact Computation* (pp. 264-275). Berlin: Springer. doi:10.1007/978-3-642-11269-0_22.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-18E4-9

##### Abstract

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.