ANR Twin-width : un projet pour mieux décomposer des graphes

Les graphes sont une manière de représenter des données où les éléments, appelés sommets, sont reliés par des lignes : les arêtes. Ces objets mathématiques deviennent rapidement difficiles à appréhender à l’œil nu passé une certaine taille, mais restent très manipulables par des algorithmes. Différents paramètres ont été identifiés afin de faciliter la tâche, comme la twin-width. Édouard Bonnet, chargé de recherche CNRS au LIP, mène actuellement un projet ANR pour approfondir cette notion.

« On essaye souvent de décomposer les graphes, c’est-à-dire de passer d’un objet a priori complexe à quelque chose de plus simple, détaille Édouard Bonnet. Parmi les notions et les outils de décomposition, on retrouve historiquement le fait qu’appréhender le graphe comme un arbre facilite sa manipulation par des algorithmes. » La largeur arborescente, ou tree-width, est ainsi un nombre qui décrit à quel point la structure d’un graphe est proche de celle d’un arbre, ce qui indique s’il peut être aisément décomposé ou non.

En 2020, Édouard Bonnet et des collègues du LIP et du LAMSADE ont inventé la notion de twin-width dans un article publié dans la revue de l’Association for Computing Machinery1 . Contrairement aux décompositions classiques de graphes, qui sont statiques, la notion est basée sur un processus dynamique de contraction, où l’on fusionne successivement deux sommets du graphe en un seul. La twin-width correspond au nombre maximal d’erreurs attribuées à un sommet lors de la contraction d’un graphe jusqu’à ce qu’il ne reste plus qu’un seul sommet.

• 1Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant. Twin-width I: tractable FO model checking. Journal of the ACM.

La notion de twin-width pourrait faciliter la résolution de différents problèmes. Les deux types principaux sont les problèmes polynomiaux, comme trouver le plus court chemin entre deux points d’un réseau, et les problèmes combinatoires exponentiels, comme dessiner le plus court chemin passant par tous les sommets du graphe. On retrouve également le problème de la coloration, qui consiste à attribuer une couleur à chaque sommet d’un graphe, avec le moins de couleurs possible et sans que deux sommets reliés par une même arête présentent la même couleur. Ce cas de figure se rencontre lorsque l’on souhaite assigner sans conflit des ressources à des agents.

« Comme pour toute notion nouvelle, nous devons répondre à des questions théoriques aussi cruciales que nombreuses sur la twin-width pour rendre compétitives les possibles applications, insiste Édouard Bonnet. L’objectif principal de notre projet ANR est de trouver un algorithme efficace pour calculer, ou du moins, approcher la twin-width. En parallèle, nous avons commencé à généraliser cette notion à d’autres objets mathématiques que les graphes, comme les groupes, et à réinspecter différents problèmes classiques sous le prisme de la twin-width. »

Démarré en octobre 2021, le projet ANR est prévu pour durer jusqu’en 2025. Il est organisé autour d’un consortium de cinq chercheurs permanents, complété par des étudiants en master et en doctorat, ainsi que par des postdoctorants.

Si Édouard Bonnet et ses co-auteurs ont bien inventé la notion de twin-width, le chercheur souligne qu’elle avait été suggérée par deux autres chercheurs dans un article de 2013. Ces travaux concernaient une notion de largeur pour les permutations, qui peuvent être considérées comme une classe particulière de graphes. Leur article indiquait qu’il serait intéressant de tenter de généraliser cette notion aux graphes. « Cette phrase est apparemment passée inaperçue. La twin-width est depuis très reprise et comble un manque théorique qui restait béant depuis un certain temps. »