proposition de thèse, algorithmique et graphes dynamiques. PhD Proposal, algorithms for dynamic grap

Non french-speaking candidates should directly contact Eric Sanlaville (see email below) for details.

Sujet de thèse proposé :

Questions de connexité dans les graphes dynamiques. Classification des problèmes et des algorithmes. Application aux systèmes complexes et à la logistique.

Laboratoire d’accueil :

LITIS, Université le Havre Normandie Encadrants : Stefan Balev, Yoann Pigné, Eric Sanlaville

Court descriptif du sujet

Les systèmes complexes s'organisent en réseaux qui modélisent les interactions entre leurs composants. Une des caratéristiques de tels systèmes, naturels ou artificiels, est leur dynamicité qui se traduit par la nature fortement évolutive du réseau d'interaction. Par exemple, cette dynamicité est issue en logistique de la disponibilité variable des moyens de transport (navires, trains,...), et des aléas sur le réseau de transport (congestion, travaux). L'outil de base pour analyser de tels systèmes est donc le graphe dynamique. Des questions clés pour l'analyse concernent la connectivité au sens large ; cette notion permet d'attaquer des problèmes issus de la logistique comme l'acheminement d'informations, d'énergie, de marchandises, de voyageurs d'un noeud du réseau à un autre. Mais bien d’autres applications sont concernées. Les graphes dynamiques font l’objet d’un nombre croissant d’études, mais souvent associées à des applications particulières. Une question fondamentale concerne les problèmes que l’on veut étudier sur ces graphes : quand leur version dynamique crée-t’elle des difficultés spécifiques ? Certains problèmes peuvent en effet se ramener à des problèmes classiques comme la coloration d’un graphe statique, d’autres (flots, ensembles couvrants,...) sont nettement plus difficiles en dynamique. Le premier objectif de cette thèse est de chercher à caractériser ce qui rend un problème dynamique, issu des questions de connexité, spécifique. Pour ce faire, nous étudierons à la fois les classes de graphes dynamiques et leur impact sur la question posée, et le type d’algorithmes qui résolvent cette question. Le second objectif est d’aboutir aux algorithmes les plus efficaces en dynamique. Nous commençons juste, au sein de l’équipe et via différentes collaborations, à comprendre les facteurs clés qui nous permettront de répondre à ces questions (thèse de M. Vernet, post doc de J. Schoeters, soumission d’un projet ANR en 2022). Comme écrit plus haut, la thèse se focalisera sur certains problèmes classiques en lien avec la connexité, comme : Qu’est ce qu’une composante connexe dynamique et comment les identifier ; arbres couvrants, arbres de Steiner ; problèmes de voyageurs de commerce, de tournées de véhicules,... Notre point de vue sera essentiellement algorithmique.

Présentation de l’équipe de recherche

L’équipe RI2C : Réseau d’Interaction, Intelligence Collective, principale équipe de recherche du laboratoire d’informatique LITIS présente au Havre (19 enseignants chercheurs), se positionne depuis des années sur les systèmes complexes. Ses membres animent le réseau Normand des systèmes complexes et sont bien identifiés dans la communauté nationale. En région, les graphes dynamiques prennent une place grandissante dans l’axe transversal « Graphes » de la fédération Normastic, et comme outil de modélisation au sein du RIN CTM (voir le projet RIN Dynamic Network avec le GREYC, des stages et des thèses communs). Au niveau national, notre objectif est de nous positionner comme un des leaders pour l’étude de ces graphes, sous les points de vue fondamental et appliqué. En parallèle, l’équipe met depuis des années ses compétences au service des applications en logistique, que ce soient l’optimisation du passage portuaire, les systèmes d’informations logistique, les réseaux de transport,... La thèse proposée vise donc à joindre deux priorités du laboratoire : des travaux fondamentaux sur les systèmes complexes, et le domaine applicatif de la logistique.

Positionnement à l’échelle internationale 

Les graphes dynamiques focalisent l’attention d’un nombre croissant d’équipes de recherche dans le monde. Cette attention vient de l’importance et la variété des domaines scientifiques où les graphes dynamiques s’imposent comme un outil de modélisation majeur . Elle a donné lieu récemment à un nombre croissant de travaux plus amont, cherchant à caractériser les spécificités des graphes dynamiques, des problèmes qu’ils posent, des algorithmes associés. Une nouvelle communauté se crée, en particulier en Europe. Maintenant bien identifiés au sein de la communauté pluri-disciplinaire des systèmes complexes (colloques Complex Networks), les graphes dynamiques ont fait l’objet l’an dernier d’un séminaire à Dagstuhl, et cette année d’un premier congrès dédié. Notre équipe collabore depuis des années avec celle du professeur Drozdowski de Poznan (PHC Polonium, séjours croisés) à la fois sur les aspects fondamentaux et sur l’optimisation portuaire, la thèse renforcera cette coopération.

Profil du ou de la candidate.

Nous cherchons des profils issus de l’informatique ou des mathématiques appliquées, avec des compétences en Recherche Opérationnelle et en Algorithmique. Une connaissance approfondie des graphes est nécessaire, si possible à la fois d’un point de vue structurel et algorithmique, mais une expérience préalable des graphes dynamiques n’est pas requise. Les candidats doivent envoyer aux 3 encadrants CV et motivation, plus les cours suivis en Master avec les notes éventuelles, avant le 9 mai 2022.

adresses électroniques des encadrants :

{stefan.balev, yoann.pigne, eric.sanlaville}@univ-lehavre.fr

Sélection Bibliographique

                                                    Références de l’équipe d’accueil

- Balev,S. , I. Lamprou, J.L. Jimenez Laredo, Y. Pigné, E. Sanlaville (2020) Cops and Robber on Dynamic Graphs:Offline and Online Case. International Colloquium on Structural Information and Communication Complexity SIROCCO 2020 (pp. 203-219). Springer, Cham. - Bourgeais, Q. Réseaux dynamiques dans les sports collectifs: analyse et applications, thèse de l’université de Rouen Normandie, co-encadrée par L. Seifert (CETAPS), R. Charrier (LITIS), E. Sanlaville. Débutée en novembre 2021. - Dutot, A., F. Guinand, D. Olivier, and Y. Pigné (2007). Graphstream: A tool for bridging the gap between complex systems and dynamic graphs. In Emergent Properties in Natural and Artificial Complex Systems. Satellite Conference within the 4th European Conference on Complex Systems (ECCS’2007). - Guinand,F., Y. Pigné (2015). Time considerations for the study of complex maritime networks. In Maritime Networks: Spatial structures and time dynamics, Routledge, pp.163-189. - Tirico, M., Balev, S., Dutot, A., & Olivier, D. (2018). Morphogenesis of Complex Networks: A Reaction Diffusion Framework for Spatial Graphs. In International Conference on Complex Networks and their Applications (pp. 769-781). Springer, Cham. - Vernet, M., Pigné, Y., Sanlaville, E. (2022), A Study of Connectivity on Dynamic Graphs: Computing Persistent Connected Components, accepted (march 2022) in 4’OR : quarterly of Operations Research (short version : algotel 2020). - Vernet, M : Modèles et algorithmes pour les graphes dynamiques, thèse de l’université Le Havre Normandie, 19 octobre 2020. Directeur E. Sanlaville, co-encadrant Y. Pigné. - Vernet, M. M. Drozdowski, Y. Pigné, E. Sanlaville (2020). A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs. Discrete Applied Mathematics, ⟨10.1016/j.dam.2019.12.012⟩. - Vernet, M., Balev, S., Pigné, Y., Sanlaville, E. (2020). On the complexity of the Dynamic Steiner Tree problem, working paper.

                                                    Références externes (positionnement, collaborations)

- Bhadra,S., and A. Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Proceedings of the 2nd International Conference on Ad Hoc, Mobile and Wireless Networks (AdHoc-Now), pages 259–270, Montreal, Canada, 2003. Springer. - Enright, J., K. Meeks, and F. Skerman. Assigning times to minimise reachability in temporal graphs. Journal of Computer and System Sciences, 115:169–186, 2021. - Holme, P. (2015). Modern temporal network theory: a colloquium. The European Physical Journal B 88 (9), 234. - Casteigts, A., Chaumette, S., & Ferreira, A. (2009, May). Characterizing topological assumptions of distributed algorithms in dynamic networks. In International Colloquium on Structural Information and Communication Complexity (pp. 126-140). Springer, Berlin, Heidelberg. - Fluschnik, T., H. Molter, R. Niedermeier, M. Renken, and P. Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806:197–218, 2020. - Schoeters, J : Contributions to temporal graph theory and mobility-related problems, thèse de l’université de Bordeaux, 29 mars. Directeur A. Casteigts, rapporteur E. Sanlaville (actuellement post doc ULHN). - SAND 2022 - 1st Symposium on Algorithmic Foundations of Dynamic Networks (Online Event, 28-30 march).