2008 | OriginalPaper | Buchkapitel
On Problems without Polynomial Kernels (Extended Abstract)
verfasst von : Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.