Probablement, le théorème le plus profond en combinatoire et théorie des graphes de ces dernières 30 années est celui de Robertson et Seymour [1], qui démontre la conjecture de Wagner : toute famille F de graphes fermée par mineurs (c'est-à-dire, telle que tout mineur d'un graphe de F appartient aussi à F) peut être caractérisée par un ensemble FINI de mineurs interdits. Ce résultat peut être vu comme une généralisation naturelle du théorème de Kuratowski [2], qui caractérise les graphes planaires comme la classe des graphes ne contenant comme mineur ni le graphe complet K5 ni le graphe biparti complet K3,3.

La preuve du theorème de Robertson et Seymour comporte plus de 500 pages, s'étalant dans une vingtaine articles publiés de 1983 à 2004, et contient tout un éventail de résultats qui ont enrichi notablement la théorie des graphes. Le plus important de ces résultats est un théorème qui décrit très précisément la structure des graphes qui ne contiennent pas un graphe fixé H comme mineur [3]. Ce résultat structurel a permis le développement de plein d'algorithmes efficaces dans cette classe de graphes pendant la dernière dizaine d'années (voir, par exemple, [4]).

Il est assez facile de voir que le résultat analogue à celui de Robertson et Seymour [1] pour des mineurs topologiques est faux. Mais très récemment, Grohe et Marx [5] ont prouvé un résultat structurel pour la classe des graphes qui ne contiennent pas un graphe fixé H comme mineur topologique, qui généralise celui de Robertson et Seymour [3]. Tout semble indiquer que ce résultat va pousser considérablement le développement d'algorithmes efficaces dans cette classe de graphes.

La première partie du stage sera composée principalement de lecture d'articles, avec le but de bien comprendre la structure de la classe des graphes qui ne contiennent pas un graphe fixé H comme mineur topologique. Dans une deuxième partie, l'objectif sera d'utiliser le nouveau résultat de Grohe et Marx pour développer des algorithmes efficaces pour des problèmes NP-durs dans cette classe de graphes. Par exemple, Grohe et Marx [5] prouvent que le problème de Dominating Set est FPT dans les graphes avec un mineur topologique interdit. D'autres variantes du problème de domination (Connected Dominating Set, Independent Dominating Set, ...) semblent des bons candidats pour commencer à attaquer ce sujet. Pour ce faire, on va se servir des outils de la théorie de la complexité paramétrée et des techniques algorithmiques classiques comme la programmation dynamique.

Le plan de travail n'est pas du tout rigide, et va évoluer en fonction de comment le stage avance et des intérêts scientifiques de l'étudiant/e.