Master 2 Parcours CASAR. UMINR341

Algorithmique combinatoire

  • Responsables :
    Stéphane Bessy
    Stéphan Thomassé
  • Calendrier :
    Les cours commenceront le ...
    Ils auront lieu le Mercredi sur le campus St-Priest.
    L'examen aura lieu en Janvier 2007.
  • Prérequis :
    Notions souhaitées, mais pas obligatoires, en théorie des graphes, algorithmique, structure de données, complexité et analyse d'algorithmes (correspondant aux actuels ULIN301, ULIN501, ULIN503, UMINM112).
  • 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.
  • Plan prévisionnel des cours :
    1. Introduction de quelques classes de graphes et des décompositions modulaires et split.
    Ces décompositions fournissent des algorithmique très efficaces en pratique dans certaines classes de graphes (cographes, graphes d'intervalles,...). Cette partie constitue une introduction au paradigme savoir décomposer c'est savoir calculer.
    2. Introduction de la notion de largeur arborescente.
    Tout graphe possède une telle largeur qui 'mesure' combien le graphe est éloigné d'être un arbre. Un arbre a par exemple largeur arborescente égale à 1. Le graphe complet à n sommets a largeur arborescente n-1.
    3. Algorithmique des graphes de largeur arborescente bornée.
    La programmation dynamique fournit des algorithmes en temps linéaire à presque tous les problèmes difficiles de graphes lorsque la largeur arborescente est fixée. Ce résultat est le point de départ de la théorie de la complexité paramétrique.
    4. Reconnaissance de classes de graphe.
    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 est planaire ou pas. La largeur arborescente et le routage dans les graphes sont les clés de ce résultat.
    5. 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. En dépit de son aspect sécuritaire, ce résultat assure que la tree-width vérifie une relation de dualité minimum=maximum.
  • Sujet de stage :
    Le point de vue Graph Searching fera l'objet du stage : Décompositions arborescentes et stratégies d'encerclement.,
  • Bibliographie :
    En anglais, le Graph Theory, de Reinhard Diestel, est à conseiller. Les six premiers chapitres constituent une excellente introduction aux graphes. Le chapitre 12, traitant de la 'tree-width', demande beaucoup plus d'investissement.
    Une recherche sur le web avec mots clés 'largeur arborescente' ou 'tree-width' peut donner une idée de l'état de l'art.