Trade-offs in Parameterized Data Reduction

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2017 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 389085303

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.

• DFG Programme: Research Grants
• International Connection: Russia
• Partner Organisation: Russian Foundation for Basic Research
• Cooperation Partner: Professor Dr. René van Bevern