Blair SULLIVAN

Un des grands défis dans l’analyse de réseaux à grande échelle est que beaucoup de problèmes d’optimisation sont très difficiles à résoudre par ordinateur (on dit qu’ils sont NP-difficiles).
Heureusement, les réseaux réels — comme les réseaux sociaux, routiers ou biologiques — ont souvent des structures particulières. Par exemple, les réseaux sociaux forment des groupes, les routes sont presque toujours organisées de façon planaire, et les réseaux biologiques ressemblent souvent à des arbres.
Les algorithmes paramétrés sont une approche qui permet de tirer parti de ces structures pour résoudre certains problèmes plus efficacement. Mais jusque-là, ces méthodes restent peu utilisées en pratique, souvent à cause d’hypothèses trop fortes ou de difficultés techniques.
Ce projet cherche à réduire cet écart entre théorie et pratique en combinant une nouvelle approche (appelée twin-width) avec une méthode appelée modification de graphe. Pour avoir un impact concret dans la société, les premières applications viseront des domaines comme la robotique, le calcul scientifique, et l’équité dans les algorithmes.