Game Development Reference
In-Depth Information
3 There are examples of invisible graph searching games which are NP -
complete.
Proof In a Searcher-monotone strategy the cop-player can only make at
most polynomially many steps as he is never allowed to return to a vertex
once vacated. As C is concise, this means that a complete strategy for the
Searcher can be kept in polynomial space and therefore we can simply guess
a strategy and then check that it is a winning strategy by playing it. This,
clearly, can be done in polynomial time.
Megiddo et al. [1988] show that the invisible graph searching game is
NP-complete and as this game is monotone Part 3 follows.
The following table summarises the general results we can obtain.
variant
visible
invisible
non-monotone
Exptime Pspace
k free
monotone
Pspace
NP
non-monotone
Ptime
Pspace
k -Searcher
monotone
Ptime
NP
7.7.2 Parametrised complexity of graph searching
Due to their close connection to graph decompositions, graph searching
games have been studied intensively with respect to parametrised complexity.
We refer to Downey and Fellows [1998] and Flum and Grohe [2006] for an
introduction to parameterised complexity.
Definition 7.50
be a concise class of graph searching games. The
problem p -Vis Search Width(
Let
C
C
) is defined as
p -Vis Search Width( C )
Input:
G∈C
and k
N
Parameter:
k
Problem:
Is there a winning strategy for k searchers
on
G
in the visible fugitive game?
)is fixed-parameter tractable (fpt) if there
is a computable function f :
p -Vis Search Width(
C
N N
, a polynomial p ( n ) and an algorithm
deciding the problem in time f ( k )
).
The problem is in the complexity class XP if there is a computable
function f :
·
p (
|G|
f ( k ) .
N N
and an algorithm deciding the problem in time
|G|
Analogously we define p -Mon Vis Search Width(
C
) as the problem to