zbMATH — the first resource for mathematics

On problems without polynomial kernels (extended abstract). (English) Zbl 1153.68554
Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 563-574 (2008).
Summary: 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.
For the entire collection see [Zbl 1142.68001].

68W05 Nonnumerical algorithms
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI