User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Two Edge Modification Problems without Polynomial Kernels


Kratsch,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;


Wahlström,  Magnus
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Kratsch, S., & Wahlström, M. (2009). Two Edge Modification Problems without Polynomial Kernels. In J. Chen, & F. V. Fomin (Eds.), 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
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.