Worker — Workshop on Kernelization

Research on theory and applications of kernelization is a vibrant and rapidly developing area in algorithm design and complexity. Worker is a series of workshops started in Bergen in 2009 and aims at consolidating the results achieved in recent years and discussing future research directions.

Felix Reidl

Main content

Kernelization is concerned with the task of preprocessing an instance of a problem in polynomial time in such a way that the resulting instance is much smaller than the original instance.  For some problems, we are able to remove all but a polynomial-sized number of objects from the original input, in which case we call the resulting instance a polynomial kernel.  The study of the existence of polynomial kernels for various problems is one of the most important areas of parameterized complexity.

Worker, the Workshop on Kernels, is the biannual meeting of the kernelization community and is organized by different research institutions.