Algorithmes de graphes parametres et exacts – AGAPE

En théorie classique de la complexité, un problème est considéré comme non résoluble s'il ne peut pas être résolu en termps polynomial. Or de nombreux problèmes pratiques se modélisent naturellement par des problèmes de graphes qui sont NP-durs et donc pour lesquels il n'existe pas d'algorithme en temps polynomial (sauf si P=NP). Ainsi trouver des solutions à ces problèmes est un enjeu important. Parfois des solutions approchées (mais non optimales) sont suffisantes mais dans d'autres cas la solution optimale est absolument nécessaire. L'objectif de ce programme de recherche est de développer de nouvelles techniques pour résoudre eactement des problèmes NP-durs sur les graphes. Pour cela, nous envisageons deux approches qui sont deux moyens assez proches pour réduire l'explosion combinatoire des problèmes NP-durs. Elles ont de nombreux liens allant de questions très pratiques en conception d'algorithmes à des problèmes théoriques de complexité. · La première approche est la recherche d'algorithmes exponentiels exacts en temps exponentiel de base c avec c une constante la plus proche de 1 possible. Alors avec la puissance de calcul toujours grandissante, on peut espérer pouvoir traiter ces problèmes si c n'est pas trop grand. · La seconde approche est la résolution à paramètre fixé. L'idée est d'isoler des paramètres du problème qui sont censés être petits pour certaines applications et de développer des algorithmes dont le temps de calcul est polynomial en la taille de l'instance mais dépend arbitrairement de ces paramètres. Ainsi tant que les paramètres restent petits, le problème est considéré comme soluble. Le choix du paramètre adequat permettant une grande flexibilité, les algorithmes à paramètre fixé ont montré leur efficacité dans des domaines aussi divers que la bio-informatique, les bases de données, la linguistique ou la vérification automatique. L'originalité de notre proposition est de combiner des outils de théorie des graphes, comme des théorèmes structurels, la méthode probabiliste ou la méthode de déchargement avec des outils algorithmiques tels que "Mesurer et conquérir" ou le principe d'inclusion-exclusion, afin d'obtenir des algorithmes efficaces. Pour estimer leur efficacité pratique, ceux-ci seront implémentés dans Mascopt afin d'être comparés avec d'autres algorithmes