GRASTA 2014
6th Workshop on GRAph Searching, Theory and Applications

March 31th-­April 4th, 2014 ,Cargèse, Corsica, France

• Home
• Venue
• List of Participants
  
• List of talks
  
• Program
  
• About Graph Searching
• Previous GRASTA
• Contact

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 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.


• 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.

Regular talks

• Spyros Angelopoulos, LIP6, CNRS, Univ. Paris 6, France
  Searching with turn cost and related problems
  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 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. Aix-Marseille, 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. 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+2delta)-copwin for any r. Conversely, we show that a (s,s')-copwin graph is delta-hyperbolic with delta = O(s²). From our approach, we deduce an O(n² 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:
  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 path-decomposition 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 path-decomposition. 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 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 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.


• 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.


• O-joung Kwon, Department of Mathematical Sciences, KAIST, South Korea
  Minor closedness property for variants of tree-width:
  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


• 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 zero-sum game in which the Hider tries to maximise 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.


• 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 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.
  


• Margaret-Ellen 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. Nice-Sophia 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 pn-log n-log 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 < 1-epsilon for some epsilon > 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


• Nicolas Nisse, Inria, Univ. Nice Sophia Antipolis, CNRS, I3S, France
  Fractional Combinatorial Two-Player Games
  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.


• 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 round-robin fashion. Such process, called the rotor-router has applications for example in load balancing and rumour 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.


• 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 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.


• Sheng-Lung 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 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.


• Jan Arne Telle, Univ. of Bergen, Norway
  Similarity of treewidth and MM-width 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 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.
  


• Dimitrios Thilikos, AlGCo project-team, 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 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 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.