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.
['Hans L. Bodlaender', 'Rodney G. Downey', 'Michael R. Fellows', 'Danny Hermelin']
On Problems without Polynomial Kernels (Extended Abstract)