Theoretical and Practical Aspects of Kernelization

点击翻译按钮获取中文摘要

Kernelization is an area of parameterized complexity that dealswith the study of preprocessing algorithms. A kernelizationalgorithm essentially strips away the easy parts of aproblem instance exposing the core or the kernel. This is an area thathas attracted the attention of both theoreticians and practitionersfor the interesting mathematical problems it poses and the practicalutility of many of the solutions.The objective of this project is to study both theoreticaland practical aspects of kernelization algorithms. On thetheoretical side, we plan to investigate topics suchas kernelization using non-standard parameters where somestructural aspect of the input (other than the solution size)is used as parameter. Other topics includestrong polynomial kernels, Turing kernels, and theconnection between kernelization and approximability. On thepractical side, we plan to design kernelization algorithmsfor concrete problems with the aim of implementing thesealgorithms. In particular, we want to investigate the possibility ofimproving kernels for several problems on planar graphs (among others).