Unifying Theories for Multivariate Algorithms – UTMA

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.

Tasks 1.1 and 1.2:

The main result is the algorithmic meta-theorem in [16]. It proved that modification problems where the target property is expressed by some first-order sentence plus planarity, admit a quadratic FPT-algorithm. [16] is the first result providing meta-algorithmic conditions for the applicability of the irrelevant vertex technique. This results has been vastly generalized in [22] 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.

Task 2.1 and Task 2.2:
In [17] 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 [17] 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).

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

• Task 3.2:
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 [14].

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

• Task 5.1:
The main result on this task is [5] (see also [20] 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 [5] it is proved that this result is optimal in the sense that no such an algorithm may be expected for more complicated quantification prefixes.

• Task 5.2:
The first step towards the realization of Task 5.2 was done in [25], [26] and [2] 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.