Game Development Reference
In-Depth Information
decide whether k searchers have a monotone winning strategy on
G
and the
corresponding invisible fugitive variants.
The correspondence between visible graph searching games and reachability
games immediately implies the following theorem.
be a concise class of abstract graph searching games.
Then the visible graph searching game on
Theorem 7.51
Let
C
C
is in XP.
This, however, fails for the case of invisible graph searching games. For
instance, Kreutzer and Ordyniak [2009] show that deciding whether two
searchers have a winning strategy in the invisible domination game is Pspace-
complete and therefore the problem cannot be in XP unless Pspace =
Ptime.
Much better results can be obtained for the visible and invisible Cops and
Robber game on undirected graphs. Bodlaender [1996] presented a linear-time
parametrised algorithm for deciding the tree-width and the path-width of a
graph. As we have seen above, these parameters correspond to the visible
and invisible Cops and Robber Game on undirected graphs showing that the
corresponding decision problems are fixed-parameter tractable.
The corresponding complexity questions for directed reachability games,
on the other hand, are wide open.
7.8 Conclusion
The main objective of this chapter was to provide an introduction to the
area of graph searching games and the main techniques used in this context.
Graph searching has developed into a huge and very diverse area with
many problems still left to be solved. Besides specific open problems such as
the approximate monotonicity of directed reachability games in the visible
and invisible inert variant, there is the general problem of finding unifying
proofs for the various monotonicity and complexity results developed in the
literature. Another active trend in graph searching is to extend the framework
beyond graphs or hypergraphs to more general or abstract structures such
as matroids.
Acknowledgement: I would like to thank Isolde Adler for carefully proof
reading the manuscript.
Search Nedrilad ::




Custom Search