Décompositions de Structures Relationnelles et Optimisation Combinatoire – DORSO

Ce projet traite d'aspects fondamentaux de l'informatique, à savoir, des aspects théoriques des décompositions des graphes, hypergraphes et autres structures combinatoires. Ces dernières décennies, de nombreuses techniques de décompositions ont été définies et ont aidé à prouver des conjectures et à concevoir des nouveaux algorithmes. Nous pensons que d'autres applications peuvent être trouvées mais qu'une connaissance approfondie de ces décompositions est nécessaire à l'émergence de résultats réellement innovant. C'est pourquoi nous voulons nous concentrer et développer quelques points précis de la théorie des décompositions.

Les graphes sont des structures simples et naturelles qui capturent une large portion de la complexité. Ils permettent de traduire des problèmes issus de nombreux domaines, comme les réseaux, la biologie, ou plus récemment les scienes sociales. Pour le résoudre, le paradigme « diviser pour régner » conduit directement aux décompositions de graphes, et effectivement, de nombreux algorithmes utilisent des techniques de décompositions. Ces décompositions sont aussi importantes d'un point de vue théorique.

Il n'est donc pas surprenant que les décompositions des graphes aient été l'objet d'intenses recherches. La littérature en regorge (décomposition modulaire, en clique...) et certaines, comme la décomposition arborescente ont même été redécouvertes plusieurs fois.

La décomposition arborescente est l'une des décompositions ayant trouvé le plus d'applications. La largeur arborescente mesure l'écart qu'il y a entre un graphe et un arbre. Les graphes de faible largeur se comportent comme des arbres et de nombreux problèmes NP-complets leurs sont décidables efficacement. Plus précisément, tout problème exprimable dans une certaine logique peut être résolu en temps linéaire pour n'importe quelle classe de graphes de largeur arborescente bornée. Bien que ces algorithmes aient une constante caché importante (au moins exponentielle en la largeur), ils ont trouvés des applications dans des heuristiques, par exemple pour le voyageur de commerce. Les graphes de contrôle de flot des langages structurés sont aussi de faible largeur, ce qui permet de bon algorithmes d'utilisation des registres. D'un point de vue théorique, la largeur arborescente entretient des liens étroits avec la relation de minoration. Cette dernière est un belordre sur les graphes. Ce résultat constituait la « conjecture de Wagner » et les décompositions arborescentes sont un ingrédient clef de sa preuve.

Les succès des décompositions arborescentes ont motivé de nombreuses extensions dans des directions diverses. De efforts ont été fait pour obtenir des décompositions plus fortes que la largeur arborescente. En effet, les graphes complets sont très simple mais leur largeur arborescente n'est pas bornée. Cela à conduit à la notion de largeur de clique par Courcelle. D'autres auteurs ont généralisés ces décompositions à d'autre structures plus générales comme les matroïdes. De leur côté, les hypergraphes et les structures relationnelles permettent de mieux modéliser les bases de données que les graphes. Les décompositions arborescentes s'y applique aussi mais des variantes comme l'hyper largeur arborescente fonctionne mieux.

Bien que ces décompositions aient déjà une longue histoire, il reste beaucoup à faire. Par exemple, il a fallu 21 ans pour publier les 20 articles de la preuve de la conjecture de Wagner et peu de monde la comprend réellement. Dans le même temps, certains résultats très généraux mais aussi de nombreux résultats épars ont été obtenus et il serait bon de les rassembler et les unifier. Ce processus de nettoyage peu permettre de nouvelles extensions, et c'est ce que nous comptons faire dans ce projet en sélectionnant quelques sous domaines particuliers de cette vaste théorie.