Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/45030
- Title
- On problems without polynomial kernels
- Author/Creator
-
Bodlaender, Hans L.;
Downey, Rodney G.;
Fellows, Michael R.;
Hermelin, Danny
- Institution
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- Description
- Kernelization is a central technique used in parameterized algorithms, and in other approaches for coping with NP-hard problems. In this paper, we introduce a new method which allows us to show that many problems do not have polynomial size kernels under reasonable complexity-theoretic assumptions. 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 or cliquewidth.
- Relation
- 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). Automata, Languages and Programming (Reykjavik, Iceland 7-11 July, 2008) p. 563-574
- Publisher Link
- http://dx.doi.org/10.1007/978-3-540-70575-8_46
- Date
- 2008
- Publisher
- Springer Berlin
- Keyword(s)
-
kernelization;
polynomial kernels;
parameterized algorithms;
optimization problems
- Resource Type
- conference paper
- Identifier
- http://hdl.handle.net/1959.13/45030
- Identifier
- ISBN:9783540705741
- Reviewed
8 Visitors
9 Hits
0 Downloads
