The Art of Difference Parameterization in Multivariate Algorithmics

• Applicant: Professor Dr. Christian Komusiewicz, since 10/2024
• Subject Area: Theoretical Computer Science
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 452214352

Further developing and analyzing analytical tools such as ``difference parameterization'' (a core example is the established framework of above-guarantee parameterization), we aim at achieving (practically) more meaningful statements about theperformance of exact (fixed-parameter) algorithms for NP-hard problems. To this end, our focus is on employing search trees and data reduction techniques as core algorithmic tools, and methods from parameterized complexity analysis as core theoretical tools.Our key lines of attack concern- to study difference parameters through lower bounds achieved via packing of combinatorial structures; - to study difference parameters gained through approximation algorithms, also including linear programming; - to study difference parameters resulting through systematic exploration of structural parameter hierarchies; and - to study linear combinations of parameters, thus generalizing the concept of difference parameters.The utmost goal is to significantly push the “art of problem parameterization'' towards the next level, particularly making the performance of branch & bound (search tree) algorithms better explainable on the one side, and to potentially improve algorithmic approaches (by exploring and exploiting further refined parameterizations) on the other side. Our studies shall mainly focus on NP-hard graph problems.

• DFG Programme: Research Grants
• Ehemalige Antragsteller: Dr. André Nichterlein, from 6/2022 until 9/2024; Professor Dr. Rolf Niedermeier, until 6/2022 (†)