Description du Projet
Enumération dans les graphes et les hypergraphes: algorithmes et complexité
La question "P = NP?" est le problème le plus important en informatique fondamentale. Partant du postulat que les classes de complexité P et NP sont différentes, il y a des problèmes que l'on ne peut résoudre efficacement à l'aide de l'ordinateur. C'est pourquoi il est important de trouver de nouvelles approches pour les aborder, autres que les algorithmes polynomiaux classiques.
Alors que l'optimisation est omniprésente en informatique et que l'on y trouve énormément de travaux sur l'algorithmique et la complexité des problèmes d'optimisation, peu d'attention a été accordée à l'énumération. Un algorithme pour la version "énumération" d'un problème fournira immédiatement une solution optimale pour la version "optimisation" du même problème. Ceci suggère que l'énumération serait nettement plus difficile que l'optimisation, d'où, entre autres, le moindre intérêt des chercheurs pour l'énumération. Cependant, des résultats récents sur la complexité des problèmes difficiles montrent que les relations entre la difficulté de l'énumération et celle de l'optimisation sont plus subtiles et méritent une étude approfondie.
Enumérer les objets satisfaisant certaines propriétés a d'importantes applications dans différents domaines de l'informatique, comme la fouille de données, l'apprentissage et IA, et c'est l'une des motivations de ce projet. Nos objectifs scientifiques sont de nature fondamentale, vers une meilleure compréhension de la complexité des problèmes d'énumération et l'étude des techniques algorithmiques spécifiques à l'énumération. Nous concentrerons nos efforts sur des problèmes d'énumération dans les graphes et hypergraphes et étudierons trois approches complémentaires de l'algorithmique d'énumération.
Pour la plupart des problèmes d'énumération, la quantité d'objets énumérés est exponentielle en la taille de l'entrée, dans notre cas en le nombre de sommets du graphe ou hypergraphe que l'on traite. Ceci a motivé l'approche appelée "output-sensitive" ("par rapport à la sortie"), où le temps d'exécution de l'algorithme est mesuré par rapport à la taille de l'entrée et de la sortie. Cette approche est classique en algorithmique d'énumération et possède une longue tradition. Des recherches récentes sur l'algorithmique exacte pour les problèmes difficiles ont attiré l'attention sur une approche "input-sensitive", où le temps d'exécution dépend uniquement de la taille de l'entrée. Cette méthode pour des problèmes difficiles d'énumération a émergé récemment et s'avère d'une grande importance pour établir des bornes (exponentielles) sur le nombre d'objets énumérés ainsi que pour l'étude de la complexité des algorithmes exacts. Une troisième approche pour la résolution des problèmes d'énumération sur les graphes et hypergraphes est l'utilisation d'algorithmes paramétrés par certains paramètres de largeur, comme la largeur arborescente ou la largeur de clique. Le but est d'établir des méta-théorèmes qui fournissent des algorithmes pour les problèmes d'énumération, en combinant des outils logiques, d'automates et de structure des graphes. Cette partie inclura un travail d’implantation dans le système expérimental AUTOGRAPH, qui permettra de tester l’utilisation en pratique de méta-théorèmes.
En plus des objectifs classiques d’un tel projet réunissant différents groupes de chercheurs français intéressés par l’algorithmique d’énumération dans les graphes (la production de résultats scientifiques, l’acquisition et la mise en commun de connaissances, etc.), nous tâcherons d’établir une communauté française autour de l’énumération et de renforcer ce sujet sur la scène de la recherche internationale en algorithmique. Le porteur de ce projet co-organise cette année un workshop international au Lorentz Center (Leiden, Pays-Bas) qui réunira des chercheurs travaillant dans différents domaines de l’énumération. L’écriture d’un livre sur le sujet serait aussi un excellent moyen d’accorder à l’algorithmique d’énumération la place qu’elle mérite.
