Trade-offs in Parameterized Data Reduction

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

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.