On problems without polynomial kernels
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. (C) 2009 Elsevier Inc. All rights reserved.
polynomial kernels kernelization parameterized complexity distillation algorithm polynomial hierarchy lower bounds composition algorithm