Théorie métrique des graphes – DISTANCIA

Ce projet concerne les fondements et les applications de la théorie métrique des graphes qui étudie la structure et l'algorithmique de classes de graphes dont la métrique satisfait certaines propriétés géométriques des métriques usuelles.

Les champs d'application de cette théorie sont nombreux et variés. Le problème de l'étiquetage pour le calcul de distances dans les réseaux de routes a des applications directes pour les logiciels de navigation. Comprendre les propriétés structurelles des grands réseaux de données est crucial pour analyser et optimiser leur performance, leur fiabilité et leur sécurité. La théorie métrique des graphes s'est révélée également indispensable pour résoudre certaines questions ouvertes dans le domaine de la concurrence, de l'apprentissage automatique et de la théorie géométrique des groupes. Par exemple, les graphes médians jouent un rôle essentiel dans la résolution de la fameuse "Virtual Haken Conjecture". Ils constituent les domaines des structures d'événements de Winskel, l'un des modèles de base de la concurrence. Cette correspondance a été utile pour réfuter les conjectures de Rozoy-Thiagarajan et Thiagarajan's concernant les "nice and regular labelings". Une apparition remarquable des graphes modulaires concerne la classification en complexité du "$0$--extension problem", un problème combinatoire qui a des applications en analyse d'images. De nombreux problèmes algorithmiques concernent les distances : plus courts chemins, centre, diamètre, diagrammes de Voronoi, TSP, clustering, etc. Les distances apparaissent aussi en analyse de données. Les plongements métriques avec faible distorsion sont des outils pour les méthodes métriques sur lesquelles sont basés certains algorithmes d'approximation. Concevoir des structures de données distribuées permettant de répondre rapidement à des requêtes de distances ou de routage sur des (presque) plus courts chemins est un problème fondamental en calcul distribué. Au delà de l'informatique et des mathématiques, la notion de distance est essentielle en archéologie, en bio-informatique, en statistiques et en analyse de données.

Ce projet a pour objectif de contribuer au développement de la théorie métrique des graphes. Cet objectif requiert un large champ d'expertise dans le domaine de la combinatoire, de la géométrie, et de l'algorithmique qui est couvert par les membres du consortium. Une des retombées positives sera le partage de connaissances entre les membres du projet. Nous espérons ainsi créer en France un groupe de chercheurs qui partagent une expertise dans l'étude métrique des graphes. Qu'elles soient de nature structurelle ou algorithmique, les questions de recherche formulées dans le cadre de ce projet sont fortement interconnectées. L'étude des propriétés combinatoires, algorithmiques, géométriques qui apparaissent dans la théorie métrique des graphes et de leurs complexes cellulaires exploitera les similarités structurelles qui émergent de différents champs d'application. Ces nouvelles connaissances permettront de répondre à des questions issues de différents domaine de l'informatique, des mathématiques discrètes et de l'optimisation combinatoire. Nous souhaitons aussi concevoir de nouveaux algorithmes pour les problèmes de distances liés à l'analyse de données, de réseaux, de calcul distribué et de sériation.

Le projet sera organisé autour de deux axes principaux "Structure in metric graph theory" et "Algorithms in metric graph theory'' rassemblant dix thèmes de recherche fortement interconnectés :

S1. Local-to-global characterizations
S2. Median graphs and event structures
S3. Lopsided sets and sample compression
S4. Matroidal structures
S5. Isometric and low distortion embeddings
S6. Packing and covering with balls, identifying codes, and $\chi$-boundedness

A1. Algorithmic aspects of hyperbolic graphs
A2. Algorithms for graph classes from MGT
A3. Finite metric spaces: approximation and realization
A4. Seriation and classification.