ANR-DFG - Appel à projets générique 2020 - DFG

# Unifying Theories for Multivariate Algorithms – UTMA

## Unifying Theories for Multivariate Algorithms

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.

### Distil the meta-algorithmic value from all aspects of parametrized complexity theory and crystallize them into AMTs. Invent new structural parameters that systematize novel algorithmic techniques.

The ultimate target is to establish AMTs as an essential unification ingredient of the theory of algorithms. To reach this we need to introduce new logics, which are based on isomorphism invariant operators, which can be evaluated efficiently on basis of the technique that we are aiming to capture. An example for such logical operators would be an operator to state the existence of a fixed number of disjoint paths, or an operator to test for planarity. These two operators can be efficiently evaluated with the irrelevant vertex technique. The challenge will be to find a natural set of operators that allows to conveniently express algorithmic problems while avoiding redundancy between the operators. Choosing such a set of operators is also strongly related to logical reductions between algorithmic problems. The new logics will be build on the basis of first-order logic or monadic second-order logic, depending on the context, and extend these base logics by operators that are not expressible in the base logic. The techniques described in Section 1 often show their potential on restricted graph classes, such as on graphs of bounded genus or H-minor-free graphs, where also FO can be evaluated efficiently. This yields the second, structural component of the new AMTs we are aiming for, that is to investigate and invent new structural parameters that systematize or incorporate novel algorithmic techniques. Understand the limitations of applicability of these techniques and provide natural structural parameters that capture their applicability. Each abstract notion of connectivity based on symmetric submodular set functions gives rise to a combi- natorial width-measure with specific algorithmic applications. Well known examples are vertex connectivity, which leads to the notion of branchwidth (which is equivalent to treewidth) or the cut-rank, which leads to the notion of rankwidth (which is equivalent to cliquewidth). Other connectivity functions in- clude edge connectivity, hypergraph connectivity, matching connectivity, matroid connectivity, etc. Each of these connectivity functions leads to its own algorithmic techniques. This allows in many cases for efficient dynamic programming algorithms, and in particular it leads in many cases to efficient MSO model checking. The third challenge that we plan to take is to<br />find the most general (new) logics that can be efficiently evaluated on well known structurally restricted graph classes.

The first work package partially addresses Challenge 1. Our objective is to build a meta algorithmic theory systematizing the applicability of the irrelevant vertex technique and define some logic, more general than FO where AMTs can be proven for certain classes of sparse graphs. Given the known complexity restrictions on the problems where the irrelevant vertex technique applies. We will first pursue this objective on topologically constrained graphs whose structural characteristics are simpler to deal with. Our results may be indicative on how to proceed to more general graph sparsity conditions. We will also try to prove hardness results that obstructing the applicability of the irrelevant vertex technique in general graphs.

The second work package partially addresses Challenge 1 and Challenge 2. We aim to bring the dynamic programming approach to its full potential by exploring new structural parameters and on the resulting structural graph classes we aim to systematize and incorporate novel algorithmic techniques. Alternative dynamic programming approaches, combined with powerful techniques such as random separation, recursive understanding, and the use of important separators, where used for the design of FPT-algorithms for problems that do not fit in any known meta-algorithmic framework. As in all these results there are common techniques and ideas, the creation of a meta-algorithmic framework that can subsume most of them in a single AMT is currently an important challenge.

The third work package partially addresses Challenge 1. We aim to prove AMTs for counting and enumeration problems. For this objective, the first step is to exploit to what extent the meta-algorithmic arsenal of for counting problems can go further than the standard frameworks.

The fourth work package partially addresses Challenge 1. Our objective is to extend the combinatorial horizon of Bidimensionality Theory and to systematize its applicability. Our main approach to address this objective is to prove that the SQGM condition holds for graphs that admit certain embeddings in higher dimensions.

The final work package partially addresses Challenges 1 and 3. Our goal is to introduce further logics that capture algorithmic techniques and find the most general graph classes on which we can efficiently test properties definable in these logics, as well as to find the most general logics that can be efficiently tested on well studied graph classes.

The main result is the algorithmic meta-theorem in . It proved that modification problems where the target property is expressed by some first-order sentence plus planarity, admit a quadratic FPT-algorithm.  is the first result providing meta-algorithmic conditions for the applicability of the irrelevant vertex technique. This results has been vastly generalized in  where a new logic is introduced for graph modification problems, the T-logic, and an algorithmic meta-theorem is proved asserting that on minor minor-closed graph classes model checking for T can be done by a quadratic FPT-algorithm.

In  we propose a dynamic programming technique for graphs of low tree-
decomposability. We propose a meta-algorithm for the following problem: compute the minimum size of a vertex set of a graph
whose removal produces a graph excluding H as a minor. The main result of  is that it gives a meta-parametric condition on H sharply distinguishing the cases where this dynamic programming can be done in time O(ctw log tw · n) or in time O(ctw · n).

The main result in this direction is  where we provide a sharp dichotomy on when problem of counting perfect matchings is polynomially solvable or #P-complete. The result in  provides a structural parametric hierarchy called vga-hierarchy, that produced parameters that are more general than treewidth.

A related result in this direction is the use of kernelization techniques (such as protrusion replacement) for the derivation of constant-factor approximation algorithms in .

The main result on Tasks 4.1 and 4.2 are those of  where we give a wide family of geometry-defined graph classes based on intersection graphs of convex objects. In , we prove that these classes satisfy the, more general, SQCM condition.

The main result on this task is  (see also  where we prove the following algorithmic meta-theorem. If f is a FOL-sentence whose prefix pattern is ???, then The problem of designing whether a graph G has elimination distance at most k to a model of f admits an FPT-algorithm, running in time f(k) · nO(|f|). In  it is proved that this result is optimal in the sense that no such an algorithm may be expected for more complicated quantification prefixes.

The first step towards the realization of Task 5.2 was done in ,  and  where we develop elements of structural graph theory in order to build an algorithmic theory of dynamic programming.

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 an- swering 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 encoun- tered in problem parametrizations. Parameterized complexity theory is a fully developed discipline of thooretical 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.

## Project coordinator

Monsieur Dimitrios Thilikos (Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

## Partner

UBremen University of Bremen
LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

Help of the ANR 189,918 euros
Beginning and duration of the scientific project: August 2021 - 36 Months