GRALMECO - Algorithmique des problèmes de couverture métriques dans les graphes

Nous souhaitons étudier la complexité algorithmique de problèmes métriques de couverture dans les graphes. Leurs applications incluent le routage et la surveillance de réseaux de communication et de transport, la recherche d'information dans les bases de données, l'apprentissage automatique. Ils posent des défis techniques importants, car la plupart des méthodes classiques utilisées pour des problèmes plus locaux échouent ici. Nos objectifs sont: (1) exhiber des propriétés communes des entrées qui rendent ces problèmes algorithmiquement difficiles ; (2) développer des algorithmes efficaces pour des classes adaptées. Nous utiliserons de façon innovante des paramètres structurels de graphes adaptés aux propriétés métriques (tels que distance VC dimension, longueur arborescente ou hyperbolicité) ainsi que des paramètres structurels introduits récemment (MIM-width et twin-width). Nous explorerons différents paradigmes : les algorithmes d'approximation, paramétrés et d'énumération.