Beyond kernelization – Greater generality for efficient preprocessing

有效的预处理是加速计算的通用方法。通过从参数化复杂性的核化的概念，对NP难问题的有效预处理进行了严格的研究。（多项式）核化是一种有效的算法，其在给定输入实例的情况下返回大小由输入的某个指定参数的（多项式）函数限制的等效实例，例如，解决方案的大小。到目前为止，多项式核化的存在性或不存在性对于受到不同输入参数影响的各种困难问题是相当好理解的。不幸的是，事实证明，许多问题不允许多项式核化（受制于合理的复杂性假设）。此外，积极的结果似乎在很大程度上局限于测量到一类输入的距离的参数，在这类输入上，所讨论的问题是容易处理的。即使在这样的参数化，我们发现，许多简单的情况下证明不承认多项式核。在这个项目中，我们希望研究宽松的内核化形式，包括现有的和新的内核化形式，以绕过这个限制。这包括近似和图灵内核化，以及它们的组合。最近，这导致了第一个积极的结果预处理的树宽参数化的困难问题。我们还想研究对整个实例的结构没有严格要求的内核化的局部形式。相反，它应该足够有一部分的输入，表现出足够的结构，其相互作用与其余的输入可以处理。同样，我们的目标是结构化预处理，产生其他输出保证，而不是小尺寸。相反，保证任何算法上有用的参数的（低）界可以改善后续的计算，这符合有效预处理的精神。总的来说，我们的目标是建立有意义的，积极的结果，有效的预处理困难的问题，在限制性较低的条件下比什么是可能的。

Efficient preprocessing is a versatile and general approach for speeding up computations. A rigorous study of efficient preprocessing for NP-hard problems was enabled through the notion of a kernelization from parameterized complexity. A (polynomial) kernelization is an efficient algorithm that given an input instance returns an equivalent instance of size bounded by a (polynomial) function of some specified parameter of the input, e.g., of the solution size. By now, the existence or non-existence of polynomial kernelizations is quite well understood for a variety of hard problems subject to different input parameters. Unfortunately, it has turned out that many problems do not admit polynomial kernelizations (subject to plausible complexity assumptions). Moreover, positive results seem largely limited to parameters that measure distance to a class of inputs on which the problem in question is tractable. Even among such parameterizations we find that many simple cases provably do not admit a polynomial kernelization. In this project, we want to study relaxed forms of kernelization, both existing and new ones, to get around this limitation. This includes approximate and Turing kernelization, as well as their combination. Recently, this led to the first positive results for preprocessing hard problems parameterized by treewidth. We also want to study local forms of kernelization that do not have strict requirements for the structure of the entire instance. Instead, it should be sufficient to have a part of the input that exhibits sufficient structure and whose interplay with the rest of the input can be dealt with. Similarly, we are aiming for structural preprocessing that yields other output guarantees than small size. Instead, guaranteeing a (low) bound for any algorithmically useful parameter may improve the subsequent computation, being true to the spirit of efficient preprocessing. Overall, the goal is to establish meaningful, positive results for efficient preprocessing for hard problems under less restrictive conditions than what is possible so far.