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).