(2019-2021, funded by DAAD, principal investigator: Professor Dr. M. Mnich, co-investigator: Professor Kristóf Bérczi, ELTE University)

Algorithms for optimization problems on graphs belong to the most investigated topics within theoretical and practical algorithm design, due to their generality in modelling vast arrays of applications and the high level of algorithmic tools that have been developed for them in the past 50-60 years. About 30 years ago, a new approach was put forward to break out of this classical P vs. NP-dichotomy for optimization problems, and propose a fine-grained hierarchy of problem complexities through the new theory of Parameterized Complexity.  However, almost all of those algorithmic tools have been designed for graph problems or graph-related problems, which are highly combinatorial in nature. But considering practical applications, it is much more common that one needs to solve problems that come with numerical input data. Those types of problems are difficult or impossible to be addressed with the current tools of parameterized complexity. In this project we will therefore develop new tools for Parameterized Complexity that can deal with numeric data.