[] [] []


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

    Other members of the project (ordered alphabetically):

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 October 2022 Looking for a PhD grant on Parameterized Complexity? Contact me!

This webpage was last updated on January 8, 2022