Exploring the Limits of Tractability – ELIT
The main goal of this project is to explore the limits of tractability of computational problems in the quest of complexity dichotomies, especially in domains that have been weakly explored so far in the literature, and through the lens of parameterized complexity. I.e., our aim is to tackle problems for which a sharp distinction between the "easy" and "hard" cases is missing, for an appropriate definition of these terms.
More precisely, we plan to focus our research on the following five tasks:
(1) draw the line of efficiency among parameterized algorithms for forbidding structures in a graph (such as minors of induced subgraphs),
(2) existence of polynomial kernels for structural parameterizations in the so-called ``distance from triviality'' framework,
(3) obtaining complexity dichotomies for CSPs focusing on modification operations for various classes of structures,
(4) optimality of algorithms using width parameters for dense graphs such as rank-width, and
(5) devising efficient algorithms in directed graphs exploiting the notion of directed tree-width.
While the scientific coordinator has extensively worked on some of these areas in the last years, most of the objectives of this project aim at tackling problems and research directions that have not been considered so far in the literature.
To achieve these goals, the consortium is centered around the scientific coordinator, and its members are collaborators, from France and abroad (in Europe and other continents), which have been appropriately chosen to pursue this program.
Monsieur Ignasi Sau (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.
CNRS-LIRMM Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
Help of the ANR 168,923 euros
Beginning and duration of the scientific project: September 2021 - 48 Months