Notre objectif est d’étudier l’algorithmique de problèmes d’optimisation motivés par les réseaux de transport, en utilisant des outils algorithmiques et structurels liés aux métriques de graphes.

En effet, un réseau de transport peut être représenté par un graphe dont les sommets sont les points d’intérêt (villes, gares, arrêts de bus, etc), et les arêtes, les connexions entre ces points. Le réseau peut être orienté ou non-orienté, et les arêtes peuvent être munies de données, représentant par exemple la distance entre les deux extrémités, ou le temps de trajet. Cette notion de distance entre les éléments du réseau est formalisée sous la notion mathématique de « métrique ».

Nous pourrons donc utiliser les outils de l’algorithmique et de la théorie des graphes (surtout ceux liés aux métriques de graphes), qui sont essentiels dans le domaines des réseaux de transport (par exemple le calcul de plus courts chemins ou la couverture des réseaux sont des problèmes fondamentaux dans ce domaine et s’expriment dans le langage des métriques de graphes).

Nous étudierons les problématiques suivantes, dans la continuité de nos travaux récents [2,3,5,6,7] :

• Comment couvrir tous les sommets d’un réseau par des lignes de transports en commun ? (couverture par chemins d’un graphe : PATH COVER [3])
• Comment placer des hubs (gares, dépôts de drones...) afin de couvrir l’ensemble du réseau par les plus courts chemins entre ces hubs ? (GEODETIC SET et variantes [5,6])
• Comment rendre un réseau de transport résilient, en détectant aisément des perturbations, comme une liaison dysfonctionnelle ? (surveillance de réseau de type MONITORING SET [3,7])

Résoudre ces problèmes théoriques est important d’un point de vue des applications, car ce sont des problèmes fondamentaux pour le développement d’infrastructures de transport modernes, connectées et intelligentes.

Notre but est d’étudier l’algorithmique de ces problèmes. Un algorithme efficace (c’est-à-dire qui s’exécute en temps polynomial en la taille du réseau) existe-t-il ? Généralement, les problèmes intéressants sont NP-difficiles et un tel algorithme n’existe pas. On peut cependant aborder plusieurs axes, en développant des algorithmes :

1- d’approximation (qui calculent une solution approchée, avec garanties de performances) [2] ;
2- pour des types particuliers de réseaux (classes particulières de réseaux comme les réseaux planaires ou de petite largeur arborescente [3,5,6]).

Notre priorité sera d’aborder ces points en utilisant des paramètres structurels adaptés aux réseaux de transport, en particulier des paramètres liés aux métriques tels que l’hyperbolicité [1] ou la densité de croisement des réseaux de transport [4] qui ont été récemment introduits. L’objectif à terme est de développer des méta-théorèmes algorithmiques, c’est-à-dire des techniques algorithmiques qui s’appliquent à un grand nombre de contextes exprimables en termes de métriques de graphes.

Nous avons publié quelques travaux sur ces sujets les dernières années [2,3,5,6,7] avec divers chercheurs notamment les quatre chercheurs indiens et britannique associés à cette action. Nous souhaitons approfondir cette thématique en généralisant nos résultats préliminaires.

Il s’agit d’une thématique où l’expertise au LIMOS est importante, ainsi L. BEAUDOU et F. FOUCAUD ont des compétences complémentaires sur les métriques de graphes (L. BEAUDOU surtout d’un point de vue structurel, et F. FOUCAUD d’un point de vue algorithmique). L’action inclut plusieurs partenaires internationaux, qui apporteront leurs expertises respectives. Avec P. TALE (IISER Pune, Inde) et D. CHAKRABORTY (Univ. Leeds, Royaume-Uni) qui ont déjà une collaboration forte avec F. FOUCAUD depuis plusieurs années [2,5,6], et trois autres collègues indiens ayant des expertises diverses et également complémentaires. Ces collaborations plus récentes méritent d’être développées et intégrées dans une dynamique de recherche collaborative.

Bibliographie

[1] M. Borassi, D. Coudert, P. Crescenzi, A. Marino. On Computing the Hyperbolicity of Real-World Graphs. Proceedings of ESA 2015.
[2] D. Chakraborty, A. Dailly, S. Das, F. Foucaud, H. Gahlawat, S. Ghosh. Complexity and algorithms for ISOMETRIC PATH COVER on chordal graphs and beyond. Proceedings of ISAAC 2022.
[3] T. Das, F. Foucaud, C. Marcille, Pavan PD, S. Sen. Monitoring arc-geodetic sets of oriented graphs. Theoretical Computer Science 1031:115079, 2025.
[4] D. Eppstein, S. Gupta. Crossing Patterns in Nonplanar Road Networks. Proceedings of ACM SIGSPATIAL 2017.
[5] F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. Mc Inerney, R. Sharma, P. Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. Proceedings of ICALP 2024.
[6] F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. Mc Inerney, R. Sharma, P. Tale. Metric Dimension and Geodetic Set parameterized by vertex cover. Proceedings of STACS 2025.
[7] F. Foucaud, C. Marcille, Z. Myint, Sandeep RB, S. Sen, S Taruni. Bounds and extremal graphs for monitoring edge-geodetic sets in graphs. Discrete Applied Mathematics 366:106-119, 2025.