Game Development Reference
In-Depth Information
is equal to the tree-width of G plus one. Hence, deciding the visible search
width of a graph is NP-complete.
7.3.4 Lazy or inert fugitives
In the games studied so far the fugitive was allowed to move at every step
of the game. The inert variant of visible and invisible graph searching is
obtained by restricting the fugitive so that he can only move if a searcher is
about to land on his position. More formally, the inert graph searching game
G
:= ( V,
S
,
F
,c ) is defined as an abstract graph searching game where for all
X, X
X .
Inert fugitive games can be defined for visible and invisible fugitives.
However, as often in life, being lazy and visible is usually not a good idea
wherefore the invisible game has received much more attention. Dendris et al.
[1997] study the invisible inert fugitive game and show it to be equivalent to
the visible cops and robber game. Richerby and Thilikos [2008] study the
inert case for a visible fugitive.
( X, v, X )= v if v
V and v
V ,
F
7.3.5 Games played on directed graphs
The games studied so far have been played on undirected graphs but many
have natural counterparts on directed graphs. Let us first consider the visible
Cops and Robber game played on an undirected graph. Suppose that the
current position for the searchers is X and the robber is on a vertex v .Ifthe
searchers announce their intention to move to their new position X then
the robber can move to any vertex u reachable in G \ ( X ∩ X ) from his
current position v . Obviously this formulation of the game is equivalent to the
formulation where the robber can move freely in the connected component
of G
X ) containing v . While the two presentations are equivalent on
undirected graphs they yield two very different games when translated to
directed graphs.
\
( X
Definition 7.13
Let G be a directed graph and let V := V ( G ), c ( X ):=
|
X
|
V ( G ) and ( X, X )
for all X, X
for all X
∈S
V ( G ).
1 The reachability game on G is defined as the abstract graph searching
game
G
:= ( V,
S
,
F
,c ), where the Fugitive admissibility function
F
is
( X, R, X ):=
defined as
F
{
v
V : there is an u
R and a directed path
X ) from v to u
.
2 The strongly connected component (SCC) game on G is defined as
the abstract graph searching game
in G
\
( X
}
G
:= ( V,
S
,
F
,c ), where the Fugitive

Custom Search