Game Development Reference
In-Depth Information
distinction between visible and invisible fugitives, which cannot be defined
in the description of the game. We can therefore speak about the class
of
the Cops and Robber games played on undirected graphs but have to say
explicitly whether we mean the visible or invisible variant.
We will study the complexity questions both within classical complexity
as well as parameterised complexity. But before that, we need to agree on
the size of a graph searching game. For this we need to following restriction
on games.
C
Definition 7.43
A class C of graph searching games is concise if
1 there is a polynomial p ( n ) such that for every G := ( V,S,F,c ) ∈C and all
X ∈ Pow( V ), c ( X ) ≤ p ( |X| ) and
2 given X, X
( X, X ) can be decided in polynomial time
V the relation
S
and
3 given X, X ,R
V and v
V we can decide in polynomial time whether
( X, R, X ).
v
∈F
This condition rules out degenerate cases where, e.g., all Searcher positions
have complexity 1. But it also disallows games where deciding whether a move
is possible for any of the players is already computationally very complex.
All graph searching games studied in this chapter are concise.
Definition 7.44
The size
|G|
of a graph searching game
G
:= ( V,
S
,
F
,c )
is defined as
|
V
|
.
This definition is in line with the intuitive definition of size for, e.g., the
visible cops and robber game where the input would only be the graph, and
therefore the size would be the order or the size of the graph, whereas the
rules of the game are given implicitly.
7.7.1 Classical complexity bounds for graph searching games
In this section we present some general complexity bounds for graph searching
games in the framework of classical complexity.
Definition 7.45
be a concise class of graph searching games. The
problem Vis-Search Width(
Let
C
C
) is defined as
Vis Search Width(
C
)
Input:
G∈C and k ∈ N
Problem:
Is there a winning strategy for k searchers
on G against a visible fugitive?