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

Short Overview of the subject area

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., [Parsons78]) 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 [RobertsonS85]. 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., [SeymourT93]).

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 litterature [FominT08]. 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 n-node 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 [BKL,BonatoN11,ScottS11]). 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 NP-complete, 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 model-checking games as a game based approach to the evaluation problem of logical systems. Among evaluation games, parity games modelling the evaluation problem of the modal $\mu$-calculus are perhaps the most prominent and the precise complexity of deciding the winner of a parity game is the most important proplem 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 $\mu$-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). Coudert et al. proposed 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.
• Network security: Applications of this type concern clearing a network of pipes contaminated by 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 searching to model the problem where a set of eavesdroppers is trying to collect information hidden in nodes of a network.

References.

• [APW08] N. Alon, P. Pralat, and N. Wormald, Cleaning regular graphs with brushes, SIAM Journal on Discrete Mathematics 23 (2008), 233-250.
• [BKL] B. Bollobas, G. Kun, I. Leader, Cops and robbers in a random graph, preprint.
• [BonatoN11] A. Bonato and R. Nowakowski, The Game of Cops and Robbers on Graphs. American Mathematical Society, 2011.
• [Bresich11] R. L. Breisch, Lost in a Cave - Applying Graph Theory to Cave Exploration. 298 pages, National Speological Society, 2011.
• [FominT08] F.V. Fomin and D.M. Thilikos, An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399(3): 236-245, 2008.
• [MHG+88] N. Megiddo, S.L. Hakimi, M.R. Garey, D.S. Johnson, C.H. Papadimitriou, The complexity of searching a graph, J. Assoc. Comput. Mach. 35 pp. 18--44, 1988.
• [Parsons78] T.D. Parsons, Pursuit-evasion in a graph, in: Theory and applications of graphs, in: Lecture Notes in Math., vol. 642, Springer, Berlin, pp. 426--441, 1978.
• [RobertsonS85] N. Robertson, P.D. Seymour, Graph minors -- a survey, Surveys in combinatorics, London Math. Soc. Lecture Note Ser., vol. 103, Cambridge Univ. Press, pp. 153--171, 1985.
• [ScottS11] A. Scott and B. Sudakov, A new bound for the cops and robbers problem, SIAM J. Discrete Math. 25(3): 1438-1442, 2011.
• [SeymourT93] P.D. Seymour, R. Thomas, Graph searching and a min-max theorem for tree-width, J. Comb. Theory Ser. B, 58, pp. 22--33, 1993.