Vendredi 08 juillet 2016 à 11h, salle 24-25/405

**Abstract**

Parameterized complexity suggests a multi-parameter analysis of the computational complexity
of hard problems. The idea is to understand the influence of parameters, distinct from the input
size, in the resolution of a problem. Such parameters could be the solution size or the structural
parameters such as width parameters.
After an introduction to parameterized complexity, we will present some of the algorithmic
consequences of the graph minor theory. From the work of Robertson and Seymour, it
is known that every graph family closed under minor can be recognized in cubic time.
However for most of such graph family, such a result is existential only. Since then
constructive meta-algorithmic theorems have been proposed (including Courcelle’s theorem)
within the framework of parameterized complexity. We will discuss recent developments in this
line of research that led to efficient algorithms for large family of problems.