Communications

My main concern is to design efficient algorithms for solving problems arising in telecommunication networks. Since most of these problems are NP-hard in general, I try to use structural properties of considered networks to derive polynomial-time exact or approximation algorithms in particular graph classes. One powerful tool I use to determine and to understand the algorithmic interest of graph structures is pursuit-evasion games. In these games, a team of searchers/pursuers/cops aims at capturing a fugitive/evader/robber moving in a graph. Below I briefly describe some works that I have presented in national/international seminars and conferences. (I have been there)

Here are brief overviews on Pursuit-evasion Games and Applications

Combinatorial (turn-by-turn two-player) Games in Graphs (e.g., Cops and Robber)

Given a graph G, the seminal cops and robber game involves two players [Nowakowski and Winkler, Quilliot, 1983]. Player 1 first places its cops on vertices of G, then Player 2 places its Robber on one node. Then, turn by turn, Player 1 moves its cops to neighboring nodes and then Player 2 does as well with its robber (cops and robber may stay idle). This is a full information game in the sense that cops and robber are always visible to each other. The Cops win if eventually one cop occupies the same node as the robber, and the Robber wins otherwise. The cop-number of a graph G is the smallest number of cops that ensures that the robber will eventually be captured in G. In particular, Meyniel conjectured that O(n1/2) cops are sufficient to capture a robber in any n-node graph (1985).
While still open in general graphs, this conjecture has been proved in many graph classes (bounded genus, graph exclusing fixed minor, etc.). I continued this study of graph properties through various variants of this game.
• Eternal domination in grid-like graphs based on this paper.
• Seminar of Northwestern Polytechnical University, Xi'an, China, Sept. 9th, 2019
• Metric Dimension in Oriented Graphs based on this paper.
• This work is not directly related to games but it deals with metric dimension as for previously mentioned game but in oriented graphs. Precisely, we study the following question. Given a class of graphs, how to orient the edges of these graphs in order to maximize the directed metric dimension of the resulting orientation? We partially answer this question in the class of graphs with bounded maximum degree, in grids and in tori.
• Seminar project COATI, Sophia Antipolis, June 25th, 2019
• AlgoTel'19, Saint Laurent de la Cabrerisse, June 6th, 2019
• Localization GameS in graphs based on this paper and this one.
• This time, we aim at locating a moving ``target" by probing k vertices at every steps. Probing a set of vertices teaches us the distance between the probed vertices and the target (related to Identifying codes and metric dimension of graphs). Either, the last probes allow us to precisely determine the location of the target, or the target may move on a neighboring node and we may probe again k vertices (and so on). We look for the minimum k allowing to eventually locate the target (whatever the target does) in several graph classes.
• Spy Games via LP based on Study of a combinatorial game in graphs through Linear Programming.
• Deciding the minimum number of guards required to control a spy in trees seems to be a difficult problem. Surprinsingly, we design a polynomial-time algorithm using Linear Programming. Designing a combinatorial algorithm for such a problem is still open. Similarly, the same problem in grids is unsolved.
• ISAAC'17, Phuket, Thailand, December 11th, 2017
• Spy Games based on Spy-Game on graphs.
• We introduce a new Game: where one Spy and some guards move from vertices to vertices, along the edges of a graph. They may occupy same vertices, but the Spy is faster than the Guards. The goal of Guards is to constantly keep the spy under control, i.e., at distance at most d (some fixed parameter) from at least one of them.
• Workshop Moving and Computing (MAC), UPMC, Paris, September 26th, 2016
• Groupe de travail de l'équipe CRO, LIF, Marseille, July 18th, 2016
• Workshop on Search Games: Theory and Algorithms, Leiden, Netherlands, June 28th, 2016.
• FUN'16, La Maddalena, Maddalena Islands, Italy, June 8th, 2016.
• Fractional Combinatorial Games, preliminary results.
• We propose a new framework to study two-player turn-by-turn games. We see them as convex games and propose a fractional relaxation of them.
• GRASTA'14, Cargèse, Corsica, France, March 31th, 2014.
• EURO'13, Roma, Italia, July 4th, 2013.
• Connected Surveillance game, based on Connected Surveillance game.
• We investigate the connected and Online variants of Surveillance game. In the online case, the observer discover the graphs as he marks the nodes. We show that, unfortunately, the best online strategy is the basic one, that marks neighbors of the surfer's position at each step. For the connected variant, we show that the connected surveillance number is at most (n.sn(G))1/2 in any n-node graph G with surveillance number sn(G). On the other hand, we exhibit a family of graphs G with connected surveillance number equal to sn(G)+2. The gap is still huge.
• Sirocco'13, Ischia, Italia, July 1st, 2013.
• Cops and Robber and algorithmic applications, based on k-Chordal Graphs: from Cops and Robber to Compact Routing via Treewidth.
• This work could as well be in the Graph decompositions or in the Routing part. More precisely, this work makes a link between most of my research interests. In this work, we prove the Meyniel conjecture in k-chordal graphs (graphs with no induced cycles greater than k). This leads us to a greedy algorihtm to compute a particular tree-decomposition of graphs that have a nice structure, in particular, in k-chordal graphs. Finally, we design an efficient compact routing scheme (see also Distributed Routing part) in graphs that admit such a decomposition.
• Seminar, JAIST, Kanazawa, Japan, August 5th, 2014
• SophiaTech networks seminar, EURECOM, Sophia Antipolis, September 26th, 2013
• IMSA seminar (longer talk), Univ. Adolfo Ibanez, Santiago, Chile, August 10th, 2012
• Plenary meeting EULER, Ghent, Belgium, June 6th, 2012
• AlgoTel'12, La Grande Motte, May 31st, 2012
• Surveillance game, based on To satisfy Impatient Web surfers is Hard.
• We define a cops and robber like game to model the prefetching problem. In the surveillance game, a surfer moves from one node to an adjacent one, starting from a marked node. Before each move of the surfer, an observer can mark a bounded amount of nodes in the graph. The observer wins if the surfer never reaches an unmarked node. We show that bounding the number of marks of the observer is hard even in split graphs (not FPT in chordal graphs, PSPACE-complete in DAGs) and we design polynomial-time algorithms in trees and interval graphs. The cost of connectivity (when marked nodes must induce a connected subgraph) is left open.
• 5th Workshop on GRAph Searching, Theory and Applications (GRASTA) (video), Banff, Canada, October 9th, 2012
• AlgoTel'12, La Grande Motte, May 31st, 2012
• Groupe de travail de l'équipe CRO, LIF, Marseille, February 20th, 2012
• 13mes Journées "Graphes et Algorithmes" (short talk), Lyon, November 18th, 2011
• Séminaire de l'équipe-project MASCOTTE, INRIA Sophia Antipolis, October 25th 2011
• Cop-win graphs in some variants, based on Cop and robber games when the robber can hide and ride.
• We characterize the graphs where one cop can capture a fast robber. We also give an (almost complete) characterization of graphs where one cop can capture a robber that shows itself only every k steps. This generalizes the structural characterization of graphs with cop-number one, a.k.a., dismantable graphs. Surprisingly (?), the case when the cop can capture the robber at some distance seems to be harder to be delt with.
• 4th Workshop on GRAph Searching, Theory and Applications (GRASTA), Dagstuhl, Germany, February 17th, 2011
• EURO 2010, Lisbon, Portugal, July 14th, 2010
• FCC 2010 (short talk), Orsay, France, June 28th, 2010
• Seminar team ParGO, Univ. federal do Ceara, Fortaleza, Brazil, April 9th, 2010
• Séminaire de l'équipe-project MASCOTTE, INRIA Sophia Antipolis, January 12th 2010
• Fast Robber, based on Pursuing a fast robber on a graph.
• We define the cops and robber game with fast cops and robber. Here, a cop/robber can move up to some fixed distance to its current position at each turn. We show that, when the robber is faster that the cops, then the number of cops required to capture a robber is unbounded in planar graphs (while, in planar graphs, 3 cops are always sufficient to capture a robber with speed 1, i.e., in the classical game [Aigner and Fromme 86]). We also show that computing the cop-number of a graph is NP-hard.
How many cops with speed 1 are necessary and sufficient to capture a robber with speed 2 in a nxn grid? (we proved it is at least Omega((log n)1/2); an easy (?) upper bound is n/5)
• Groupe de travail de l'équipe CRO, LIF, Marseille, December 15th 2008
• 10mes Journées "Graphes et Algorithmes", INRIA, Sophia Antipolis, November 6th 2008
• Seminar project Anillo en Redes (DIM), Santiago, Chile, August 22nd, 2008
• AlgoTel'08 (short french talk), Saint Malo, May 14th, 2008

Graph Searching and Graph Decompositions

In graph searching, a team of searchers aims at capturing a arbitrary fast omniscient fugitive in a graph. The searchers can be placed at or removed from the nodes of a graph (they can jump). The fugitive can move along paths of the graph as long as it does not meet any searcher. The fugitive is captured when a searcher lands at the same node and the fugitive cannot flee. If the fugitive is invisible, the smallest number of searchers required to capture it in a graph G equals the pathwith of G plus 1. If the fugitive is visible, it is its treewidth plus 1. In some (equivalent) variants the searchers also can slide along edges.
I study graph searching as it provides an algorithmic interpretation of graph decompositions. I also study this problem in a distributed setting as it provides a natural way to understand how mobile agents have to colaborate in order to achieve a task in a network.
• Overview talks
• Constrained Tree-Decompositions
• Efficient computation of tree-decompositions is a challenging task. Indeed, computing optimal tree-decompositions is NP-hard and, while FPT, no practical algorithms exist for computing tree-decomposition of width at most k, for k at least 5. For handling this problem, I consider new constraints and/or measures that could be added to achieve efficient approximation algorithms to compute treewidth. One measure I am particularly interested in is the length of a tree-decomposition which, roughly, corresponds to the diameter of the bags of a tree-decomposition.
• Treelength and pathlength of subclasses of planar graphs (based on this paper and this paper). We mainly consider the computation of treelength in series-parallel graphs and of pathlength in outerplanar graphs.
• Seminar project COATI, Sophia Antipolis, December 13rd, 2022.
• Seminar ParGO team, Universidade Federal do Ceara, Fortaleza, Brazil, November 18th, 2022.
• When treewidth and treelength are equivalent (based on this paper). We prove that approximation algorithm for treelength also approximates treewidth in the class of bounded genus graphs (more generally in apex-minor-free graphs) with small isometric cycles.
• Seminar Xidian University, Xi'an, China, September 5th, 2018.
• Seminar project COATI, Sophia Antipolis, June 21st, 2016.
• 2nd Workshop Franco-brésilien de Graphes et Optimisation Combinatoire (GCO), Praia de Redonda, Brazil, March 31st, 2016
• Seminary of ACRO team, LIF, Marseille, France, June 28th, 2015.
• Minimum size Tree-Decompositions, based on this paper. Here, we consider tree-decompositions of given width k and minimum number of bags.
• LAGOS 2015, Praia das Fontes, Ceara, Brasil, May 12th, 2015.
• Non-deterministic Graph Searching, Duality and Graph Minors
• The equivalence between graph searching and tree/path-cecompositions relies in the monotonicity property. We define the non deterministic variant of graph searching where the searchers can ask the position of the fugitive a bounded number of times. We generalize the monotonicity results of Bienstock and Seymour, and Seymour and Thomas. Non-deterministic graph searching hence includes both visible (treewidth) and invisible (pathwidth) graph searching. This allows us to generalize brambles, the dual notion of treewidth, to other structures.
• Distributed Graph Searching
• In a distributed setting, searchers are automata/robots that all exectute the same algorithm using only local information. In particular, robors have usually no global knowledge of the network. We mainly study the tradeoff between the amount of local information available to robots and the possibility/performance of search strategies.
• Overiew talk.
• Groupe de travail de l'équipe MoVe, LIF, Marseille, October 30th, 2008
• Seminar project MASCOTTE, INRIA Sophia Antipolis, October 8th, 2008
• 2nd Workshop on GRAph Searching, Theory and Applications (GRASTA), Redonda, Brasil, February 27th, 2008
• Monotonicity with Advice, based on Graph Searching with Advice.
In this paper, we consider the amount of (global) information that must be initially available in each node to ensure that the minimum number of robots can clear a graph in a monotone way and in a distributed setting.
• General Distributed Algorithm, based on Distributed Chasing of Network Intruders by Mobile Agents.
We give a distributed algorithm that allows robots to clear any graph in an asynchronous setting and without any global information about the network. The asynchronicity requires only one extra robot compared to the optimal number of robots in a centralized setting. The resulting strategy is however non-monotone and may have exponential length.
• SIROCCO'06, Chester, England, July 3rd, 2006
• Réunion FRAGILE, Ile d'Oléron, September 7th, 2006
• Connected Graph Searching
• In connected graph searching, the ``cleared" part of the graph (where the fugitive cannot stand) must always induce a connected subgraph. In other words, all searchers start in a same node, and a searcher can be placed only at a neighbor of an already occupied node. We investigate the cost of the connectivity constraint in terms of number of searchers. We also study the impact of this constraint on monotonicity. Since then, Dereniowski has proved that connected pathwidth is at most twice the pathwidth (2011).
• Overview talk
• Séminaire projet MASCOTTE, INRIA Sophia Antipolis, December 19th, 2006
• Groupe de travail de l'équipe MC2 (LIP), Lyon, April 12nd, 2006
• Visible Fugitive, based on Monotony Properties of Connected Visible Graph Searching.
We show that, in the case of a visible fugitive, the connectivity constraint may increase the number of searchers up to a ratio log(n). Moreover, the corresponding graph searching variant is not monotone.
• WG'06, Bergen, Norway, June 23th, 2006
• Journées ResCom (french talk), Lille, March 6th, 2006
• Cost of Connectedness, based on Connected Graph Searching.
We propose a polynomial-time algorithm that, given a tree-decomposition of a graph, computes a ``connected" tree-decomposition of it without increasing its width. It allows us to show that connectivity constraint cannot increase ``too much" the number of searchers to capture an invisible fugitive.
• LATIN'06, Valdivia, Chile, March 21th, 2006
• AlgoTel'05 (french talk), Presqu'île de Giens, May 11th, 2005
• Réunion FRAGILE, Aussois, March 23th, 2005
• Séminaire GrafComm, Orsay, February 18th, 2005
• Réunion TAROT, Lyon, October 14th, 2004
• 6mes Journées "Graphes et Algorithmes", Grenoble, September 29th, 2004
• Master Defense (very short french talk), Orsay, June 2004
• Exclusive Graph Searching
• We define exclusive graph searching as a variant of mixed graph searching with the additional constraint that, at each step, each node can be occupied by at most one searcher. We prove that the corresponding search number provides an approximation of the pathwidth in graphs with bounded maximum degree. Moreover, this variant allows us to design fault tolerant strategies for clearing a graph in a distributed setting.

Routing Reconfiguration in WDM Networks

The configuration of a network (e.g. WDM) corresponds mainly to the routing (and wavelengths assignment) of connection requests of the network. To optimize the usage of resources with the evolution of the traffic matrix, or to avoid using particular resources subject to maintenance operation, it may be necessary to change the configuration of the network. It is then required to first determine the new configuration and then to schedule necessary changes to switch from the current configuration to the new one, while limiting possible traffic perturbations to customers (traffic disruption). The latter problem is called the routing reconfiguration problem. The study of the reconfiguration problem led to the definition of a new variant of graph searching in directed graph, called processing game.
In this game, searchers can (as in classical graph searching) be placed at or removed from vertices of the graph. The difference comes from the way the fugitive is captured: the capture occurs as soon as the fugitive cannot access a strongly connected subgraph without any searcher. In particular, it means that capturing the fugitive does not require to visit all vertices. For instance, in symmetric digraph, the fugitive is captured if it is surrounded by searchers.

Distributed Routing

Routing tables are a zone of local information available in each node of a network. When a message arrives at some node v, it chooses what is its next hop accoring to its destination and the content of the routing table of v. For instance, when you arrive in some city, the next road you will follow depends on your destination and on the road signs that you see. The performance measures are the size of the routing tables and the length of the routes.
Current telecommunication networks are subject to huge dynamicity (topology, traffic). Therefore, new paradigms of routing must be proposed to handle this dynamicity (e.g., update routing tables). In particular, structural properties must be considered.
• Finding Datas with Liers (slides from N. Hanusse), based on Locating a target with an agent guided by unreliable local advice.
Here, we assume that, given on destination node t, each node indicates a shortest path toward t. However, a bounded number of nodes are liers and indicate a false information. We present a probabilistic routing scheme with good performances in path and in random regular graphs. The latter result mainly uses the fact that random regular graphs are expanders. The performance of our routing scheme in other graph classes (in particular in multi dimensional grids) is left open.
• Nice Workshop on Random Graphs, Lab. Dieudonne, Nice, May 15th, 2014.
• Séminaire de l'équipe-project MASCOTTE, INRIA Sophia Antipolis, March 15th, 2011
• IMSA Workshop on Algorithms and Randomness, Santiago, Chile, January 18th, 2011
• Compact Routing in Chordal Graphs, based on Distributed computing of efficient routing schemes in generalized chordal graphs.
We propose a compact routing scheme with good performances in chordal graphs, i.e., if induced cycles of the network are not ``too" large. The advantage of our scheme is that routing tables can be efficiently computed by a distributed algorithm.
• Groupe de travail Alcatel-Lucent-Belgique/MASCOTTE/LaBRI, LaBRI, Bordeaux, December 3rd, 2009
• Groupe de travail Alcatel-Lucent-Belgique/MASCOTTE/LaBRI, Carry-le-Rouet, June 15th, 2009
• Workshop COST 293 GRAAL, Arcachon, France, September 25th, 2008

Graph Optimization

Mainly on graph properties and/or distributed/centralized algorithms to compute them.
• Brief Introduction to Parameterized Algorithms. Online seminar Inria team TADdaaM, October 12th, 2021.
• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation based on this paper.
• Workshop Moving and Computing (MAC), Pisa, Italia, September 21th, 2022.
• GRASCAN, August 5th, 2021.
• On Minimizing the Maximum Color for the 1-2-3 Conjecture based on this paper.
• Séminaire de l'équipe-project COATI, INRIA Sophia Antipolis, April 17th, 2020.
• Maintaining Balanced Trees For Structured Distributed Streaming Systems based on this paper.
• Seminar Univ. Adolfo Ibanez, Santiago, Chile, November 21st, 2017.
• Recovery of disrupted airline operations (in french) based on this paper (and for the LAGOS'talk also on this paper).
Here, we study a graph theoretical problem for helping Airline Operation Controllers. Given a graph G and a matching M, the goal is to compute a maximum matching that can be achieved from M by augmenting paths of length at most k, where k is a fixed odd integer. We prove that the problem is polynomial for k at most 3. Then, we show it s NP-complete for k at least 5, in the class of planar bipartite graphs with maximum degree 3. In this paper, we further investigate this problem (and the other related problem where augmenting paths must have length exactly k) in trees.
• Seminar team ParGO, Univ. federal do Ceara, Fortaleza, Brazil, May 10th, 2019
• Seminar Xidian University, Xi'an, China, September 12th, 2018.
• LAGOS 2017, Marseille, September 11st, 2017.
• Groupe de travail de l'équipe ACRO, LIF, Marseille, July 10th, 2017.
• Seminar Univ. Adolfo Ibanez, Santiago, Chile, November 4th, 2016.
• Séminaire du LIMOS, Univ. Blaise Pascal, Clermont-Ferrand, January 28th, 2016.
• Séminaire de l'équipe-project COATI, INRIA Sophia Antipolis, July 7th, 2015.
• AlgoTel 2015, Beaune, June 3rd, 2015.
• Weighted coloring in trees based on this paper.
Given a vertex-weighted graph and a proper coloring of it, the weight of a color is the maximum weight of a node with that color. The weight of a coloring is the sum of the weight of its colors. The weighted coloring problems aims at finding a proper coloring with minimum weight. We prove that under the Exponential Time Hypothesis (no sub-exponential time algorithm can solve 3-SAT), the best algorithm to solve the Weighted Coloring Problem in trees has time-complexity nΘ(log n) where n is the size of the input tree.
• STACS 2014, Lyon, March 6th, 2014.
• Séminaire de l'équipe-project MASCOTTE, INRIA Sophia Antipolis, March 5th, 2013.
• Computing in one Round, based on Adding a referee to an interconnection network: What can(not) be computed in one round and Allowing each node to communicate only once in a distributed system: shared whiteboard models
In this work, we define a particular computing model. Each node of a labeled graph computes a message with size O(log n), based on the labels of its neighbors and on its own label. Then, using only the messages of all the n nodes, global properties of the network must be computed. We investigate which kind of graph properties can be computed. For instance, deciding whether a graph contains a triangle is not possible in this model. On the other hand, in the class of bounded degeneracy graphs, the whole map of the graphs can be computed.
• Réunion ANR Displexity, Arcachon, September 3rd, 2015.
• Réunion ADR Network science, LINCS, Paris, February 28th, 2013.
• Séminaire de l'équipe-project MASCOTTE, INRIA Sophia Antipolis, November 2nd, 2010
• Small survey on results About small worlds (no slides). Séminaire de l'équipe-project MASCOTTE, INRIA Sophia Antipolis, July 12th, 2011.
• About PCP theorem and Hardness of Approximation (slides). JCALM15, Sophia Antipolis, france, March 10th, 2015.

Popularization
• Posters de vulgarisation d'informatique théorique...ou pas (in french)
• Posters de vulgarisation sur les graphes (avec des jeux, bien sur...) (in french)
• Fête de la science, Inria Sophia Antipolis, Oct. 7th 2018.
• Fête de la science, Palais des Congrès de Juan-Les-Pins, Oct. 22-23rd, 2016, Oct. 7-8th, 2017, Oct. 20-21th, 2018
• Fête de la science, Collège de Vinon-sur-Verdon, Oct. 11-13th, 2016, Oct. 10-12th, 2017, Oct. 9-12th, 2018
• Week of Maths. Presentations at ESPE (in front of future teachers), Nice, 19-20 March and 9-10 April 2018, 22 March 2019.
• Combinatorial Games (in french)
• Collège Sydney Bechet, Antibes, March 14th, 2019
• Lycée Carnot, Cannes, March 13th, 2019
• Lycée des Remparts, Marseille, April 17th, 2015
• Lycée Marcel Pagnol, Marseille, December 2013