Externally Funded Research Projects
DFG Projekt SI 2497/2 "Grundlagen der algorithmischen Stabilit?tstheorie"
Principal investigator: Sebastian Siebertz
Project term: March 2021 - March 2024.
First-order and monadic second-order logic play important roles in computer science. Besides the traditional connections with finite automata and regular languages, descriptive complexity, and many more, they find strong applications in the formulation of algorithmic meta-theorems. An algorithmic meta theorem provides algorithmic techniques that work not only for individual problems but for whole classes of problems. These classes of problems are often specified by logical means. A famous example of an algorithmic meta-theorem is Courcelle’s Theorem, stating that every property definable in monadic second-order logic can be decided in linear time on every class of graphs of bounded treewidth. A similar result for first-order logic states that every property definable in first-order logic can be decided in almost linear time on every nowhere dense class of graphs. Under standard complexity theoretic assumptions both of these tractability results cannot be extended to more general graph classes that are closed under taking subgraphs, hence, the classification of subgraph-closed graph classes on which monadic second-order and first-order properties can be decided efficiently is essentially complete. The goal of this project is to develop a systematic understanding of the combinatorial structure underlying algorithmic tractability beyond subgraph-closed graph classes. The main tool that will be applied is stability theory, also known as classification theory, which is one of the most successful areas of contemporary mathematical logic. Recent results successfully combine methods from discrete mathematics and stability theory to obtain strong structural and algorithmic results for important graph classes. Examples include efficient algorithms for nowhere dense graph classes, which are stable, a regularity lemma without exceptional pairs for stable graphs, and a definable regularity lemma for hypergraphs with the non-independence property (NIP), which is a modeltheoretic counterpart of the Vapnik-Chervonenkis dimension. I aim to provide a rigorous foundational analysis of algorithmic applications of stability theory in finite combinatorics and graph theory. The immediate beneficiaries of this research will be researchers in theoretical computer science, especially in parameterized complexity and approximation algorithms, graph theory, and logic.
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.