Beyond kernelization – Greater generality for efficient preprocessing

点击翻译按钮获取中文摘要

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.