Communications
My main concern is to design efficient algorithms for solving problems arising in telecommunication networks. Since most of these problems are NPhard in general, I try to use structural properties of considered networks to derive polynomialtime 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 pursuitevasion 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 Pursuitevasion Games and Applications
 Survey on Cops and Robber Games
 JGA 2015, Orléans, November 4th, 2015.
 GRASTAMAC'15, Montréal, Canada, October 19th, 2015.
 Jounées du GDR IM, Bordeaux, Feb. 2nd, 2015.
 HDR Defense, Sophia Antipolis, May 26th, 2014.
 AlDyNet Workshop on Algorithms and Randomness, Santiago, Chile, November 21st, 2013.
Combinatorial (turnbyturn twoplayer) 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 copnumber 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(n^{1/2}) cops are sufficient to capture a robber in any nnode 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.
 Localization GameS in graphs based on this paper and this 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.
 Seminar project COATI, Sophia Antipolis, March 27th, 2018
 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 polynomialtime 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 SpyGame 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 twoplayer turnbyturn 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 nnode 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 kChordal 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 kchordal graphs (graphs with no induced cycles greater than k). This leads us to a greedy algorihtm to compute a particular treedecomposition of graphs that have a nice structure, in particular, in kchordal 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, PSPACEcomplete in DAGs) and we design polynomialtime 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), 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'équipeproject MASCOTTE, INRIA Sophia Antipolis, October 25th 2011
 Copwin 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 copnumber 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'équipeproject 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 copnumber of a graph is NPhard.
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
 Seminar project COATI, Sophia Antipolis, October 8th, 2014
 Seminar project Anillo en Redes (DIM), Santiago, Chile, October 12nd, 2007
 Ph.D. Defense, Orsay, July 2nd, 2007
 Réunion
FRAGILE, Paris, June 19th, 2007
 Constrained TreeDecompositions
Efficient computation of treedecompositions is a challenging task. Indeed, computing optimal treedecompositions is NPhard and, while FPT, no practical algorithms exist for computing treedecomposition of width at most k, for k at least 5. For handling this problem, I consider new constraints that could be added to achieve efficient approximation algorithms to compute treewidth.
 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 apexminorfree graphs) with small isometric cycles.
 Seminar project COATI, Sophia Antipolis, June 21st, 2016.

2nd Workshop Francobré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 TreeDecompositions, based on this paper. Here, we consider treedecompositions of given width k and minimum number of bags.
 LAGOS 2015, Praia das Fontes, Ceara, Brasil, May 12th, 2015.
 Nondeterministic Graph Searching, Duality and Graph Minors
The equivalence between graph searching and tree/pathcecompositions 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.
Nondeterministic 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.

A Kuratowski theorem for general surfaces, based on "Graphs on Surfaces" [Mohar and Thomassen].
 7th
Journees Combinatoire et Algorithmes du Littoral Mediterraneen (JCALM), Sophia Antipolis, France, October 19th, 2009

Duality Decompositions/Brambles, based on Submodular Partition Functions.
 2nd Journees Combinatoire et Algorithmes du Littoral Mediterraneen (JCALM), Montpellier, France, April 27th, 2007
 Séminaire équipe GraphComb, Orsay, May 25th, 2007
 Séminaire
équipe Graphes et applications, LaBRI, Bordeaux, May 11th, 2007
 Monotonicity, based on Monotonicity Property of NonDeterministic Graph Searching.
 WG 2007 (short english talk), Dornburg, Germany, June 21st, 2007
 1st Workshop on GRAph Searching, Theory and Applications (GRASTA), Anogia, Crete,
October 10th, 2006
 8mes Journées "Graphes et Algorithmes" (french talk), Orléans, November 9th, 2006

Nondeterministic Graph Searching, based on NonDeterministic Graph Searching: From Pathwidth to Treewidth.
 AlgoTel'06,
Tregastel, May 11st, 2006
 Séminaire GrafComm (long french talk), Orsay, January 13th, 2006
 7mes Journées "Graphes et Algorithmes", Bordeaux, November 3rd, 2005
 Workshop on Graph Classes, Width Parameters and Optimization, Prague, Czech Republic, October 19th, 2005
 MFCS'05, Gdansk, Poland, September 1st, 2005
 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 nonmonotone 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 polynomialtime algorithm that, given a treedecomposition of a graph, computes a ``connected" treedecomposition 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.
 Exclusive Graph Searching in CORDA model based on Gathering and Exclusive Searching on Rings under Minimal Assumptions
 Seminar project COATI, INRIA Sophia Antipolis, February 11th, 2014
 ICDCN'14, Coimbatore, India, January 5th, 2014
 Exclusive Graph Searching in trees (no slides) based on Exclusive Graph Searching
 Seminar project COATI, INRIA Sophia Antipolis, July 16th, 2013
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.
 Overview talk
 Reconfiguration and Graph Searching, mainly based on Routing Reconfiguration/Process Number: Coping wih Two Classes of Services.
We show that processing game is equivalent to graph searching in the combinatorial complexity point of view. We also present an heuritic to solve the routing reconfiguration problem.
 Groupe de travail équipe Graphes et applications, LaBRI, Bordeaux, March 13th, 2009
 Séminaire LIFL, Lille, March 5th 2009
 Tradeoffs, based on Tradeoffs in process strategy games with application in the WDM reconfiguration problem.
In processing game, the less searchers are used and the more nodes must be occupied (equivalently, the more requests must be interrupted). We study the tradeoff between the number of searchers that are used and the number of visited nodes. Equivalently, it represents the tradeoff between the total number of perturbations induced in a reconfiguration and the maximum number of perturbations at any time of the reconfiguration.
 AlgoTel'10 (short talk), Belle Dune, June 3rd, 2010
 Réunion ANR ALADDIN, LaBRI, Bordeaux, November 27th, 2009
 Shared Wavelength, based on On Rerouting Connection Requests in Networks with Shared Bandwidth.
In this work, we show that routing reconfiguration becomes much more difficult when requests may share wavelength. We leave open the question of the complexity of this problem when at most two requests can share one wavelength. Note that modelling the routing reconfiguration problem with shared wavelength by a graph searching game is also open.
 AGT 2009, Warwick, England, March 24th, 2009
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'équipeproject 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 AlcatelLucentBelgique/MASCOTTE/LaBRI, LaBRI, Bordeaux, December 3rd, 2009
 Groupe de travail AlcatelLucentBelgique/MASCOTTE/LaBRI, CarryleRouet, 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.
 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 NPcomplete 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.
 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, ClermontFerrand, January 28th, 2016.
 Séminaire de l'équipeproject COATI, INRIA Sophia Antipolis, July 7th, 2015.
 AlgoTel 2015, Beaune, June 3rd, 2015.
 Weighted coloring in trees based on this paper.
Given a vertexweighted 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 subexponential time algorithm can solve 3SAT), the best algorithm to solve the Weighted Coloring Problem in trees has timecomplexity n^{Θ(log n)} where n is the size of the input tree.
 STACS 2014, Lyon, March 6th, 2014.
 Séminaire de l'équipeproject 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'équipeproject MASCOTTE, INRIA Sophia Antipolis, November 2nd, 2010
 Small survey on results About small worlds (no slides). Séminaire de l'équipeproject 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, Palais des Congrès de JuanLesPins, October 78th, 2017

Fête de la science, Collège de VinonsurVerdon, October 1012th, 2017
 Fête de la science, Palais des Congrès de JuanLesPins, October 2223rd, 2016

Fête de la science, Collège de VinonsurVerdon, October 1113th, 2016
 Combinatorial Games (in french)

Lycée des Remparts, Marseille, April 17th, 2015

Lycée Marcel Pagnol, Marseille, December 2013