Décompositions des graphes et algorithmes – GRAAL

Ce projet se situe aux fondements de l'informatique théorique, et est centré sur l'étude des décompositions de graphes tant d'un point de vue structurel qu'algorithmique.Nous proposons de combiner les approches issues de la théorie des graphes et de l'algorithmique avec elles issues des théories de langages formels et de la logique. En effet l'utilisation des relations logiques afin de représenter les graphes et de formaliser les propriétés de ces graphes devrait nous permettre d'établir de nouvelles relations entre la complexité paramétrée, les algorithms FPT et la logique. Quant aux applications algorithmiques nous proposons d'étudier les formalisations algébriques des propriétés utilisées dans les algorithmes de décomposition existants. Les compréhensions fines de ces méchanisms algorithmiques devraient nous permettre d'étendre nos algorithms à d'autres structures combinatoires tout en gardant leurs performances. Nous avons la conviction que les aspects logiques, combinatoires et algorithmiques des décompositions sont fortement imbriqués. Ce projet rassemble des spécialistes internationalement reconnus des laboratoires LaBRI, LIAFA et LIRMM et nous sommes convaincus que cette association unique de compétences devrait permettre l'obtention de résultats importants tant d'un point de vue théorique qu'applicatif.