- Title
- On problems without polynomial kernels
- Creator
- Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
- Relation
- Journal of Computer and System Sciences Vol. 75, Issue 8, p. 423-434
- Publisher Link
- http://dx.doi.org/10.1016/j.jcss.2009.04.001
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2009
- Description
- Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given parameterized instance to an equivalent instance of the same problem, with size and parameter bounded by a function of the parameter in the input. A kernel is polynomial if the size and parameter of the output are polynomially-bounded by the parameter of the input. In this paper we develop a framework which allows showing that a wide range of FPT problems do not have polynomial kernels. Our evidence relies on hypothesis made in the classical world (i.e. non-parametric complexity), and revolves around a new type of algorithm for classical decision problems, called a distillation algorithm, which is of independent interest. Using the notion of distillation algorithms, we develop a generic lower-bound engine that allows us to show that a variety of FPT problems, fulfilling certain criteria, cannot have polynomial kernels unless the polynomial hierarchy collapses. These problems include k-Path, k-Cycle, k-Exact Cycle, k-Short Cheap Tour, k-Graph Minor Order Test, k-Cutwidth, k-Search Number, k-Pathwidth, k-Treewidth, k-Branchwidth, and several optimization problems parameterized by treewidth and other structural parameters.
- Subject
- parameterized complexity; kernelization; polynomial kernels; lower bounds
- Identifier
- uon:7412
- Identifier
- http://hdl.handle.net/1959.13/807459
- Identifier
- ISSN:0022-0000
- Reviewed
- Hits: 3141
- Visitors: 2331
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|