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.

References.