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
- Survey on Cops and Robber Games
- JGA 2015, Orléans, November 4th, 2015.
- GRASTA-MAC'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.
Cops and Robber Games
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.
- 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.
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'é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.
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,
- 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.
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 that could be added to achieve efficient approximation algorithms to compute treewidth.
- 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
FRAGILE, Paris, June 19th, 2007
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.
- 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 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.
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.
A Kuratowski theorem for general surfaces, based on "Graphs on Surfaces" [Mohar and Thomassen].
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
équipe Graphes et applications, LaBRI, Bordeaux, May 11th, 2007
- Monotonicity, based on Monotonicity Property of Non-Deterministic 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
Non-deterministic Graph Searching, based on Non-Deterministic Graph Searching: From Pathwidth to Treewidth.
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
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).
- Overiew talk.
- Groupe de travail de l'équipe MoVe, LIF, Marseille, October 30th, 2008
- Seminar project MASCOTTE, INRIA Sophia Antipolis, October 8th, 2008
Workshop on GRAph Searching, Theory and Applications (GRASTA),
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
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.
- 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 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
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
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 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.
- 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.
- 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 Juan-Les-Pins, October 7-8th, 2017
Fête de la science, Collège de Vinon-sur-Verdon, October 10-12th, 2017
- Fête de la science, Palais des Congrès de Juan-Les-Pins, October 22-23rd, 2016
Fête de la science, Collège de Vinon-sur-Verdon, October 11-13th, 2016
- Combinatorial Games (in french)
Lycée des Remparts, Marseille, April 17th, 2015
Lycée Marcel Pagnol, Marseille, December 2013