Édouard Bonnet médaillé de bronze du CNRS pour ses travaux sur les graphes
Très prisés pour décrire des réseaux, les graphes deviennent rapidement énormes dans les applications informatiques. Divers outils algorithmiques sont développés pour les manipuler, qui sont l’objet des travaux d’Édouard Bonnet, chargé de recherche CNRS au Laboratoire de l'informatique du parallélisme (LIP - CNRS/ENS de Lyon/Université Claude Bernard Lyon 1). Ses recherches sur la notion de twin-width représentent ainsi un grand pas dans la décomposition des graphes.
Très tôt passionné par les sciences, Édouard Bonnet savait depuis le collège qu’il voulait devenir chercheur et a poursuivi ce but tout au long de son parcours. Après un master en informatique obtenu à l’ENS Cachan, il soutient une thèse à l’Université Paris Dauphine - PSL sur l’approximation et la complexité paramétrée en 2014. Il enchaîne trois postdoctorats à Budapest, Londres et à l’ENS Lyon avant d’être recruté comme chargé de recherche CNRS au LIP.
« J’aime bien parler de théorie algorithmique des graphes pour décrire mon travail et celui de ma communauté, avance Édouard Bonnet. Je suis à l’intersection de l’étude théorique de leur structure et de leur manipulation par des algorithmes. La majorité des problèmes combinatoires que nous rencontrons s’expriment dans le langage des graphes. » Ils s’illustrent par exemple dans la représentation des réseaux, notamment biologiques, informatiques, routiers et sociaux. Rapidement trop complexes pour être explorés à la main, ils sont traités grâce à des algorithmes qui vont, en particulier, les décomposer en plusieurs graphes plus simples.
Édouard Bonnet s’est démarqué en développant avec ses collègues une nouvelle manière de les décomposer, basée sur la notion de twin-width. Elle est liée à la contraction dynamique d’un graphe en fusionnant ses sommets deux par deux jusqu’à ce qu’il n’en reste plus qu’un. Dans le cadre d’un projet ANR JCJC, Édouard Bonnet approfondit ce concept, qui se montre particulièrement utile dans des applications telles que la logique, la combinatoire énumérative et la vérification de modèles.
La twin-width peut aider à résoudre plus vite des problèmes polynomiaux comme trouver le plus court chemin entre deux points d’un même réseau, ou à mieux approximer des problèmes combinatoires exponentiels tels que la coloration des sommets d’un graphe sans conflit avec un minimum de couleurs, utile notamment en ordonnancement.
Ces questions ramènent à un autre volet du travail d’Édouard Bonnet, qui s’intéresse aux problèmes NP-difficiles. On suspecte pour ces derniers, comme pour celui de la coloration, qu’il n’y ait pas d’algorithme qui les résolve exactement en un temps acceptable. Pour ces problèmes, on se demande s’il est possible de trouver efficacement des approximations, c’est-à-dire des solutions approchées suffisamment satisfaisantes. Édouard Bonnet a ainsi obtenu, avec des collègues, le meilleur algorithme approché pour la recherche du plus grand nombre de points deux à deux à distance d’au plus 1, parmi un ensemble donné de points de l’espace. Ce problème est utile pour le clustering et la recherche de communautés.
La richesse de ces travaux, ainsi que son implication dans l’écosystème de la recherche, valent à Édouard Bonnet de recevoir la médaille de bronze du CNRS. « Je suis content, pour moi comme pour la communauté de la théorie des graphes, se réjouit Édouard Bonnet. Trois de mes co-auteurs ont été récompensés de même par le passé, c’est important que nos thématiques, moins proposées au grand public que l’apprentissage automatique ou l’informatique quantique, soient valorisées. »