Projet ELiT: Exploring the Limits of Tractability

Financement : ANR JCJC
Identifiant : ANR-20-CE48-0008-01
Partenaires : LIRMM
Dates : 2021/2025
Responsable : Ignasi Sau

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: draw the line of eficiency among parameterized algorithms for forbidding structures in a graph (such as minors of induced subgraphs), existence of polynomial kernels for structural parameterizations in the so-called "distance from triviality" framework, complexity dichotomies for CSPs focusing on modification operations for various classes of structures, optimality of algorithms using width parameters for dense graphs such as rank-width, and devising eficient 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 areas and research directions that have not been considered so far in the literature.