AGAPE

Algorithmes de graphes paramétrés et exacts.

Résoudre les problèmes difficiles (NP-durs) est un enjeu majeur en informatique. Comme aucun algorithme exact en temps polynomial ne peut être espéré pour de tel problèmes, diverses approches sont considérées pour les résoudre : algorithmes d’approximation, algorithmes randomisés, heuristiques, ... Les algorithmes exponentiels exacts ou paramtrés sont deux approches voisines pour ce faire. La première consiste à trouver un algorithme en temps $O(c^n)$ avec c le plus petit possible afin de pouvoir traiter des instances les plus grandes possibles. La deuxième consiste à isoler des paramètres du problème qui concentrent l’explosion combinatoire de la résolution afin de pouvoir traiter les problèmes sur de grandes instances pour lesquelles ce paramètre reste petit. Plus précisément, on cherche un paramètre $k$ tel qu'il existe un algorithme en temps $O(f(k)P(n))$ avec $f$ une fonction quelqconque de $k$ et $P$ un polynôme en $n$. Ces deux approches se sont très fortement développées depuis le milieu des années 90 et ont obtenu des succès importants aussi bien d’un point de vue pratique que théorique.
Nous renvoyons ceux qui veulent en savoir plus vers les notes de cours de l'Ecole AGAPE.

Le but de l'ANR AGAPE est d'étudier des problèmes NP-durs sur des graphes et plus particulièrement, des problèmes de coloration de graphes et sur les graphes orientés.
Texte de la proposition