Beyond kernelization – Greater generality for efficient preprocessing

超越内核化 â 更通用的高效预处理

• 批准号: 526215872
• 负责人: Professor Dr. Stefan Kratsch
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/526215872?language=en
• 关键词: Beyond; kernelization; Greater; generality; efficient

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.

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