Trade-offs in Parameterized Data Reduction

核化是参数化复杂性分析对算法设计的主要贡献之一：对于一个给定的实例(典型的NP-Hard问题)，人们在多项式时间内计算一个等价的实例，其大小可以由一个函数仅依赖于某个参数(它衡量输入的某些(结构性)属性)的上限。许多核化是由只要适用就可应用的数据约简规则组成的。在这个项目中，基于对核化各个方面的多年经验，我们计划进一步推动核化的新方面的发展，特别是关注各种权衡效应。特别是，我们计划推动核化的新方面的发展，特别是关注各种权衡效应。特别是，我们计划推动核化的新方面的发展，特别是关注各种权衡效应我们对有效的核化时间和有效的核大小之间的权衡很感兴趣。因此，我们对帕累托最优核感兴趣，然后通过一个接一个地执行核化来利用链接效应。此外，我们计划系统地探索诸如部分核化、近似核化、随机化核化、图灵核化等概念，所有这些最终目标都是在更好的运行时间和/或核大小与核概念的一些放松之间进行权衡。这样，我们计划在理论上(包括新的框架和下界)和实践上(直到算法工程)做出贡献。虽然我们的重点是NP-Hard问题，但我们也考虑了多项式时间可解问题。

Kernelization is arguably one of the major contributions of parameterized complexity analysis to algorithm design: for a given instance of a (typically NP-hard) problem, one computes in polynomial time an equivalent instance whose size can be upper-bounded by a function only depending on some parameter (which measures some (structural) property of the input).Many kernelizations are composed of data reduction rules that are applied as long as applicable.In this project, based on many years of experience with various facets of kernelization, we plan to further push the development of new aspects of kernelization, particularly focussing on various trade-off effects.In particular, we are interested in trade-offs of efficient kernelization time and effective kernel size with a number of quality measures for kernels.So we are interested in Pareto-optimal kernels, then making use of "chaining effects" by executing one kernelization after another.Further, we plan to systematically explore concepts such as partial kernelization, approximative kernelization, randomized kernelization, Turing kernelization etc., all with the ultimate goal to trade better running time and/or kernel size against some relaxation of the kernel concept.Doing so, we plan to contribute both theoretically (including new frameworks and lower bounds) and practically (up to algorithm engineering).Although our focus is on NP-hard problems, we also include polynomial-time solvable problems in our considerations.