Fedor V Fomin

Pierre Fraignaud

Nicolas Nisse

Dimitrios M Thilikos

Report on GRASTA 2014 *

Introduction

Graph searching involves a team of mobile agents (called searchers or pursuers or cops) that aims at capturing a set of escaping agents (called evaders or fugitives or robbers) that hide in a network modeled by a graph. There are many variants of graph searching studied in the literature, often referred to as a pursuitevasion game or cops and robbers game. These variants are either application driven, i.e. motivated by problems in practice, or are inspired by foundational issues in Computer Science, Discrete Mathematics, and Artificial Inteligence. Thus many researchers from different areas of Mathematics, Computer Science and Operations Research are interested in quite similar problems around graph searching.

GRASTA 2014 is the main forum on graph searching and was held in the Institut d'Etudes Scientifiques of Cargèse, Corsica, France. It gathered 43 researchers from diverse areas of Theoretical Computer Science and Discrete Mathematics related to Graph Searching Games and their Applications both from the applied and the theoretical point of view. The program included 2 keynote talks, 18 regular talks, and 2 open problem sessions.

Objectives

Graph searching was introduced by Breisch (Southwestern Cavers Journal 1967) proposing a "speleotopological" approach for the problem of finding an explorer who is lost in a complicated system of dark caves (see the recent book [Breisch11]). The first mathematical models on Graph Searching were then introduced by Torrence Parsons and Nikolai Petrov in the 70's (e.g., [START_REF] Parsons | Pursuit-evasion in a graph[END_REF]) while the first variants, along with the corresponding algorithmic and complexity results, appeared during the 80's [MGH+88].

Graph searching revealed the need to express in a formal mathematical way intuitive concepts such as avoidance, surrounding, sense of direction, hiding, persecution, and threatening. Clearly, such a project led to the study and introduction of various complicated combinatorial structures. One of the most powerful combinatorial tools used in the study of such structures emerged from the Graph Minors theory, developed by Robertson and Seymour towards proving the long-standing Wagner's Conjecture [START_REF] Robertson | Graph minors -a survey[END_REF]. The collection of results and methodologies derived from the Graph Minors Theorem are acknowledged as among the most influential results in modern combinatorics. They include deep graph-theoretic results and techniques with direct consequences to problems at the kernel of Graph Searching problems (e.g., [START_REF] Seymour | Graph searching and a min-max theorem for tree-width[END_REF]).

The graph searching games may vary significantly according to the capabilities of the evaders and the pursuers in terms of relative speed, sensor capabilities, visibility, etc. Also, the notion of capture itself admits several interpretations. Therefore, many variants have been studied in the literature [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF]. A different, and somehow independent, branch of research on graph searching is the Cops and Robber games defined by Winkler and Nowakowski, and independently by Quilliot, in 1983. In this variant, Meyniel conjectured in 1985 that the number of cops needed to capture a robber is O( √ n) in any connected nnode graph. During the last few years, a huge effort of research has been devoted to prove this conjecture which is still open (e.g., see [START_REF] Bollobas | Cops and robbers in a random graph[END_REF][START_REF] Bonato | The Game of Cops and Robbers on Graphs[END_REF][START_REF] Scott | A new bound for the cops and robbers problem[END_REF]). We do hope that the Workshop will bring us a bit closest to the solution.

Several variants are motivated by problems in practice. For instance, in the seminal variant of Parsons, the problem can be also formulated as the problem of clearing a contaminated network (e.g., by some poisonous gas). The Cleaning with Brushes variant arises from the need to have robots clean networks with conditions that do not allow access to humans (e.g. cleaning the cooling pipes in a nuclear power plant, or cleaning biofilm from small pipes). In what follows, we mention some of the existing applications (practical and fundamental) of Graph Searching.

• Information Seeking: Here the searchers represent information sharing models or mobile software agents that are looking for information. Information can be hidden, migrating, moving, and evolving and therefore can be viewed as one or more potential evaders from the searchers.

• Robot motion planning: Motion planning is one of the central problem in the development of autonomous robots. Can a robot plan its root to achieve a certain goal and to avoid colliding with other robots? Can a team of robots detect a mobile intruder or guard some area from intrusion? To address these type of questions, pursuit-evasion games are the natural setting.

• Graph Theory. One of the most powerful combinatorial tools for analyzing cops-and-robbers games emerged from the Graph Minors theory, developed by Robertson and Seymour towards proving the long-standing Wagner's Conjecture. The collection of results and methodologies derived by this project are acknowledged as among of the most influential results in modern combinatorics. They include deep graph-theoretic results and techniques with direct consequences to problems at the kernel of the cops-and-robbers games.

• Database Theory and Cops and Marshals Games: Among the (practically) most important database query mechanisms are conjunctive queries. While general conjunctive query evaluation is NPcomplete, Yannakakis proved that it can be done in polynomial time if the queries are acyclic. One of the most convincing concepts for generalising the notion of acyclicity for conjunctive queries has been introduced by Gottlob et al. with the concept of hypergraph decompositions, in particular hypertree-width. Hypertree-width is an adaptation of tree-width to hypergraphs and it has been shown that conjunctive queries of bounded hypertree-width can be evaluated in polynomial time. An elegant and intuitive way to understand hypertree-width is based on Robber and Marshal games, an adaptation of graph searching to hypergraphs. Robber and Marshal games provide valuable insight into hypertree-decompositions and naturally yield a notion of obstructions to small hypertree-width in forms of hyperbrambles.

Following Feder and Vardi's observation, that conjunctive query evaluation, the graph homomorphism problem and constraint satisfaction problems are essentially the same problem, hypergraph decompositions and hence Robber and Marshal games have found applications in constraint satisfaction also.

• Logic: Computational aspects of logical systems are intensively studied in areas such as databases, artificial intelligence and verification. For instance, current approaches to hard-and software verification rely on efficient methods for evaluating logical formulas in process models, i.e. in graphs.

Games have always played an important role in logic, for instance in the use of Ehrenfeucht-Fraïssé or pebble games for comparing models of logical formulas, or, more recently, the use of modelchecking games as a game based approach to the evaluation problem of logical systems. Among evaluation games, parity games modeling the evaluation problem of the modal µ-calculus are perhaps the most prominent and the precise complexity of deciding the winner of a parity game is the most important problem in this area, with significant applications to the theory of verification.

While model-checking games differ in some aspects from graph searching games, they share a core of common methods and problems and it seems likely that there are fruitful connections between the two areas. For instance, Berwanger and Grädel use a graph searching game, called Robber and Detective game, as a tool to analyse the model µ-calculus variable hierarchy.

• Distributed Computing: currently, Graph Searching is mostly tackled using centralized methods. Nevertheless, recent advances in Mobile Computing enable to envisage tackling graph searching problems in a distributed framework. This framework is in fact the natural one for many applications of graph searching, including network security and decentralized network control.

• VLSI design: Circuit design is directly connected to different variants of graph searching. In each such variant, the target is to improve the way a graph (representing a circuit) can be embedded in a specific pattern taking into account different optimization criteria.

• Models of computation: The graph represents a computation circuit, and searching the graph is associated with pebble games on the graph that capture various computational complexity measures.

• Routing in telecommunication networks: To optimize the usage of resources with the evolution of the traffic in telecommunication networks, it may be necessary to change the configuration (set of routes of the connections) 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 In this talk, we discuss the computational complexity of deciding whether k cops can capture a robber on a graph G. How fast (or how slow) are the best possible computer algorithms for determining who wins? In 1995, Goldstein and Reingold conjectured that the problem is EXPTIME-complete -in other words, that Cops and Robbers is among the "hardest" problems that can be solved in time exponential in the size of the input. Goldstein and Reingold themselves proved EXPTIME-completeness of two specialized variants of Cops and Robbers, but were unable to say anything about the original game. In fact, it was not until recently that partial results began to emerge: in 2010, Fomin et al. showed the game to be NP-hard, and in 2013, Mamino showed it to be PSPACE-hard. By combining Mamino's ideas with our own insights, we prove that Cops and Robbers is, in fact, EXPTIME-complete.

Searching hidden Structures and Activities in Large Networks

David Peleg, Weizmann Institute of Science, Israel

The talk will discuss various contexts in which it is required to identify some structural pattern or activity pattern in a large network. Examples to be discussed include identifying nodes suspected as involved in money laundering in a network of transactions, and identifying the elite in a social network.

Regular Talks:

Star search and related problems: recent techniques, measures and results Spyros Angelopoulos, LIP6, CNRS, Univ. Paris 6, France

We study two optimization problems in the presence of set-up costs. The first problem involves a searcher (e.g., robot) that must locate a target which lies in one of many concurrent rays, and at an unknown position from their common origin. Every time the searcher turns direction, it incurs a turn cost. The objective is to derive a search strategy for locating the target as quickly as possible. The second problem involves contract algorithms, namely algorithms in which the available computation time is specified prior to their execution. More precisely, we seek a schedule of executions of contact algorithms for several different problems in a single processor so as to simulate an interruptible algorithm, assuming that each execution incurs a given set-up cost. Upon interruption, any one of the problems can be queried for its current solution. The performance of the search and scheduling strategies are evaluated by means of well-established measures, namely the competitive ratio and the acceleration ratio, respectively.

In this presentation we provide optimal strategies for the above problems. We demonstrate that a previous approach based on infinite LP formulations due to Demaine et al. [TCS 2006] can lead to erroneous results. We provide a nontrivial correction to their result, and we prove that infinite LPs can be used so as to derive optimal schedules of contract algorithms as well.

Cop and robber game and hyperbolicity

Jérémie Chalopin, CNRS, LIF, Univ. Aix-Marseille, France

In this talk, we consider a variant of the cop and robber game where the cop and the robber move at different speed. The difference with the classical cop and robber game is that at each step, the cop can move along a path of lenght at most s', and the robber can move along a path of length at most s without going through the position of the cop. A graph is (s, s )-copwin if the cop with speed s' has a strategy to capture any robber moving at speed s. Delta-hyperbolic graphs are graphs that are close to trees from a metric point of view; we will present a few (of the many) definitions of hyperbolicity.

We then will present some results relating the cop and robber game and the hyperbolicity of a graph. We show that if a graph is delta-hyperbolic, then it is (2r, r + 2δ)-copwin for any r. Conversely, we show that a (s, s )-copwin graph is δ-hyperbolic with δ = O(s 2 ). From our approach, we deduce an O(n 2 log n) algorithm to approximate the hyperbolicity of a graph when we are given its distance matrix This talk is based on joint works with V. Chepoi, N. Nisse and Y. Vaxès, and with V. Chepoi, P. Papasoglu and T. Pecatte.

Practical computation of pathwidth

David Coudert, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France Path-decompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NP-hard problems. Therefore, computing the pathwidth and associated pathdecomposition of graphs has both a theoretical and practical interest. In this presentation, we will present a Branch and Bound algorithm that computes the exact pathwidth of graphs and a corresponding pathdecomposition. Our main contribution consists of several non-trivial techniques to reduce the size of the input graph (pre-processing) and to cut the exploration space during the search phase of the algorithm. We have evaluated experimentally our algorithm by comparing it to existing algorithms of the literature. It appears from the simulations that our algorithm offers a significant gain with respect to previous work. In particular, it is able to compute the exact pathwidth of any graph with less than 60 nodes in a reasonable running-time (less than 10 min.). Moreover, our algorithm also achieves good performance when used as a heuristic (i.e., when returning best result found within bounded time-limit). Our algorithm is not restricted to undirected graphs since it actually computes the vertex-separation of digraphs (which coincides with the pathwidth in case of undirected graphs). This is joint work with D. Mazauric and N. Nisse.

Connected graph searching: a distributed algorithm

Dariusz Dereniowski, Gdansk University of Technology, Poland

We revisit a problem of converting a path decomposition into a connected one. This problem is reformulated as searching a certain graph in which searchers can distinguish directions. In this talk we discuss a distributed/online approximation algorithm for searching such graphs, i.e., algorithm in which the searchers learn the structure of an underlying graph as they reach new nodes.

Cops and Robber in geometric intersection graphs

Tomáš Gavenčiak, Charles University, Prague, Czech Republic

The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph G, one controlling k cops and the other one robber, all positioned on V G . The players alternate in moving their pieces to distance at most 1 each. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop-number of G, that is the smallest k such that k cops win the game, has recently been a widely studied parameter.

Intersection graph classes are defined by their geometric representations: the vertices are represented by certain geometrical shapes and two vertices are adjacent if and only if their representations intersect. Some well-known intersection classes include interval and string graphs. Various properties of many of these classes have been studied recently, including an interest in their game-theoretic properties.

In this paper we show an upper bound on the cop-number of string graphs and sharp bounds on the cop-number of interval filament graphs, circular graphs, circular arc graphs and function graphs. These results also imply polynomial algorithms determining cop-number for all these classes and their subclasses.

The cost of drunkenness for visible and invisible robbers

Athanasios Kehagias, Aristotle University of Thessaloniki, Greece

The cops and robbers game has been studied under the assumption of optimal play by both the cops and the robbers. In this talk I will present results (by P. Pralat, D. Mitsche and A. Kehagias) regarding the CR game played by optimal cops and a DRUNK robber (that is, a robber who performs a random walk on a graph). Our main goal is to characterize the "cost of drunkenness", i.e., the ratio of expected capture times for the optimal and the drunk robber versions of the game. Clearly this ratio will never be less than one; we prove that actually it can asymptotically reach any value in [1, ∞). Furthermore, we examine an additional variant of the CR game, in which the robber is "invisible", i.e., the cops only learn his position on capture. This variant can also be played with either an optimal or a drunk robber and the capture time is well defined in both cases (to show this we use game theoretic concepts). Hence the cost of drunkenness can also be computed in this case. We show that in fact the "invisible cost of drunkenness" can asymptotically reach any value in [2, ∞) but there is a gap for values in (1,2). We also present algorithms to compute capture times and cost of drunkenness for all the variants mentioned. Finally, we obtain estimates of the (visible and invisible) cost of drunkenness for special graph familes such as trees and grids.

The computational complexity of Cops and Robbers

Minor closedness property for variants of tree-width O-joung Kwon, Department of Mathematical Sciences, KAIST, South Korea Classical cop and robber game is related to the well-known parameter of a graph, called tree-width. Tree-width can be defined as the minimum integer k such that the given graph has an embedding on chordal graphs with maximum clique size k + 1. Recently, people suggested some variants of tree-width using embedding on other intersection models instead of chordal graphs. We prove that for parameters, spaghetti tree-width, directed path tree-width and strongly chordal tree-width, the graphs having the parameter at most k are closed under taking minors if and only if k is at most two. We also discuss some relations between these parameters and variants of search games.

This is joint work with Seongmin Ok

Expanding search on a network

Thomas Lidbetter, London School of Economics, UK

An immobile Hider is located on a rooted network according to some probability distribution. A Searcher tries to find the Hider in minimal expected time, using an expanding search: this is a nested family of connected subsets of the network, starting at the root and increasing at unit speed. Assuming the Hider's distribution is known to the Searcher, we solve the problem for tree networks. We then suppose the Searcher does not know the Hider's distribution, and model the problem as a zero-sum game in which the Hider tries to maximize the expected time to be found. We give a solution of the game for trees and 2-arc connected networks, and a lower bound on the value for general networks. This is joint work with Steve Alpern.

Exclusive Graph Searching in Various Graph Classes

Euripides Markou, University of Thessaly, Lamia, Greece

In Graph Searching, a team of searchers tries to capture an invisible fugitive who is moving arbitrary fast in a graph. Many variants of this problem have been studied with respect to the constraints that the searchers strategy must satisfy. We study here the Exclusive Graph Searching problem in which two searchers can not occupy simultaneously a node. We will discuss the complexity of finding the minimum number of searchers capable of solving the problem in various classes of graphs. We show that the problem is NP-hard in planar graphs with maximum degree 3. We will also present a graph family in which the problem of finding a monotone strategy of a minimum number of searchers remains NP-hard and some other graph families in which the problem can be solved in polynomial time.

Joint work with Nicolas Nisse and Stéphane Pérennes.

The (all guards move) Eternal Domination number for 3 × n grids:

Margaret-Ellen Messinger, Mount Allison University, Canada

In the eternal dominating set problem, guards form a dominating set on a graph and at each step, a vertex is attacked. After each attack, if the guards can 'move' so that they form a dominating set containing the attacked vertex, then the guards have 'defended against the attack'. We wish to determine the minimum number of guards required to defend against any sequence of attacks, the eternal domination number. As the domination number for grid graphs was recently determined (2011), grid graphs are a natural class of graphs to consider for the eternal dominating set problem. Though the eternal domination number has been determined for 2 × n-grids and 4 × n grids, it has remained only loosely bounded for the 3 × n-grid. We determine the eternal domination number for 3 × n grids.

Joint work with S. Finbow, M. van Bommel, A.Z. Delaney

A note on the acquaintance time of random graphs

Dieter Mitsche, Lab. J.A.Dieudonné, Univ. Nice-Sophia Antipolis, France

We prove a conjecture of Benjamini, Shinkar and Tsur on the acquaintance time AC(G) of a random graph G in G(n, p). It is shown that asymptotically almost surely AC(G) = O(log n/p) for G in G(n, p), provided that pn-log n-log log n → ∞ (that is, above the threshold for Hamiltonicity). Moreover, we show a matching lower bound for dense random graphs, which also implies that asymptotically almost surely K n cannot be covered with o(log n/p) copies of a random graph G ∈ G(n, p), provided that np > n 1/2+ and p < 1for some > 0. We conclude the paper with a small improvement on the general upper bound showing that for any n-vertex graph G, we have

AC(G) = O(n 2 / log n).
Joint work with William B. Kinnersley and P. Pralat

Fractional Combinatorial Two-Player Games Nicolas Nisse, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France

We propose a fractional relaxation of two-player combinatorial games. Two players can move or/and add fractions of tokens on the nodes of a graph and a player wins if he is the first one to reach a configuration in some specified set. Both allowed moves and winning configurations are defined thanks to convex sets. Our framework applies to many two-players games including the fractional variant of cops and robber games. We give some results and promising perspectives of this new framework.

Joint work with F. Giroire, S. Pérennes and R.P. Soares.

Bounds on the Cover Time of Parallel Rotor Walks

Dominik Pajak, LaBRI, Inria, Univ. Bordeaux, France

The most natural deterministic analogue of the random walk in a graph is a process when walkers are propagated by each node to its neighbors in round-robin fashion. Such process, called the rotor-router has applications for example in load balancing and rumor spreading. We will study the speedup of k-agent rotor-router system with respect to the cover time of a single walk. In this talk we will completely resolve the question of the possible range of speedups, showing that its value is between Θ(log k) and Θ(k), for any graph. Both of these bounds are tight. Thus, the proven range of speedup for the rotor-router corresponds precisely to the conjectured range of speedup for the random walk.

Patrolling Games

Katerina Papadaki, London School of Economics, UK

This paper describes a class of patrolling games on graphs, motivated by the problem of patrolling a facility (for example in order to defend an art gallery against theft of a painting, or an airport against terrorist attack). The facility can be thought of as a graph Q of interconnected nodes (e.g. rooms, terminals) and the Attacker can choose to attack any node i of Q within a given time T : He requires m consecutive periods there, uninterrupted by the Patroller, to commit his nefarious act (and win). The Patroller can follow any path on the graph. Thus the patrolling game is a win-lose game, where the Value is the probability that the Patroller successfully intercepts an attack, given best play on both sides. We determine analytically optimal (minimax) patrolling strategies for various classes of graphs.

On the Minimum Node and Edge Searching Spanning Tree Problems

Sheng-Lung Peng, National Dong Hwa University, Taiwan For a graph G = (V, E), the graph searching problem on G is to determine the minimum number of searchers to clean G via the searching rules. It is studied for a long time and in particular, two variants, namely, node searching and edge searching, are well studied. In this talk, we propose the minimum node (edge) searching spanning tree problem on G. The objective is to find a spanning tree T of G such that the node-search (edge-search) number of T is the minimum among all possible spanning trees of G. We show that both the 4-searchable node and edge searching spanning tree problems are NP-hard and propose approximation algorithms for these two problems.

Monotonicity in directed cops and robber games

Roman Rabinovich, Technische Universität Berlin, Germany

We consider the cops and robber games characterizing DAG-width and directed tree-width (up to a constant factor). In the former the cops win only if they never allow the robber to visit vertices that have already been occupied by cops. This robber-monotonicity is rather fragile. Many graph transformations preserve the number of cops needed to capture the robber, but not the robber-monotonicity. It is an open question whether the robber-monotonicity cost (the difference between the minimal numbers of cops capturing the robber in the general and in the robber-monotone case) can bounded by some function. Examples show that this function (if it exists) is at least f (k) > 4k/3 [Kreutzer, Ordyniak 2008]. We approach a solution by defining weak monotonicity and showing that if k cops win weakly monotonically, then O(k 2 ) cops win monotonically. It follows that DAG-width is bounded in Kelly-width, which has been open since the definition of Kelly-width [Hunter, Kreutzer 2008]. For the game that corresponds to directed tree-width we show that, unexpectedly, the cop-monotonicity cost (no cop revisits any vertex) is not bounded by any function. This separates directed tree-width from D-width defined by Safari in 2005.

Similarity of treewidth and MM-width by a cops and robber game Jan Arne Telle, Univ. of Bergen, Norway

Using a branch decomposition that partitions the vertex set of a graph, with the cut function being the size of a maximum matching, M.Vatshelle (PhD Thesis 2012) defined the MM-width of a graph. By a non-monotone strategy for a cops and robber game he showed that MM-width and treewidth are bounded on the same classes of graphs. It was recently shown by S.H. Saether that a monotone strategy can be found efficiently, and that the cut function used to define MM-width is submodular. In this talk we present these results.

Contraction obstructions for connected graph searching Dimitrios Thilikos, AlGCo project-team, CNRS, LIRMM, France and Department of Mathematics, University of Athens, Greece Many applications of graph searching demand that there always exist a safe path between the searchers so to maintain their safe communication. This variant is known as connected graph searching and was introduced by Lali Barrière et al. In this talk we consider the graph classes with bounded connected mixed-search number and we deal with the the question weather the obstruction set, with respect of the contraction partial ordering, for those classes is finite. In general, there is no guarantee that those sets are finite, as the contraction ordering is not a W.Q.O. of the class containing all graphs. Our main result is that for k = 2 the obstruction set contains exactly 174 graphs that completely characterize the graphs with connected mixed search number at most 2. Our proof reveals that the "sense of direction" of an optimal search searching is impotent for connected search which is in contrast to the unconnected origin al case. We also give a double exponential lower bound at the size of the obstruction set for the classes where it is finite. This is join work with Micah J. Best, Arvind Gupta, and Dimitris Zoros.

Open problems

Nicolas Nisse Price of the connectivity for surveillance. The surveillance problem deals with the following two players game in an n-node (di)graph G = (V, E) with a given starting vertex v 0 ∈ V . There are two players, fugitive and observer. The fugitive wants to escape the control of an observer whose purpose is to keep the fugitive under constant surveillance. Let k ≥ 1 be a fixed integer. The game starts when the fugitive stands at v which is initially marked. Then, turn by turn, the observer controls, or marks, at most k vertices and then the fugitive either moves along an edge to a (out-)neighbor of her current position, or skip her move. In other words, at every step of the game the observer enlarges observable part of the graph by adding to it k, not necessarily adjacent, vertices. And his task is to ensure that the fugitive is always in the observable area. Note that, once a vertex has been marked, it remains marked until the end of the game. The fugitive wins if, at some step, she reaches an unmarked vertex and the observer wins otherwise. That is, the game ends when either the fugitive enters an unmarked vertex (and then she wins) or all vertices have been marked (and then observer wins). The surveillance number of G, denoted by sn(G, v), is the least k such that there is a winning k-strategy of observer in G of the fugitive starting from v.

Consider the variant of the game where at every step of the game the set of vertices marked by the observer is connected (that is, the set of already marked nodes union the new marked nodes must be connected). Let csn(G, v 0 ) be the connected surveillance number. What is the relation between two surveillance numbers? Is there a constant c such that for any graph G and vertex

v ∈ V (G), csn(G, v) sn(G, v) ≤ c?
What is known, there exist graph G and v ∈ V (G) such that csn(G, v) = sn(G, v)+2. Also it is possible to show that for any graph G and vertex

v ∈ V (G), csn(G, v) ≤ |V (G)| • sn(G, v).
David Ilcinkas Dynamic Graph Exploration. In the graph exploration problem, an explorer is willing to visit every vertex of a given graph G within a minimum number of steps. Each step consists of moving from a vertex to an adjacent vertex. For an n-vertex graph one needs at least n -1 steps to explore the graph. The upper bound of 2n -3 follows from the strategy of walking along the edges of a spanning tree.

What happens in the following dynamic setting, when instead of a graph, we are given an evolving graph, that is a sequence of static graphs,

G = (G 1 , G 2 , . . . )
such that all graphs are on the same vertex set, and each of the graphs is connected? What is the bound on the number of steps for the dynamic graph exploration (traversing an edge takes one unit of time)? The worst-case exploration time of such a dynamic graph based on the ring is exactly 2n -3 (see reference below). On the other hand, a trivial upper bound is (n -1) 2 (the temporal diameter of any constantly connected evolving graph is at most n -1).

Update. Jan Kratochvil proposes the following dynamic graph based on the vertex set V = {v 0 , v 1 , . . . , v n-1 }: the static graph at time t is the star centered at node v t mod n/2 . Between two visits of a node in the set {v n/2 , . . . , v n-1 }, the agent must wait at least n/2 time units, yielding to an overall exploration time of roughly (n/2) 2 .

The open problem can now be reformulated as follows: what is the worst-case exploration time of a dynamic graph whose underlying graph has m edges? (The underlying graph has edge {u, v} iff the edge {u, v} is present at least once in the evolving graph.) Note that, from Jan's construction, we know that this worst-case exploration time is in Ω(m).

Besides, what is the worst-case exploration time of a dynamic graph based on a cactus (roughly a tree of rings)?

Velner, yet unpublished). What happens for d = 2? An answer would be interesting already for the case when all moves are along the axes. additional restriction: R ⊆ R. Note, however, that the (weak) monotonicity condition is not affected by that restriction (otherwise we have the game corresponding to directed tree-width [3]). Most likely, both questions in this formulation have a negative answer (the √ n× √ n-grid, as suggested by P. Golovach, or the incidence graph of the projective plane of order √ n have to be considered in this respect), but maybe they are still worth to be considered for classes of graphs.

Victor Chepoi

Alternatively, in Question 1 instead of hitting will vertices, one can consider hitting C with shortest paths of G or/and with distance-preserving subtrees of G (say, induced stars), and, more generally, with neighborhoods of shortest paths, etc. One can also replace √ n by another sublinear function, say by n 2 3 . The "cop-and-robber" motivation for these questions comes from a result of [1] that the cop-number cn(G) of a graph G without induced cycles of length k is at most k -1. On the other hand, it is known that for each shortest path P of G a constant number of cops can prevent the robber R entering the neighborhood of P (one cop is enough to prevent entering R in a distance-preserving tree of G). Hence, if C can be hit with O( √ n) such objects (each of which can be controlled with a constant number of cops), then by [1], the remaining part of G can be controlled with O( √ n) cops and this will show that the cop-number of G is O( √ n).

Question 1 :

 1 Hitting and packing induced cycles of length ≥ √ n. For an undirected graph G with n vertices, let C := {C : C is an induced cycle of length at least √ n}. Is the size of a minimum hitting set of C of size O( √ n)? Question 2: Is the size of a minimum hitting set of C bounded by a linear function of the maximum number of disjoint cycles from C?

  France and Department of Mathematics, University of Athens, Greece • Minor closedness property for variants of treewidth O-joung Kwon, Dept of Math. Sciences, KAIST, South Korea On the Minimum Node and Edge Searching Spanning Tree Problems Sheng-Lung Peng, National Dong Hwa University, Taiwan • Practical computation of pathwidth David Coudert, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France

	2 Program
		Wednesday, April 2nd
	9 : Keynote 2	Monday, March 31th
	09 : 10 : 30 11 : 00 10 : 10 : Keynote 1 11 : 00 Complexity of graph searching games (2/2) Registration, Welcome Searching hidden Structures and Activities in Large Networks David Peleg Coffee Break The computational complexity of Cops and Robbers (Weizmann Institute of Science, Israel) 10 : • Exclusive Graph Searching in Various Graph Classes 10 : 11 : Coffee Break 11 : 30 Euripides Markou, University of Thessaly, Lamia, Greece
	11 : 11 : Cops and Robber (1/2) (Ryerson University, Toronto, Canada) Bill Kinnersley 11 : Search in graphs 11 : 30 Lunch 13 : 00 • Star search and related problems: recent techniques, measures and results Spyros Angelopoulos, LIP6, CNRS, Univ. Paris 6, France 13 : 00 End of the conference, departure of the shuttle for Ajaccio after lunch
	• Cops and Robber in geometric intersection graphs • Expanding search on a network
	). Coudert et al. pro-posed a modelization of this problem in terms of a graph searching problem in directed graphs. This formulation allowed to provide solutions and tradeoffs for the routing reconfiguration problem. 12 : Tomas Gavenciak, Charles University, Prague, Czech Republic 12 : 14 : Lunch 12 : Thomas Lidbetter, London School of Economics, UK 3 Abstracts 12 : 14 : Lunch Keynote talks:
	• Network security: Applications of this type concern clearing a network of pipes contaminated by 14 : 19 : Excursion Bill Kinnersley, Ryerson University, Toronto, Canada
	some poisonous gas, capturing intruders resorting in a building or in a road network, disease control, robot motion co-ordination, and virus elimination problems. Franklin, Galil, and Yung used graph 20 : ... Gala Dinner
	searching to model the problem where a set of eavesdroppers is trying to collect information hidden
	in nodes of a network.
		Thursday, April 3rd
	15 : 16 : 18 : 16 : 10 : 10 :	Coffee Break Open Problems session Coffee Break
		Tuesday, April 1st
	15 : 16 :	Open Problems session
	16 : 16 :	Coffee Break
	12 : 14 : 16 : 18 :	Lunch Working session
	14 : 16 : 16 : 16 :	Working session Coffee Break Friday, April 4th
	16 : 18 :	Working session

14 : Cops and Robber (2/2) 15 :

• Cop and robber game and hyperbolicity Jérémie Chalopin, CNRS, LIF, Univ. Aix-Marseille, France • The cost of drunkenness for visible and invisible robbers Athanasios Kehagias, Aristotle Univ. of Thessaloniki, Greece • Fractional Combinatorial Two-Player Games Nicolas Nisse, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France 09 : Pursuit-evasion games and width parameters (1/2) 10 : • Similarity of treewidth and MM-width by a cops and robber game Jan Arne Telle, Univ. of Bergen, Norway • Monotonicity in directed cops and robber games Roman Rabinovich, Technische Universität Berlin, Germany 10 : 11 : Coffee Break 11 : Pursuit-evasion games and width parameters (2/2) 12 : • Contraction obstructions for connected graph searching Dimitrios Thilikos, AlGCo project-team, CNRS, LIRMM, 10 : Pursuit-evasion games in graphs (1/2) 12 : • Patrolling Games Katerina Papadaki, London School of Economics, UK • Connected graph searching: a distributed algorithm Dariusz Dereniowski, Gdansk University of Technology, Poland • A note on the acquaintance time of random graphs Dieter Mitsche, Lab. J.A.Dieudonné, Univ. Nice-Sophia Antipolis, France 12 : 14 : Lunch 11 : Pursuit-evasion games in graphs (2/2) 12 : • Bounds on the Cover Time of Parallel Rotor Walks Dominik Pajak, LaBRI, Inria, Univ. Bordeaux, France • The (all guards move) Eternal Domination number for 3 x n grids Margaret-Ellen Messinger, Mount Allison University, Canada 09 : Complexity of graph searching games (1/2) 10 : 30 •

We consider the cops and robber game as defined by Nowakowski and Winkler [1]. Two players play alternately on a graph G: first the C places its cops on nodes of G then R chooses one vertex to place its robber. Then, alternately starting with C, the players may move each of their token along an edge of the graph. C wins if eventually, one of its cops occupies the same node as the robber.

We consider the following variant where the graph is directed. The only constraint is that the robber must follow the arcs (the cops may move along the arcs or in the reverse direction). Is it possible to characterization (in terms of dismantling ordering of the vertices) of the Cop-win graphs (where a single cop has a winning strategy) in this variant?

If we restrict also the cops to follow the arcs, the same question arises. Moreover, what is the copnumber of tournaments? (question of G. Hahn)

2014 was partly funded by Univ. Nice Sophia Antipolis, the laboratory I3S and Inria. The last author was cofinanced by the E.U. (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: "Thales. Investing in knowledge society through the European Social Fund".

where cost(S, T ) is the time required to reach T by making use of strategy S, and |T | is the distance of the target from the origin. This problem is well-understood, see e.g. the textbook by Alpern and Gal [1].

The optimal strategy is based on doubling, and incurs a competitive ratio equal to 9. Alpern and Gal introduced the variant of the problem in which the Searcher is required to pass over the target at least r times so as to locate it. We do not know the optimal strategies for this problem. It is known that the best strategies based on "doubling" achieve a competitive ratio of 20, whereas better non-monotone straregies achieve competitive ratios at least 17.2. For instance, one can define a strategy in which the searcher "hovers" around the turn points before returning to the origin. To my knowledge, this is the simplest example of a search problem for which the "back-and-forth" strategies based on doubling are not efficient. We currently do not have the appropriate tools for analyzing such non-monotone strategies.

[1] S. Alpern and S. Gal. The theory of search games and rendezvous. Kluwer Academic Publishers, 2003 Roman Rabinovich The price of monotonicity in directed search. The question was asked in [1]. The two players are a team of two cops who can fly by helicopters and a infinitely fast visible robber. The robber is captured if he has no legal move (in particular, he cannot stay on his vertex). Formally, let G be a directed graph and k ∈ N. Positions of the cops have the form

The initial position of the game (∅, ∅, ∅) belongs to the robber and there are moves from (∅, ∅, ∅) to any position (∅, R), where R is strongly connected. The cops win if the robber cannot make any move, the robber wins if the game goes on forever.

In the robber-monotone variant, the cops win only those plays in which the robber can never visit a vertex that has already been occupied by a cop, i.e. the cops lose in positions

This variant of the game corresponds to DAG-width [1] (the DAG-width of the graph is the least number of cops needed to capture the robber in a robber-monotone way).

The problem is whether there is a function f : N → N such that if k cops capture the robber, then f (k) cops capture the robber robber-monotonically.

It suffices to consider weak monotonicity instead of (strong) robber-monotonicity [2]. A play is weakly monotone if the robber can never reach a vertex that has been occupied by a chaser (a cop who was placed into the robber component). The set M (C, R) of such vertices in a position (C, R) is history dependent and can be formally described inductively: M (∅, R) = ∅ and if the last moves are

We can also assume that the robber is shy, i.e. he never leaves his component. Formally, the robber moves (C, C , R) → C , R have an

Bill Kinnersley Complexity of Eternal Domination

Consider the following process on a graph G. Initially, some number of guards occupy some set S of vertices of G (no two guards can occupy the same vertex). At each time-step, some vertex v of G gets "attacked" by a robber. In response, some guard must move to v from an adjacent vertex; if the guards can do this, we say that they have "defended" the attack. (Note that only one guard may move on each time-step, and that guard must move to the attacked vertex.) This process continues indefinitely. If the guards can defend against any infinite sequence of attacks, then we say that S is an eternal dominating set of G. The minimum size of an eternal dominating set of G is the eternal domination number of G, denoted γ ∞ (G). One may also consider the variant in which any subset of guards may move on a single time-step; the corresponding paramteter is the all-guards move eternal domination number of G, denoted γ ∞ all (G).

Given a graph G and a set S of vertices of G, what is the computational complexity of deciding whether S is an eternal dominating set of G? Similarly, given a graph G and integer k, what is the computational complexity of deciding whether G has an eternal dominating set of size at most k? Both of these problems may be considered both in the one-guard move model and the all-guards move model.

All four problems are known to belong to EXPTIME. For the one-guard move model, it was shown by Klostermeyer [3] that deciding whether S is an eternal dominating set of G is coNP NP -hard. For the all-guards move model, no hardness results are known (for either problem). However, it is worth noting that the all-guards move model of eternal domination can be viewed as a special case of the so-called guarding problem; Fomin, Golovach, and Lokhstanov [2] proved that the guarding problem is PSPACEhard in general, and asked whether it is PSPACE-complete. The closely-related eternal vertex cover problem, in which attacks are made on edges, an attack is defended by moving a cop along the attacked edge, and all cops may move on every turn, was shown by Fomin et al. to be NP-hard [1].

Conference photo

Photo of the participants of GRASTA 2014, April 01, 2014