ELiT project -- ANR JCJC

ELiT
Exploring the Limits of Tractability
ANR JCJC project (ANR-20-CE48-0008-01)
From 10/2021 until 10/2026, funded 169k€

Other members of the project (ordered alphabetically):

Julien Baste (CRIStAL, Université de Lille, France)
Rémy Belmonte (LAMSADE, Université Paris-Dauphine, France)
Marin Bougeret (LIRMM, Université de Montpellier, France)
Victor A. Campos (Universidade Federal do Ceará, Fortaleza, Brazil)
Clément Carbonnel (LIRMM, Université de Montpellier, France)
Bart M. P. Jansen (Eindhoven University of Technology, Netherlands)

Summary of the project

The main goal of this project is to explore the limits of tractability of computational problems in the quest of complexity dichotomies, through the lens of parameterized complexity.

Objectives

At a high level, we plan to tackle problems arising from the following contexts:

Finding dichotomies for graph modification problems, such as those consisting in forbidding certain structures in a graph.
Characterizing the existence of polynomial kernels for structural parameterizations of fundamental graph problems.
Complexity dichotomies for CSPs inspired by graph modification problems, stemming from the non-uniform CSP dichotomy.
Closing the gap of algorithms using width parameters for dense graphs, such as rank-width or clique-width.
Efficient algorithms in directed graphs, in particular exploiting the notion of directed tree-width.

PhD grant starting in September 2024

Looking for a PhD grant on Parameterized Complexity? Contact me!

This webpage was last updated on January 8, 2024