Project Description

DFG - ANR Projekt SI 2497/3 "Verallgemeinernde Prinzipien für multivariate Algorithmen"

Principal investigator: Sebastian Siebertz, Dimitrios Thilikos

Project term:  2021 - 2024.

Studying the tractability of computational problems is a core challenge in theoretical computer science. A central question is when, why, and how computational problems can be solved efficiently. Towards answering this question, the theory of algorithms has offered powerful unifying results, called algorithmic meta-theorems (AMTs) that provide general mathematical conditions implying the automatic derivation of efficient algorithms. These conditions are typically linked to the descriptive complexity of the problems (via logic) and the structural properties of their inputs (via combinatorics). AMTs, while infrequent, are precious because they provide a deep understanding of the nature of computational tractability. This proposal aims at revealing the unification potential of AMTs in discrete algorithms. We are going to employ the framework of parameterized complexity theory, where algorithm efficiency is evaluated not only with respect to the input size but also with respect to additional key secondary parameters. This multivariate approach allows to flexibly take into account the logical and structural conditions that are typically encountered in problem parametrizations. Parameterized complexity theory is a fully developed discipline of theoretical computer science and has developed an extended arsenal of algorithmic techniques and paradigms. Their systematic elevation to AMTs is a mature and non-trivial challenge that calls for a qualitative shift in the theory of algorithms from the study of particular problems to the quest for unifying algorithmic theories. We plan to distill the best meta-algorithmic value from the most advanced techniques in all aspects of contemporary parameterized complexity theory. We propose the proof of AMTs for wide families of problems in diverse contexts in discrete algorithms. The ultimate outcome will be the establishment of AMTs as an essential unification ingredient of the theory of algorithms.