List of presentations
Keynotes

Bill Kinnersley, Ryerson University, Toronto, Canada
The computational complexity of Cops and Robbers:
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 EXPTIMEcomplete  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 EXPTIMEcompleteness 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 NPhard, and in 2013, Mamino showed it to be PSPACEhard. By combining Mamino's ideas with our own insights, we prove that Cops and Robbers is, in fact, EXPTIMEcomplete. 
David Peleg,
Weizmann Institute of Science, Israel
Searching hidden Structures and Activities in Large Networks:
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.

Spyros Angelopoulos, LIP6, CNRS, Univ. Paris 6, France
Searching with turn cost and related problems
We study two optimization problems in the presence of setup 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 setup 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 wellestablished measures, namely the competitive ratio and the acceleration ratio, respectively.
In this presentation we show how to obtain 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. 
Jérémie Chalopin, CNRS, LIF, Univ. AixMarseille, France
Cop and robber game and hyperbolicity:
In this talk, we consider a variant of the cop and rober 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 lenght 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. Deltahyperbolic 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 deltahyperbolic, then it is (2r,r+2delta)copwin for any r. Conversely, we show that a (s,s')copwin graph is deltahyperbolic with delta = 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 
David Coudert, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France
Practical computation of pathwidth:
Pathdecompositions of graphs are an important ingredient of dynamic programming algorithms for solving efficiently many NPhard 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 nontrivial techniques to reduce the size of the input graph (preprocessing) 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 signicative 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 runningtime (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 timelimit). Our algorithm is not restricted to undirected graphs since it actually computes the vertexseparation of digraphs (which coincides with the pathwidth in case of undirected graphs).
This is joint work with D. Mazauric and N. Nisse. 
Dariusz Dereniowski, Gdansk University of Technology, Poland
Connected graph searching: a distributed algorithm
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. 
Tomas Gavenciak, Charles University, Prague, Czech Republic
Cops and Robber in geometric intersection graphs

Athanasios Kehagias, Aristotle University of Thessaloniki, Greece
The cost of drunkenness for visible and invisible robbers:
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,\infty). 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,\infty) 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. 
Ojoung Kwon, Department of Mathematical Sciences, KAIST, South Korea
Minor closedness property for variants of treewidth:
Classical cop and robber game is related to the wellknown parameter of a graph, called treewidth. Treewidth 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 treewidth using embedding on other intersection models instead of chordal graphs. We prove that for parameters, spaghetti treewidth, directed path treewidth and strongly chordal treewidth, 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 
Thomas Lidbetter, London School of Economics, UK
Expanding search on a network
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 zerosum game in which the Hider tries to maximise the expected time to be found. We give a solution of the game for trees and 2arc connected networks, and a lower bound on the value for general networks.
This is joint work with Steve Alpern. 
Euripides Markou, University of Thessaly, Lamia, Greece
Exclusive Graph Searching in Various Graph Classes
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 NPhard 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 NPhard 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.

MargaretEllen Messinger, Mount Allison University, Canada
The (all guards move) Eternal Domination number for 3 x n grids:
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 x n grids and 4 x n grids, it has remained only loosely bounded for the 3 x n grid. We determine the eternal domination number for 3 x n grids.
Joint work with S. Finbow, M. van Bommel, A.Z. Delaney 
Dieter Mitsche, Lab. J.A.Dieudonné, Univ. NiceSophia Antipolis, France
A note on the acquaintance time of random graphs
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 pnlog nlog log n \to \infty (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 \in G(n,p), provided that np > n^{1/2+epsilon} and p < 1epsilon for some epsilon > 0. We conclude the paper with a small improvement on the general upper bound showing that for any nvertex graph G, we have AC(G)=O(n^2/log n).
Joint work with William B. Kinnersley and P. Pralat 
Nicolas Nisse, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France
Fractional Combinatorial TwoPlayer Games
We propose a fractional relaxation of twoplayer 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 twoplayers 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. 
Dominik Pajak, LaBRI, Inria, Univ. Bordeaux, France
Bounds on the Cover Time of Parallel Rotor Walks
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 roundrobin fashion. Such process, called the rotorrouter has applications for example in load balancing and rumour spreading. We will study the speedup of kagent rotorrouter 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 rotorrouter corresponds precisely to the conjectured range of speedup for the random walk. 
Katerina Papadaki, London School of Economics, UK
Patrolling Games
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 winlose 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.  ShengLung Peng, National Dong Hwa University, Taiwan
On the Minimum Node and Edge Searching Spanning Tree Problems

Roman Rabinovich, Technische Universität Berlin, Germany
Monotonicity in directed cops and robber games:
We consider the cops and robber games characterising DAGwidth and directed treewidth (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 robbermonotonicity is rather fragile. Many graph transformations preserve the number of cops needed to capture the robber, but not the robbermonotonicity. It is an open question whether the robbermonotonicity cost (the difference between the minimal numbers of cops capturing the robber in the general and in the robbermonotone 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 DAGwidth is bounded in Kellywidth, which has been open since the definition of Kellywidth [Hunter, Kreutzer 2008].
For the game that corresponds to directed treewidth we show that, unexpectedly, the copmonotonicity cost (no cop revisits any vertex) is not bounded by any function. This separates directed treewidth from Dwidth defined by Safari in 2005. 
Jan Arne Telle, Univ. of Bergen, Norway
Similarity of treewidth and MMwidth by a cops and robber game
Abstract: 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 MMwidth of a graph. By a nonmonotone strategy for a cops and robber game he showed that MMwidth 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 MMwidth is submodular. In this talk we present these results.

Dimitrios Thilikos, AlGCo projectteam, CNRS, LIRMM, France and Department of Mathematics, University of Athens, Greece
Contraction obstructions for connected graph searching
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 mixedsearch 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 original 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 Best, Arvind Gupta, and Dimitris Zoros.