Kernel­ization

Preprocessing shows up in almost every implementation for hard problems, but how can you tell whether a simplification routine is doing something meaningful? Kernelization makes this precise within parameterized complexity. A kernel is a polynomial-time algorithm that shrinks any instance to an equivalent one whose size is bounded by a function of the parameter alone. I survey the early work on kernels, newer techniques for designing them, and the framework of Bodlaender et al. and Fortnow and Santhanam for showing, under standard complexity assumptions, that some problems are unlikely to have kernels of polynomial size.