Édouard Bonnet : vers de nouveaux outils en théorie des graphes

Des systèmes tels que les réseaux sociaux, les réseaux informatiques ou de télécommunications, les réseaux de transports... peuvent être représentés sous la forme de graphes : un ensemble de points (les sommets), reliés par des lignes (les arêtes). Les problèmes que l'on cherche à résoudre pourront alors être traités par des algorithmes dont l'efficacité, c'est-à-dire le temps nécessaire pour obtenir la solution, dépend de la manière dont on représente le graphe. C'est pourquoi de nombreuses recherches en théorie des graphes portent sur des moyens pour simplifier ou contracter ces objets mathématiques complexes.

Depuis sa thèse, soutenue en 2014 à l'université Paris Dauphine-PSL, Édouard Bonnet a consacré ses recherches à la théorie des graphes. Il a ensuite réalisé trois post-doctorats, à Budapest, à Londres, puis à l'ENS de Lyon, avant de rejoindre le CNRS en 2018, au LIP. Chargé de recherche CNRS, il appartient à une équipe d’une dizaine de chercheurs et chercheuses dont les travaux sont axés sur la théorie et les algorithmes des graphes. 

Comme beaucoup de scientifiques dans ce domaine, Édouard Bonnet s'est intéressé aux moyens de simplifier les graphes afin de faciliter leur résolution. Une solution consiste à les représenter comme une arborescence, afin de les décomposer en graphes plus simples et plus faciles à manipuler. Ainsi est née la notion de tree-width, largeur d'arborescence, qui caractérise la proximité d'un graphe avec la structure d'un arbre (les graphes connexes dont la tree-width vaut au plus 1 sont exactement des arbres). En 2020, Édouard Bonnet et ses collègues ont proposé une notion nouvelle, la twin-width, dont l'objectif est aussi d'appliquer une stratégie de simplification des graphes, mais qui cette fois est dynamique. La contraction dynamique d’un graphe consiste à fusionner ses sommets deux par deux jusqu’à ce qu’il n’en reste plus qu’un. « La twin-width est une notion transversale en théorie des graphes, qui devrait faciliter la résolution de nombreux problèmes dans des domaines très divers », indique Édouard Bonnet. 

Parmi les problèmes qui pourraient bénéficier des avancées de la notion de twin-width : trouver le plus court chemin entre deux points d’un réseau ou le plus court chemin passant par tous les sommets du graphe. Ou encore, le problème de la coloration, qui consiste à attribuer une couleur à chacun de ses sommets de manière à ce que deux sommets reliés par une arête soient de couleurs différentes, le tout avec un minimum de couleurs. Cette dernière question correspond à l'attribution de ressources à différentes tâches, sans conflit. 

Mais avant d'en venir à des utilisations pratiques, des questions théoriques posées par la twin-width doivent trouver leurs réponses et c'est pour s'y attaquer qu'a été lancé le projet ANR JCJC TWIN-WIDTH (2021-2025), coordonné par Édouard Bonnet. Pour ses travaux sur la twin-width, Édouard Bonnet a reçu en 2023 la médaille de bronze du CNRS. Ses recherches sont à nouveau distinguées en 2025, avec le prix Lovelace-Babbage, qui récompense des scientifiques dont les travaux de recherche portent sur tous les domaines de l’informatique et est remis conjointement par l’Académie des sciences et la Société informatique de France (SIF).