Game Development Reference
In-Depth Information
questions about the variable hierarchy in the modal μ -calculus, as explored
See the annotated bibliography of graph searching by Fomin and Thilikos
[2008] for further applications and references.
As different applications require different types of games, it is not surprising
that graph searching games come in many different forms. We will give an
overview of some of the more commonly used variants of games in the
Section 7.3.
Organisation. This chapter is organised as follows. In Section 7.2 we first
define graph searching games in an abstract setting and we introduce formally
the concept of monotonicity. We also explore the connection between graph
searching and reachability games and derive a range of general complexity
results about graph searching games. In Section 7.3 we present some of the
more commonly used variants of graph searching games. The monotonicity
problem and some important tools to show monotonicity are discussed in
Section 7.4. Formalisations of winning strategies for the fugitive in terms of
obstructions are discussed in Section 7.5. We will explore the connections
between graph searching and graph decompositions in Section 7.6. Finally,
in Section 7.7 we study the complexity of deciding the minimal number of
searchers required to search a graph in a given game and we close this chapter
by stating open problems in Section 7.8. Throughout the chapter we will
use some concepts and notation from graph theory which we recall in the
appendix.
7.2 Classifying graph searching games
In the previous section we have described one particular version of graph
searching, also known as the Invisible Cops and Robber games. Possible
variants of this game arise from whether or not the fugitive is invisible, from
the type of graph the game is played on, i.e., undirected or directed, a graph
or a hypergraph, whether the searchers can move freely to any position or
whether they can only move along one edge at a time, whether searchers only
dominate the vertex they occupy or whether they dominate other vertices as
well, whether the fugitive or the searchers can move in every round or only
once in a while, and many other differences. The great variations in graph
searching games has made the field somewhat confusing. The fact that the
same names are often used for very different games does not help either. In