Cours de Master 2: Décompositions arborescentes et algorithmes FPT


  • Responsables :
    Stéphan Thomassé

  • Horaires :
    Cours de vague 1. Il y a deux cours de deux heures par semaine, le lundi de 10h15 à 12h15 et le vendredi de 13h30 à 15h30. Les cours commencent le vendredi 14 septembre.

  • Prérequis :
    Notions de base souhaitées en théorie des graphes, algorithmique et complexité.

  • Validation :

    DM disponible ici

    L'examen aura lieu en salle B1 le 30 novembre 2012 de 13h30 à 16h30. Les documents sont autorisés.


  • Objectif du module :
    Une grande majorité des problèmes en algorithmique des graphes sont NP-difficiles, comme par exemple le problème du voyageur de commerce. En revanche, la plupart de ces problèmes deviennent polynomiaux lorsque les graphes considérés sont acycliques, e.g. des arbres. Une manière de contourner la difficulté est de structurer le graphe en le décomposant de façon arborescente. L'objectif de ce cours est de présenter ces techniques, dont notamment la désormais incontournable notion de tree-width, ou largeur arborescente, introduite par Robertson et Seymour. Une introduction aux algorithmes FPT (fixed parameter tractable), qui découlent de cette théorie, sera aussi proposée.

  • Plan (très) prévisionnel des cours:

    1. Introduction des notions de largeur arborescente (tree-width) et de ses nombreux dérivés, dont la path-width et la branch-width.
    Résultats de base, jusqu'au Grid-Minor Theorem.
    2. Programmation dynamique sur les graphes de largeur arborescente bornée.
    Ce résultat est le point de départ du chapitre suivant.
    3. Introduction à la complexité paramétrée.
    4. Notion de Noyau et d'algorithme de compression.
    5. Le théoreme des mineurs de graphes. Avec son corollaire principal:
    Pour toute classe de graphe close par mineur, il existe un algorithme polynomial qui décide si un graphe appartient à cette classe ou pas. Nous présenterons ce résultat, certainement le plus difficile et le plus profond de la théorie des graphes. Une application directe est par exemple qu'il est polynomial de décider si un graphe se plonge sur une surface donnée. La largeur arborescente et le routage (linkage) sont les clés de ce résultat.
    6. Graph Searching.
    La notion de largeur arborescente est interprétable en termes de nombre minimum d'agents requis pour rechercher un fugitif dans un réseau. Les stratégies gagnantes des deux camps suggèrent une dualité.
    7. Certificat dual de la tree-width.
    Introduction de la notion de bramble et autres certificats des mesures de largeur arborescente.
    8. Introduction de la notion de clique-width de Courcelle.
    Une mesure de complexité qui capture plus de graphes que la tree-width, et stable par complémentation. Equivalence avec la notion de rank-width de Seymour et Oum

  • Bibliographie :
    Une petite Introduction aux mineurs de graphes, de László Lovász.
    Le Graph Theory, de Reinhard Diestel, est à conseiller. Le chapitre 12, traite de la 'tree-width'.
    Le Parameterized Complexity Theory, de Jorg Flum et Martin Grohe, est une bonne réference pour les algorithmes FPT.
    Pour les plus courageux, la série des Graph Minors de I à XXIII, de Neil Robertson et Paul Seymour, est intéressante à parcourir, pour se rendre compte de la difficulté du résultat.