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!