William Lochet et l'algorithmique des graphes

Quel est votre domaine de recherche ?

Mon domaine de recherche se situe essentiellement autour de l'algorithmique des graphes. Les graphes sont des objets mathématiques élémentaires, composés de sommets et d'arêtes reliant ces sommets et permettant de représenter un très grand nombre d'objets comme des plans de transports ou des réseaux sociaux. Ainsi, de nombreuses problématiques peuvent se modéliser en des questions algorithmiques sur les graphes. Malheureusement, une grande partie des problèmes élémentaires sur les graphes sont NP difficiles, ce qui rend l'existence d'algorithmes polynomiaux peu probable. Pour comprendre ces problèmes plus en détails, plusieurs paradigmes ont été étudiés, le plus ancien étant de trouver des algorithmes d'approximations, et donc qui ne cherche pas forcément une solution optimale. Un paradigme plus récent, et qui m'a beaucoup intéressé ces dernières années, est celui de la complexité paramétrée, dont le but est d'étudier la complexité du problème en fonction de certains paramètres de l'instance. Un exemple typique de paramètre est la taille de la solution optimale, mais on peut aussi citer le genre de la plus petite surface dans lequel le graphe peut se plonger. L'idée est d'essayer d'avoir une compréhension plus fine de ce qui rend un problème vraiment difficile, mais aussi d'avoir des algorithmes qui peuvent être efficaces sur certaines classes d'instances.

Qu’avez-vous fait avant d’entrer au CNRS ? Pourquoi avoir choisi le CNRS ?

J'ai d'abord effectué une thèse entre l'Université Côte d'Azur et l'ENS de Lyon en théorie des graphes, encadré par Frédéric Havet et Stéphan Thomassé. Je m'intéressais alors essentiellement à des questions structurelles en théorie des graphes. En particulier, je cherchais à comprendre les propriétés (degré, coloration) que doivent satisfaire les graphes pour lesquels certaines structures sont interdites. Ma transition vers une étude plus algorithmique de ces objets est arrivée après ma thèse, lorsque j'ai effectué un post-doc dans l'équipe Algorithm de l'Université de Bergen, en Norvège, où j'ai essentiellement collaboré avec Saket Saurabh et Fedor Fomin.
Le CNRS offrant une liberté et des conditions inédites pour faire de la recherche, le choix m'apparaissait évident pour continuer ma carrière, et ce d'autant plus que la communauté graphe est très développée en France.

Qu’est-ce qui vous a amené à faire de l’informatique et/ou des sciences du numérique ?

Il n'y a pas vraiment eu de déclic particulier. Mes parents m'ont transmis depuis tout petit leur passion pour les mathématiques, ce qui a guidé ma scolarité. J'ai tout de suite été attiré par la théorie des graphes parce que ce sont des objets très simples, avec des preuves souvent élémentaires et élégantes. L'étude de ces objets étant essentiellement motivée par des problématiques algorithmiques, il me semblait alors naturel de m'orienter dans cette direction.