DS0704 - Fondements du numérique

Enumération dans les graphes et les hypergraphes: algorithmes et complexité – GraphEn

Enumération dans les graphes et hypergraphes : algorithmes et complexité

L'enumeration des objets bien spécifié au rapport du type ou des propriétés est une tâche fondamental en algorithmique qui a des nombreuses applications dans des divers domaines de l'Informatique et dans vie réel. On va se concentrer sur les problèmes des graphes et hypergraphes et étudier trois approches différents pour la construction des algorithmes d'énumération.

Les buts du projet sont la nature théorique et orientés vers une meilleure comprehension de la complexité d'énumération et l'étude des techniques algorithmiques

Étude des approches principales pour la constructions algorithmes d'énumération: classique approche output-sensitive et les approches proposés récemment input-sensitive et énumération paramètrisés

Les approches output-sensitive et input-sensitive sont étudiés d'un point de vue théorique. L'étude d'énumération paramètrée est orienté vers des logiciels efficaces et pratiques.

Algorithmes et logiciels pour la résolution des problèmes dénumeration, techniques algorithmic nouveaux. Organisation d'une école été et des workshop international sur l'énumération algorithmique

Etablir l'énumération algorithmique comme un domaine important de l'Algorithmique et Complexité

Publications des résultats dans des journaux scientifiques et des conférences
bien connu de l'Informatique Fondamental et de l'algorithmique

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.

Coordinateur du projet

Monsieur Mathieu Liedloff (Laboratoire d'informatique théorique et appliquée)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LITA Laboratoire d'informatique théorique et appliquée
LIMOS Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes
LaBRI Laboratoire Bordelais de Recherche en Informatique

Aide de l'ANR 398 320 euros
Début et durée du projet scientifique : septembre 2015 - 48 Mois

Liens utiles