Author: David COUDERT

• Christophe Crespelle, Professor, Université Côte d’Azur, France
• Arnaud Casteigts (referee), Professor, University of Geneva, Switzerland
• Daniele Marinazzo (referee), Professor, University of Ghent, Belgium
• Guillaume Dalle, Researcher, École nationale des ponts et chaussées, Paris, France
• Romain Veltz, Researcher, Centre Inria d’Université Côte d’Azur, France
• David Coudert (supervisor), Senior Researcher, Centre Inria d’Université Côte d’Azur, France

Abstract: This thesis develops computational methods for the analysis of temporal networks, with an emphasis on applications to neuroscience. Temporal graphs provide a natural representation for dynamic systems in which interactions evolve over time, such as functional connectivity in the human brain. As a relatively recent area of study, temporal graph theory still requires the development of dedicated tools and generalizations of classical static methods. To address this gap, new metrics are proposed to extend classical notions, such as clustering coefficient, path length, and small-worldness, into the temporal domain. These are designed to capture both local and global structure while respecting the causality imposed by time. A novel null model, the Random Temporal Hyperbolic model, is introduced to simulate the small-world property observed in brain dynamics while randomizing other topological features. This provides a meaningful baseline for the statistical evaluation of temporal connectivity patterns. A machine learning framework is also introduced to identify task-relevant subnetworks from temporal connectivity data. This approach integrates Shapley values to quantify the contribution of each subnetwork to the model’s predictions. Applied to fMRI recordings during naturalistic stimuli, the framework reveals interpretable patterns in how different brain regions support narrative comprehension, aligning with current cognitive neuroscience theories. To support and generalize these computational approaches, I contributed to developed GraphNeuralNetworks.jl, an open-source Julia package for building and training graph neural networks on static, temporal, and heterogeneous graphs. This flexible and performant software enables rapid experimentation with modern graph-based learning models and is used here in the context of both brain decoding and traffic forecasting. Altogether, this thesis introduces a collection of reusable mathematical, algorithmic, and software tools designed for modeling and analyzing temporal graphs, while contributing to our understanding of the brain’s dynamic architecture. Though they were initially developed in neuroscience, these methods can be applied to a broad range of disciplines that deal with evolving relational data.

Résumé: Cette thèse développe des méthodes computationnelles pour l’analyse des réseaux temporels, avec un accent particulier sur les applications en neurosciences. Les graphes temporels offrent une représentation naturelle des systèmes dynamiques dans lesquels les interactions évoluent au fil du temps, comme la connectivité fonctionnelle dans le cerveau humain. En tant que domaine d’étude relativement récent, la théorie des graphes temporels nécessite encore le développement d’outils dédiés et la généralisation de méthodes classiques issues du cadre statique. Pour combler cette lacune, de nouvelles métriques sont proposées afin d’étendre des notions classiques, telles que le coefficient de clustering, la longueur des chemins et le caractère petit-monde, au domaine temporel. Ces métriques sont conçues pour capturer à la fois la structure locale et globale tout en respectant la causalité imposée par le temps. Un nouveau modèle nul, appelé modèle hyperbolique temporel aléatoire, est introduit afin de simuler la propriété de petit-monde observée dans les dynamiques cérébrales tout en rendant aléatoire d’autres caractéristiques topologiques. Ce modèle fournit une base pertinente pour l’évaluation statistique des motifs de connectivité temporelle. Un cadre d’apprentissage automatique est également introduit pour identifier les sous-réseaux pertinents à partir des données de connectivité temporelle. Cette approche intègre les valeurs de Shapley pour quantifier la contribution de chaque sous-réseau aux prédictions du modèle. Appliqué à des mesures réalisées par IRMf lors de stimuli naturels, ce cadre révèle des motifs interprétables illustrant comment différentes régions cérébrales soutiennent la compréhension narrative, en accord avec les théories actuelles en neurosciences cognitives. Pour soutenir et généraliser ces approches computationnelles, j’ai contribué au développement de GraphNeuralNetworks.jl, une bibliothèque open-source en Julia dédiée à la construction et à l’entraînement de réseaux neuronaux sur graphes statiques, temporels et hétérogènes. Ce logiciel flexible et performant permet des expérimentations rapides avec les modèles modernes d’apprentissage sur graphes, et est utilisé ici dans le contexte du décodage cérébral et de la prévision du trafic. Dans l’ensemble, cette thèse introduit un ensemble d’outils mathématiques, algorithmiques et logiciels réutilisables, conçus pour modéliser et analyser les graphes temporels, tout en contribuant à notre compréhension de l’architecture dynamique du cerveau. Bien que développées initialement pour les neurosciences, ces méthodes peuvent être appliquées à un large éventail de disciplines traitant de données relationnelles évolutives.

• Marthe Bonamy, CRCN CNRS, LaBRI, Bordeaux, France
• Louis Esperet (referee), DR CNRS, INP Grenoble, France
• Ararat Harutyunyan, MCF, Université Paris-Dauphine, France
• Alexander Scott (referee), Professor, University of Oxford, UK
• Stéphan Thomassé, Professor, ENS Lyon, France
• Anders Yeo (referee), Professor, University of Southern Denmark
• Frédéric Havet (supervisor), DR CNRS, COATI, France
• Stéphane Bessy (co-supervisor), Professor, LIRMM, University of Montpellier, France

Abstract: This thesis focuses on a notion of colouring of digraphs introduced by Erdös and Neumann-Lara in the late 1970s, namely the dicolouring, and its associated digraph parameter: the dichromatic number. It appears in the last decades that many classical results on graph colouring have directed counterparts using these notions.
We first give a collection of bounds on the dichromatic number of digraphs for which the underlying graph is chordal. We then introduce a notion of variable degeneracy for digraphs which leads to a more general version of Brooks Theorem. We also strengthen this theorem on a large class of digraphs which contains digraphs without antiparallel arcs.
Next we prove a collection of results on $k$-dicritical digraphs, the digraphs that are minimal obstructions for the $(k-1)$-dicolourability. We first generalise a result of Gallai to the directed case, and then prove a conjecture of Kostochka and Stiebitz in the particular case $k=4$. We also discuss the maximum density of such digraphs and prove that the number of $3$-dicritical semi-complete digraphs is finite. We then give a collection of results on the substructures in large dicritical digraphs.
We finally study the notion of redicolouring for digraphs. In particular, we prove that a large collection of evidences for Cereceda’s conjecture admit a directed counterpart.

Résumé: Cette thèse est dédiée à l’étude de la dicoloration, une notion de coloration pour les digraphes introduite par Erdös et Neumann-Lara à la fin des années 1970, ainsi que le paramètre qui lui est associé, à savoir le nombre dichromatique. Lors des dernières décennies, ces deux notions ont permis de généraliser de nombreux résultats classiques de coloration de graphes.
Nous commençons par donner différentes bornes sur le nombre dichromatique des digraphes dont le graphe sous-jacent est un graphe cordal. Ensuite, nous améliorons la borne donnée par le théorème de Brooks pour les digraphes sans arcs antiparallèles et introduisons une notion de dégénérescence variable pour les digraphes, ce qui nous permet de prouver une version plus générale du théorème de Brooks.
Nous étudions ensuite les digraphes $k$-dicritiques, c’est-à-dire les obstructions minimales à la $(k-1)$-dicolorabilité. En particulier, nous généralisons un résultat de Gallai au cas dirigé, et nous prouvons une conjecture de Kostochka et Stiebitz dans le cas particulier $k=4$. Nous discutons également la densité maximum de tels digraphes, et prouvons qu’il n’y a qu’un nombre fini de digraphes semi-complets $3$-dicritiques. On donne par la suite certains résultats structurels sur les digraphes dicritiques de grand ordre.
Enfin, nous étudions la notion de redicoloration pour les digraphes. En particulier, nous prouvons que de nombreux résultats soutenant la conjecture de Cereceda se généralisent au cas dirigé.

• André-Luc Beylot (referee), Toulouse INP ENSEEIHT, France
• Walid Dabbous, Inria, France
• Andrzej Duda, Grenoble INP Ensimag, France
• Isabelle Guérin-Lassous (referee), Université Lyon 1, France
• Samer Lahoud (referee), Dalhousie University, Canada
• Hervé Rivano, INSA Lyon, France
• Catherine Rosenberg, University of Waterloo, Canada

Résumé: Ce document retrace mes travaux sur la modélisation et l’optimisation des réseaux sans fil. J’applique des méthodes d’optimisation, principalement la programmation linéaire, pour calculer des solutions optimales et analyser leurs structures afin d’appliquer des techniques comme la génération de colonnes, ou évaluer des solutions approchées permettant de passer à l’échelle.
La première partie porte sur l’utilisation de drones afin de couvrir ou recharger des capteurs fixes ou mobiles. Les modèles optimisent le nombre de drones nécessaires ou calculent les trajectoires optimales. Les résultats mettent en évidence les compromis entre la distance parcourue en vol, l’énergie dépensée par les drones, et l’altitude impactant la qualité de couverture et de recharge.
La deuxième partie s’intéresse à la capacité des réseaux LoRaWAN en terme de nombre de nœuds tout en garantissant un taux de livraison des transmissions. J’optimise l’allocation des facteurs d’étalement et l’ordonnancement des transmissions dans des réseaux synchronisés tout en respectant les contraintes règlementaires d’utilisation de la bande de fréquence. Les résultats montrent l’intérêt du contrôle de puissance et de la répétition des envois de paquets.
Je conclus sur des perspectives autour de la dynamique des réseaux aériens, des nouvelles technologies pour les réseaux LPWAN, et des réseaux du futur virtualisés.

• Leszek GASIENIEC (referee), University of Liverpool, UK
• David PELEG (referee), Weizmann Institute of Science, Israel
• Christian SCHEIDELER (referee), University of Paderborn, Germany
• Pierluigi CRESCENZI Gran Sasso Science Institute, Italie
• Giovanni NEGLIA, Inria, France
• Laurent Viennot, Inria, Paris

Résumé: Cette présentation se concentre sur l’intersection du problème du sous-ensemble sléatoire (RSSP) et de ses applications novatrices au sein des réseaux de neurones artificiels (ANNs). Après un voyage rétrospectif qui couvre une décennie de recherche, l’exposé touche non seulement dans les contributions de l’auteur à la science informatique théorique, y compris les problèmes de consensus sous communication stochastique dans les systèmes multi-agents, mais s’aventure également dans les domaines de la modélisation d’évaluation intégrée et des explorations en neurosciences computationnelles. En synthétisant des intérêts de recherche allant de l’analyse stochastique des algorithmes distribués au développement d’algorithmes de pruning pour les ANNs, l’exposé vise à partager les contributions de l’auteur à la science informatique théorique et au-delà, en esquissant des orientations de recherche futures à l’intersection de l’informatique et d’autres sciences appliquées.

• Christophe Crespelle, Professor, Université Côte d’Azur, I3S, CNRS, France.
• Guillaume Ducoffe, Associate Professor, Faculty of Mathematics and Informatics, University of Bucharest, Romania.
• Arnaud Malapert, Maître de conférences, Université Côte d’Azur, I3S, CNRS, France.
• Cyril Gavoille (reviewer), Professor, LaBRI, Université de Bordeaux, France.
• Dimitrios M. Thilikos (reviewer), Directeur de recherche, LIRMM, Université de Montpellier, CNRS, Montpellier, France.
• Nicolas Nisse (supervisor), Chargé de recherche, Inria, Université Côte d’Azur, CNRS, I3S, Sophia-Antipolis, France.

Abstract: Graph decompositions are a powerful tool aimed to divide a graph into several parts, called bags, connected in a tree-like or a path-like fashion, depending on whether we consider a tree-decomposition or a path-decomposition. They can be used to solve some NP-hard problems in linear time, as long as the maximum size of the bags (i.e. the width) is bounded. This has motivated the study of treewidth (minimum width out of all tree-decompositions of a graph) over the past 30 years. Nevertheless, there are still a lot of open questions, such as the computational complexity of treewidth in planar graphs. To answer this question, it could be interesting to study the length of these decompositions. This measure corresponds to the maximum diameter among the bags of a decomposition, and it was shown that there is a relationship between treelength and treewidth in planar graphs.

In chapter 2, we study the treelength of several simple classes of planar graphs, such as series-parallel graphs. We give an infinite list of forbidden isometric subgraphs for series-parallel graphs of treelength 2. This list is then used to decide in polynomial time if a series-parallel graph has treelength at most 2 and, in case of a positive answer, to output a decomposition of length at most 2.

In chapter 3, we focus on the pathlength, and we give a characterization for trees and cycles. We also study the pathlength of outerplanar graphs for which we design an approximation algorithm with additive ratio 1.

Finally, in chapter 4, we study the Hunters and Rabbit game, an algorithmic variant of path-decomposition defined as a pursuit-evasion game. In this game, a group of hunters hunts an invisible rabbit which is forced to move to a neighboring position at every step. We are interested in the minimum number h(G) of hunters needed to catch the rabbit, independently of its moves along a graph G. This game has already been studied for some bipartite graphs (meshes, trees, hypercubes…). However, it remains open questions in a lot of graph classes, notably in trees. A very useful notion for the computation of strategies in pursuit-evasion games is the notion of monotonicity. We define a monotone variant of the Hunters and Rabbit game, for which we prove that the minimum number mh(G) of hunters differs by at most one from the pathwidth. This has important consequences, such as the fact that computing mh(G) is NP-hard. We also characterize mh(G) for several graph classes, such as split graphs, interval graphs, trees, and cographs. For these classes, we study the difference between mh and h and, in particular, we show that it is arbitrarily large in trees.

Résumé: Les décompositions de graphes sont un outil permettant de représenter un graphe en plusieurs parties, appelées sacs, et structurées comme un arbre ou un chemin suivant si ce sont des décompositions arborescentes ou linéaires. Ces décompositions permettent de résoudre certains problèmes NP-difficiles en temps linéaire, si la taille maximum des sacs (i.e. la « largeur/width ») est bornée. Cela a motivé les travaux de ces 30 dernières années sur la largeur arborescente d’un graphe G (la plus petite largeur des décompositions arborescente de G). Cependant, il reste encore beaucoup de questions ouvertes comme la complexité du calcul de la largeur arborescente des graphes planaires. Pour pouvoir répondre à cette question, il peut être intéressant d’étudier une autre mesure des décompositions, la longueur. Cette mesure correspond au diamètre maximum des sacs d’une décomposition, et il a été prouvé qu’il existe une relation entre la longueur arborescente et la largeur arborescente dans les graphes planaires.

Nous nous intéressons donc dans le chapitre 2 à la longueur arborescente de classes de graphes planaires simples, comme les graphes série-parallèles. Nous explicitons une liste infinie de sous-graphes isométriques interdits pour les graphes série-parallèles de longueur arborescente 2. Grâce à cette liste, il est alors possible en temps polynomial de tester si un graphe série-parallèle a une longueur arborescente au plus 2 et, dans le cas d’une réponse positive, de calculer une décomposition arborescente optimale.

Nous nous intéressons aussi au cas de la longueur linéaire dans le chapitre 3. Nous nous focalisons sur les classes des arbres et des cycles pour lesquelles nous caractérisons la longueur linéaire. Nous nous intéressons aussi à la longueur linéaire des graphes planaires extérieurs et concevons un algorithme d’approximation de rapport additif 1.

Finalement, dans le chapitre 4, nous nous intéressons à une variante algorithmique des décompositions linéaires des graphes, par le biais d’un jeu de poursuite-évasion, le jeu des Chasseurs et du Lapin. Dans ce jeu, un groupe de chasseurs traque un lapin invisible qui est forcé de bouger à chaque étape sur une position voisine. Nous nous intéressons au nombre minimum h(G) de chasseurs qui peuvent attraper le lapin quoi qu’il fasse sur un graphe G. Ce jeu a notamment été étudié dans le cas des graphes bipartis (grilles, arbres, hypercubes…) mais reste ouvert dans beaucoup de classes de graphes et notamment dans les arbres. Une notion très utile pour le calcul de stratégie dans les jeux de poursuite-évasion est la notion de monotonie. Nous définissons une variante monotone du jeu des chasseurs et du lapin, nous permettant entre autres, de prouver que, dans cette variante, le nombre minimum mh(G) de chasseurs diffère d’au plus un de la largeur linéaire du graphe G. Ce résultat a d’importantes conséquences, comme le fait que le calcul de mh(G) est NP-difficile. Nous caractérisons aussi mh(G) pour plusieurs classes de graphes, comme les graphes scindés, les graphes d’intervalles, les arbres et les cographes. Nous étudions la différence entre mh et h dans ces classes de graphes et, en particulier, nous montrons qu’il peut exister une différence arbitrairement grande entre mh et h dans les arbres.

• Emmanuel Chaput (reviewer), Professor, INP Toulouse, France.
• Enrico Natalizio (reviewer), Professor, LORIA, Université de Lorraine, Nancy, France.
• Hervé Rivano, Professor, INSA, Lyon, France.
• Yann Busnel, Professor, IMT Nord Europe, Lille, France.
• David Coudert, Directeur de Recherche, Centre Inria d’Université Côte d’Azur, France.
• Christelle Caillouet, Assistant Professor, Université Côte d’Azur, France.

Abstract: Unmanned Aerial Vehicles (UAVs) have gained tremendous attention lately. These autonomous flying devices have several advantages in terms of deployment cost and processing capabilities, making them a promising solution for a wide range of military and commercial applications. In this thesis, we have studied two applications: creating a flying network to connect mobile sensors to a base station and wirelessly charging fixed ground sensors.

In the first application, we want to communicate with mobile sensors in a disaster scenario without pre-existing communication infrastructure. Our goal in this application is to determine the optimal flight plans for the UAVs. The UAVs must maintain a connected path between the base station and the sensors to allow the sensors to send critical information when necessary. We optimise the UAVs’ total distance travelled and energy consumed.

The second application has a set of fixed ground sensors we need to recharge. Equipping the UAVs and sensors with power harvesting technology allows us to recharge these sensors wirelessly. We proposed a 2 step solution where first, a linear program finds where each drone needs to go and how long it should stay there to ensure the sensors get enough power. Then, greedy scheduling algorithms determine the order in which UAVs visit these spots, ensuring they do not get in each other’s way or reduce the charging efficiency. We minimise the total time to charge all sensors in both steps.

Résumé: Les véhicules aériens sans pilote (UAV) ont suscité une attention considérable récemment. Ces appareils volants autonomes présentent plusieurs avantages en termes de coûts de déploiement et de capacités de traitement, ce qui en fait une solution prometteuse pour un large éventail d’applications militaires et commerciales. Dans cette thèse, nous avons étudié deux applications : la création d’un réseau aérien pour connecter des capteurs mobiles à une station de base et la recharge sans fil de capteurs fixes au sol.

Dans la première application, nous voulons communiquer avec des capteurs mobiles dans un scénario de catastrophe sans infrastructure de communication préexistante. Notre objectif dans cette application est de déterminer les meilleurs plans de vol pour les UAVs. Les UAVs doivent maintenir un chemin connecté entre la station de base et les capteurs pour permettre aux capteurs d’envoyer des informations critiques si nécessaire. Nous optimisons la distance totale parcourue par les UAVs et l’énergie consommée.

La deuxième application concerne un ensemble de capteurs au sol fixes que nous devons recharger. La technologie de récupération d’énergie, basée sur l’échange de signaux radio-fréquence, permettant de recharger les batteries des capteurs sans fil. Nous avons proposé une solution en 2 étapes où d’abord, un programme linéaire détermine où chaque drone doit aller et combien de temps il doit y rester pour s’assurer que les capteurs reçoivent suffisamment d’énergie. Ensuite, des algorithmes gloutons d’ordonnancement déterminent l’ordre dans lequel les UAVs visitent ces points, en veillant à ce qu’ils ne se gênent pas mutuellement ou ne réduisent pas l’efficacité de la charge. Nous minimisons le temps total nécessaire pour recharger tous les capteurs dans les deux étapes.