Category: PhD & HDR

• 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.

• Emanuele NATALE (Thesis director), Chargé de Recherche, CNRS, COATI, France.
• Vincent GRIPON (Reviewer), IMT-Atlantique, France.
• Marc LELARGE (Reviewer), Directeur de recherche, Inria, Paris, France.
• Konstantin AVRACHENKOV, Directeur de recherche, Inria, Sophia Antipolis, France.
• Pierluigi CRESCENZI, Professeur, Gran Sasso Science Institute, L’Aquila, Italy.
• Frédéric GIROIRE, Directeur de recherche, CNRS. COATI, Sophia Antipolis, France.
• Laurent VIENNOT (Invited), Directeur de recherche, Inria, Paris, France.

Abstract: The Strong Lottery Ticket Hypothesis (SLTH) states that neural networks contain, at random initialisation, sub-networks that perform well without any training. The random network needs, however, to be over-parameterized: to have more parameters than it would otherwise need.

The SLTH was first proved for fully-connected networks and assumed polynomial over-parameterization. Soon after, this was improved to only require a logarithmic overhead, which is essentially optimal. This strong result leveraged a theorem on the Subset Sum Problem (SSP). It considers a randomised version of the SSP in which one seeks to approximate a target value by summing subsets of a given random sample. The theorem asserts that ensuring the existence of a solution with high probability only requires a logarithmic sample size relative to the precision of the approximations. We present a simpler, more direct proof for this result.

Then, leveraging the theorem on the SSP, we extend the SLTH to Convolutional Neural Networks (CNNs): we show that random CNNs contain sparse sub-CNNs that do not require training to achieve good performance. We also obtained the result assuming a logarithmic over-parameterization.

Even though the overhead imposed by the SLTH could be offset by the sparsity of the sub-networks obtained, exploiting sparsity in practice is very difficult if it is not structured. Extending the results on the SLTH to produce structured sub-networks would require a multidimensional version of the theorem on SSP. We prove such a version and use it to show that the SLTH still holds for CNNs if we require the sub-networks to be structured.

Finally, we propose an application of the ideas in this thesis to the design of circuits: We harness the inherent randomness in the specs of integrated electronic components to obtain highly accurate programmable components from low-precision static ones.

Résumé: La Strong Lottery Ticket Hypothesis (SLTH) stipule que les réseaux de neurones contiennent, lors de l’initialisation aléatoire, des sous-réseaux qui fonctionnent bien sans aucun entraînement. Le réseau aléatoire doit cependant être sur-paramétré : avoir plus de paramètres qu’il n’en aurait besoin.

La SLTH a d’abord été prouvée pour les réseaux entièrement connectés et suppose une sur-paramétrisation polynomiale. Puis, cela a été amélioré pour ne nécessiter qu’un surplus logarithmique, ce qui est essentiellement optimal. Ce fort résultat a tiré parti d’un beau théorème sur le Subset Sum Problem (SSP). Il considère une version aléatoire du SSP dans laquelle on cherche à approximer une valeur cible en sommant des sous-ensembles d’un échantillon aléatoire donné. Le théorème affirme que garantir l’existence d’une solution avec une haute probabilité ne nécessite qu’une taille d’échantillon logarithmique par rapport à la précision des approximations. Nous présentons une preuve plus simple et plus directe pour ce résultat.

Ensuite, en tirant parti du théorème sur le SSP, nous étendons le SLTH aux Convolutional Neural Networks (CNNs) : nous montrons que les CNN aléatoires contiennent des sous-CNN clairsemés qui n’ont pas besoin d’entraînement pour obtenir de bonnes performances. Nous avons également obtenu le résultat en supposant une sur-paramétrisation logarithmique.

Bien que le surplus imposé par le SLTH puisse être compensé par la rareté des sous-réseaux obtenus, exploiter la rareté en pratique est très difficile si elle n’est pas structurée. Étendre les résultats sur le SLTH pour produire des sous-réseaux structurés nécessiterait une version multidimensionnelle du théorème sur le SSP. Nous prouvons la véracité d’une telle version et nous l’utilisons pour montrer que le SLTH est toujours valable pour les CNN si nous exigeons que les sous-réseaux soient structurés.

Enfin, nous proposons une application des idées de cette thèse à la conception de circuits : nous exploitons l’aléatoire inhérent aux spécifications des composants électroniques intégrés pour obtenir des composants programmables hautement précis à partir de composants statiques de faible précision.

• Robert Elsässer (referee), Full Professor, University of Salzburg, Austria
• Pierre Fraigniaud (referee), Directeur de Recherche, CNRS, France
• Frederik Mallmann-Trenn (referee), Assistant Professor, King’s College London, United Kingdom
• Emanuele Natale (supervisor), Chargé de Recherche, CNRS, France
• Nicolas Nisse (supervisor), Chargé de Recherche, Inria, France
• Alain Jean-Marie, Directeur de Recherche, Inria, France

Abstract: In recent years there has been a surge of interest on behalf of the algorithmic community in applying its theoretical tools to the understanding of complex systems, in particular biological ones, such as insect colonies, flocks of birds, and networks of neurons. We contribute to the investigation of such systems in three different directions. First, we analyze computational dynamics for stochastic coordination tasks in multi-agent systems: in particular, we focus on the consensus problem in environments where communication is affected by some form of noise. In this setting, we analyze two known opinion dynamics, the \textsc{Undecided-State} and the \textsc{3-Majority} dynamics, and prove that they exhibit a phase-transition at different noise thresholds. Below the threshold, the two dynamics quickly reach an almost-consensus metastable phase; above, no form of consensus is possible. Second, we study Lévy walks, i.e.,\ special random walks known to model many movement patterns found in nature, characterized by a step-length density distribution proportional to a power-law. We analyze their parallel hitting time and show how to use them to design an almost optimal algorithm for the ANTS problem, a distributed search problem on $ \mathbb{Z}^2 $ which captures some aspects of animal foraging theory. Third, we consider the Assembly Calculus, a recently proposed distributed computational model of the brain which consists of stylized spiking neurons and synapses, and we test experimentally its capabilities, largely unexplored. In particular, we implement known heuristics for the Blocks World planning task; we empirically prove that reasonably large and complex programs in the Assembly Calculus run correctly and reliably.

Résumé:
Récemment, la communauté algorithmique a manifesté un intérêt croissant pour l’utilisation de ses outils théoriques à la compréhension des systèmes complexes, notamment biologiques, tels que les colonies d’insectes, les volées d’oiseaux et les réseaux de neurones. Nous contribuons à l’étude de ces systèmes dans trois directions différentes. Premièrement, nous analysons des dynamiques computationnelles pour les tâches de coordination stochastique dans les systèmes multi-agents. En particulier, nous nous focalisons sur le problème du consensus dans des environnements où la communication est bruyante : nous analysons deux dynamiques d’opinion, les dynamiques \textsc{Undecided-State} et \textsc{3-Majority}, et nous prouvons qu’elles présentent une transition de phase à des seuils de bruit différents. En dessous du seuil, ces dynamiques atteignent rapidement une phase métastable de quasi-consensus ; au-dessus, aucune forme de consensus n’est possible. Deuxièmement, nous étudions les Lévy walks, des marches aléatoires qui modélisent des schémas de mouvement trouvés dans la nature, dont la distribution de la longueur de pas suit une loi de puissance. Nous analysons leur temps d’arrêt (hitting time) parallèle et les utilisons pour concevoir un algorithme optimal pour l’ANTS problem, un problème de recherche distribuée sur $\mathbb{Z}^2$ qui capture certains aspects de la théorie du butinage. Troisièmement, nous considérons l’Assembly Calculus, un modèle distribué du cerveau récemment proposé, qui consiste en des neurones et des synapses stylisés, et nous testons expérimentalement ses capacités, largement inexplorées, en mettant en œuvre des heuristiques connues pour la tâche de planification du monde des blocs. Nous montrons empiriquement que des programmes grands et complexes dans ce modèle s’exécutent correctement et de manière fiable.

• Andrea Clementi, Full Professor, University of Rome Tor Vergata
• Romuald Elie, Research Scientist, DeepMind, Google
• Frédéric Giroire (supervisor), Directeur de recherche, CNRS
• Marc Lelarge (referee), Directeur de recherche, Inria Paris
• Pietro Michiardi (referee), Full Professor, EURECOM
• Giovanni Neglia, Directeur de recherche, Inria Sophia Antipolis

Abstract: The field of Artificial Intelligence (AI) has brought a broad impact on today’s society, leading to a gripping interaction between several scientific disciplines. In this respect, there has been a strong twofold interest across the literature. On the one hand, a growing trend in telecommunication networks consists in revisiting classic optimization problems using machine learning techniques in order to exploit their potential benefits. We focus on some challenges brought by the detection of anomalies in networks, and the allocation of resources within software-defined networking (SDN) and network function virtualization (NFV). On the other hand, a substantial effort has been devoted towards the theoretical understanding of the collective behavior of networks. We focus on some challenges brought by the study of majority dynamics within multi-agent systems, and the compression of artificial neural networks with the aim at increasing their efficiency. In this study, we contextualize the above focal points in the framework of investigating some foundations of networks; viewed through the lens of telecommunications networks and neural networks. We first focus our attention on developing graph similarity measures for network anomaly detection. Next, we study deterministic and stochastic majority dynamics in multi-agent systems. Then, we discuss the random subset sum problem in the context of neural network compression. Finally, we walk through some other miscellaneous problems.

Résumé: Le domaine de l’Intelligence Artificielle (IA) a un large impact sur la société d’aujourd’hui, ayant conduit notamment à une interaction passionnante entre plusieurs disciplines scientifiques. À cet égard, un double intérêt émerge dans la littérature. D’une part, une tendance croissante dans les réseaux de télécommunication consiste à revisiter les problèmes d’optimisation classiques en utilisant des techniques d’apprentissage automatique afin d’exploiter leurs avantages potentiels. Nous nous focaliserons sur certains défis posés par la détection d’anomalies dans les réseaux ainsi que l’allocation des ressources dans le cadre des réseaux logiciels (SDN) et de la virtualisation des fonctions réseau (NFV). D’autre part, un effort substantiel a été consacré dans le but d’apporter une compréhension théorique du comportement collectif des réseaux. Nous nous focaliserons sur certains défis posés par l’étude de la dynamique majoritaire au sein des systèmes multi-agents ainsi qu’à la compression des réseaux de neurones artificiels dans le but d’augmenter leur efficacité. Dans cette étude, nous contextualisons les points focaux ci-dessus dans le cadre de l’étude de certains fondements de réseaux; vus sous l’angle des réseaux de télécommunications et des réseaux neuronaux. Nous nous concentrons d’abord sur le développement de mesures de similarité de graphes pour la détection d’anomalies dans les réseaux. Ensuite, nous étudions la dynamique majoritaire déterministe et stochastique dans les systèmes multi-agents. Ensuite, nous discutons du problème de la somme de sous-ensembles aléatoires dans le contexte de la compression des réseaux neuronaux. Enfin, nous passons en revue quelques problèmes généraux divers.

• Éric Sopena (referee), Professor, LaBRI, Université de Bordeaux
• Mariusz Woźniak (referee), Professor, AGH University of Science and Technology
• Julien Bensmail (supervisor), Associate professor, I3S, Université Côte d’Azur
• Nicolas Nisse (supervisor), Inria Research Officer, Inria Sophia Antipolis
• Théo Pierron, Associate professor, LIRIS, Université Claude Bernard Lyon 1
• Olivier Togni, Professor, LIB, Université de Bourgogne

Abstract: In this thesis, we consider two families of computational problems defined on graphs: proper edge-labellings and combinatorial games. We attack these problems in a similar (and classical) way: we show that they are computationally hard, and then find efficient algorithms for instances with specific structure.

First we focus on problems related to proper labellings of graphs. For some natural number k, a k-labelling is a weight function on the edges of a graph G, assigning weights, called labels in this context, from {1, . . . , k}. A k-labelling induces a vertex-colouring of G, where each vertex receives as colour the sum of the labels of its incident edges. A k-labelling is proper if the induced vertex-colouring is proper, i.e., such that any two adjacent vertices of G are assigned different colours. According to the so-called 1-2-3 Conjecture, any connected graph of order at least 3 should admit a proper 3-labelling. Weconsider three variations of this conjecture. We look into equitable proper k-labellings, for which the assigned labels appear an equal number of times. We then focus on proper labellings that also minimise the sum of labels being used, and finally, proper 3-labellings that also minimise the number of times that the label 3 is assigned.
The choice to study these variations is natural. Indeed, an equitable version of the 1-2-3 Conjecture claims that almost every graph G should admit an equitable proper 3-labelling. Also, the sum of labels of such a labelling would be at most 2|E(G)| and it would assign label 3 to at most one third of the edges of G. We prove that the introduced optimisation problems are NP-hard. Furthermore, through structural and algorithmical results, we propose new conjectures for the upper bounds of the parameters that we study, which we verify for specific graph classes (e.g. complete, bipartite, regular, 3-chromatic, etc.). Interestingly, our work gives further evidence that stronger variations of the 1-2-3 Conjecture could hold. We close our study of proper labellings by considering the problem of finding a largest induced subgraph of a given graph that admits a proper 1-labelling. This problem is proven to be computationally hard and not approximable within a ratio of O(|V(G)|^(1−c)) for every natural number c. Nevertheless, we provide efficient parameterised algorithms.

In the second part of the thesis, we introduce and study the Maker-Breaker largest connected subgraph game. This game is played by two players, Alice and Bob, on a shared, initially uncoloured graph G. The two players take turns colouring the vertices of G, each one with their own colour, until there remains no uncoloured vertex. Alice is the winner of the game if, by the end, the largest connected subgraph of G induced by her colour is of order greater than k, where the natural number k is also given at the start of the game. Otherwise Bob wins the game. We also consider a Maker-Maker version of the same game, played in the same way, but in which the winner is the player whose colour induces the largest connected subgraph of G by the end of the game.
We first prove that deciding the outcome of both of these games is PSPACE-hard, and then proceed by providing efficient algorithms when the games are played on particular graph classes (e.g. paths, cycles, cographs, (q, q − 4)-graphs, etc.). Comparing the behaviour of these games, one of the main differences we observe is that Bob can never win the Maker-Maker version (if Alice plays optimally). Nevertheless, if Alice can win the Maker-Breaker version when playing on G for a value of k equal to half the order of G (the best outcome she can hope for), then she can build a connected subgraph of the same order for the Maker-Maker version; such graphs are called A-perfect. We then study regular graphs that are A-perfect and prove that any 3-regular A-perfect graph has order at most 16. We finish by providing sufficient conditions for a graph to be A-perfect.

Résumé: Cette thèse considère deux familles de problèmes définis sur des graphes : les étiquetages d’arêtes propres et les jeux combinatoires. Nous traitons ces problèmes de façon similaire (et classique) : nous montrons que les problèmes considérés sont difficiles à résoudre, puis nous trouvons des algorithmes efficaces sur des instances restreintes.

Nous nous concentrons d’abord sur des problèmes concernant des étiquetages propres de graphes. Pour un entier k fixé, un k-étiquetage d’un graphe G est une fonction associant à chaque arête de G une étiquette parmi {1, . . . , k}. Un k-étiquetage induit une coloration des sommets de G, où chaque sommet reçoit comme couleur la somme des étiquettes de ses arêtes incidentes. Un k-étiquetage est propre si, dans la coloration induite, deux sommets adjacents de G reçoivent des couleurs différentes. D’après la Conjecture 1-2-3, tout graphe connexe d’ordre au moins 3 admet un 3-étiquetage propre. Nous considérons trois variantes de cette conjecture. Nous étudions les k-étiquetages propres équilibrés, pour lesquels les étiquettes assignées apparaissent dans les mêmes proportions.
La deuxième variante concerne les étiquetages propres qui minimisent la somme des étiquettes utilisées. Enfin, nous nous intéressons aux 3-étiquetages propres qui minimisent le nombre de fois où l’étiquette 3 est attribuée. Le choix d’étudier ces variantes est naturel. En effet, une version équilibrée de la Conjecture 1-2-3 est que presque tous les graphes G admettent un 3-étiquetage propre équilibré. En outre, la somme des étiquettes d’un tel étiquetage est au plus égale à 2|E(G)| et associe l’étiquette 3 à au plus un tiers des arêtes de G. Nous prouvons que les problèmes d’optimisation introduits sont NP-difficiles. Grâce à des résultats structurels et algorithmiques, nous sommes amenés à proposer de nouvelles conjectures pour ces problèmes, que nous vérifions sur quelques classes de graphes (complets, bipartis, réguliers, 3-chromatiques, etc.).
Notre travail renforce l’idée que des variantes plus fortes de la Conjecture 1-2-3 pourraient être vraies. Nous terminons en considérant le problème consistant à trouver un plus grand sous-graphe induit d’un graphe donné qui admet un 1-étiquetage propre. Il est prouvé que ce problème est difficile à résoudre et qu’il n’est pas approximable à un facteur O(|V (G)|^(1−c)) près pour tout entier c. Néanmoins, nous fournissons des algorithmes paramétrés efficaces.

La deuxième partie de la thèse introduit le jeu du plus grand sous-graphe connexe Maker-Breaker, joué par deux joueurs, Alice et Bob, sur un graphe G, initialement non coloré. Les joueurs colorent à tour de rôle les sommets de G, chacun avec sa couleur, jusqu’à ce que tous les sommets soient colorés. Alice est la gagnante si, à la fin, le plus grand sous-graphe connexe de G induit par sa couleur est d’ordre au moins k, un entier fixé. Sinon, Bob gagne le jeu. Nous considérons aussi une version Maker-Maker du même jeu, dans laquelle le gagnant est le joueur dont la couleur induit le plus grand sous-graphe connexe de G à la fin du jeu. Nous prouvons que décider de l’issue de ces deux jeux est PSPACE-difficile et nous fournissons des algorithmes efficaces pour le cas où le jeu se déroule dans certaines familles de graphes (chemins, cycles, cographes, (q,q−4)-graphes, etc.).
En comparant ces deux jeux, la principale différence que nous observons est que Bob ne peut jamais gagner la version Maker-Maker (si Alice joue de manière optimale). Pour une valeur de k égale à la moitié de l’ordre de G, remarquons que si Alice peut gagner la version Maker-Breaker alors elle peut aussi construire un sous-graphe connexe du même ordre dans la version Maker-Maker ; de tels graphes sont nommés A-parfaits. Nous étudions les graphes réguliers qui sont A-parfaits et prouvons que tout graphe 3-régulier A-parfait a au plus 16 sommets. Nous terminons en fournissant des conditions suffisantes pour qu’un graphe soit A-parfait.

• Etienne Birmelé (referee), Professor, IRMA, Strasbourg, France
• Guillaume Fertin (referee), Professor, LS2N, Nantes, France
• Christophe Paul, Senior Researcher (DR CNRS), LIRMM, Montpellier, France
• Blerina Sinaimeri, Senior researcher (CR Inria), Inria Lyon, France
• Stéphane Vialette, Senior researcher (DR CNRS), LIGM, Grenoble, France
• Frédéric Havet (supervisor), Senior researcher (DR CNRS), Université Côte d’Azur, CNRS, I3S, Inria, Sophia Antipolis, France
• Dorian Mazauric (supervisor), Senior Researcher (CR Inria), Inria, Sophia Antipolis, France

Abstract: To explain the biological function of a molecular assembly (MA), one has to know its structural description. It may be ascribed to two levels of resolution: low resolution (i.e. molecular interactions) and high resolution (i.e. relative position and orientation of each molecular subunit, called conformation). Our thesis aims to address the two problems from graph aspects.
The first part focuses on low resolution problem. Assume that the composition (complexes) of a MA is known, we want to determine all interactions of subunits in the MA which satisfies some property. It can be modeled as a graph problem by representing a subunit as a vertex, then a subunit-interaction is an edge, and a complex is an induced subgraph. In our work, we use the fact that a subunit has a bounded number of interactions. It leads to overlaying graph with bounded maximum degree. For a graph family F and a fixed integer k, given a hypergraph H = (V (H), E(H)) (whose edges are subsets of vertices) and an integer s,
MAX (∆ ≤ k)-F-OVERLAY consists in deciding whether there exists a graph with degree at most k such that there are at least s hyperedges in which the subgraph induced by each hyperedge (complex) contains an element of F. When s = |E(H)|, it is called (∆ ≤ k)-F-OVERLAY . We present complexity dichotomy results (P vs. NP-complete) for MAX (∆ ≤ k)-F-OVERLAY and (∆ ≤ k)-F-OVERLAY depending on pairs (F, k).
The second part presents our works motivated by high resolution problem. Assume that we are given a graph representing the interactions of subunits, a finite set of conformations for each subunit and a weight function assessing the quality of the contact between two subunits positioned in the assembly. Discrete Optimization of Multiple INteracting Objects (DOMINO ) aims to find conformations for the subunits maximizing a global utility function. We propose a new approach based on this problem in which the weight function is relaxed, CONFLICT COLORING . We present studies from both theoretical and experimental points of view. Regarding the theory, we provide a complexity dichotomy result and also algorithmic methods (approximation and fixed paramater tracktability). Regarding the experiments, we build instances of CONFLICT COLORING associated
with Voronoi diagrams in the plane. The obtained statistics provide information on the dependencies of the existences of a solution, to parameters used in our experimental setup.

Résumé: Pour comprendre les fonctions biologiques d’un assemblage moléculaire (AM), il est utile d’en avoir une représentation structurale. Celle-ci peut avoir deux niveaux de résolution : basse résolution (i.e. interactions moléculaires) et haute résolution (i.e. position relative et orientation de chaque sous-unité, appelée conformation). Cette thèse s’intéresse à trouver de telles représentations à l’aide de graphes.
Dans la première partie, nous cherchons des représentations basse résolution. Etant donné la composition des complexes d’un AM, notre but est de déterminer les interactions entre ses différentes sous-unités. Nous modélisons l’AM à l’aide d’un graphe : les sous-unités sont les sommets, les interactions entre elles sont les arêtes et un complexe est un sous-graphe induit. Utilisant le fait qu’une sous-unité n’a qu’un nombre limité d’interactions, nous arrivons au problème suivant. Pour un graphe F et un entier k fixés, étant donné un hypergraphe H et un entier s, MAX (∆ ≤ k)-F-OVERLAY consiste à décider s’il existe un graphe de degré au plus k tel qu’au moins s hyperarêtes de H induisent un sous-graphe contenant F (en tant que sous-graphe). La restriction au cas s = |E(H)| est appelée (∆ ≤ k)-F-OVERLAY . Nous donnons une dichotomie de complexité (P vs. NP-complet) pour MAX (∆ ≤ k)-F-OVERLAY et (∆ ≤ k)-F-OVERLAY en fonction du couple (F, k).
Dans la seconde partie, nous nous attaquons à la haute résolution. Nous sont donnés un graphe représentant les interactions entre sous-unités, un ensemble de conformations possibles pour chaque sous-unité et une fonction de poids représentant la qualité de contact entre les conformations de deux sous-unités interagissant dans l’assemblage. Le problème Discrete Optimization of Multiple INteracting Objects (DOMINO) consiste alors à trouver les conformations pour les sous-unités qui maximise une fonction d’utilité globale. Nous proposons une nouvelle approche à ce problème en relâchant la fonction de poids, ce qui mène au problème de graphe CONFLICT COLORING . Nous donnons tout d’abord des résultats de complexité et des algorithmes (d’approximation et à paramètre fixé). Nous menons ensuite des expérimentations sur des instances de CONFLICT COLORING associées à des diagrammes de Voronoi dans le plan. Les statistiques obtenues nous informent sur comment les paramètres de notre montage expérimental influe sur l’existence d’une solution.