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