Game Development Reference
In-Depth Information
7.3.6 Games played on hypergraphs
Graph searching games have also found applications on hypergraphs. Gottlob
et al. [2003] study a game called the Robber and Marshal game on
hypergraphs. In the game, the fugitive, here called the robber, occupies
vertices of the hypergraph whereas the searchers, here called marshals, occupy
hyper-edges. The game is somewhat different from the games discussed above
as a marshal moving from a hyper-edge e to a hyper-edge h still blocks the
vertices in e
h . In particular, one marshal is enough to search an acyclic
graph, viewed as a hypergraph in the obvious way, whereas we always need
at least two cops for any graph containing at least one edge in the visible
cops and robber game.
Formally, given a hypergraph H := ( V ( H ) ,E ( H )) the Robber and Marshal
game on H is defined as
G
H := ( V,
S
,
F
,c ) where
• V := V ( H ) ˙
∪E ( H )
( X, X ) ∈S if X, X ⊆ E ( H )
•F
( X, R, X ):=
if R
V ( H )or R
⊆{
v
V ( H ):
e
X, v
e
}
and
( X, R, X ):=
otherwise
F
{
v
V ( H ) : there is a path in H from a vertex
R to v not going through any vertex in X
X }
u
c ( X ):=
|
X
|
.
Robber and Marshal games have been studied in particular in connec-
tion to hypergraph decompositions such as hypertree-width and generalised
hypertree-width and approximate duality theorems similar to the one we will
establish in Sections 7.4.2 and 7.6 have been proved by Adler et al. [2005].
7.3.7 Further variants
Finally, we briefly comment on further variants of graph searching. Here we
concentrate on games played on undirected graphs, but some of the variants
translate easily to other types of graphs such as digraphs or hypergraphs.
An additional requirement sometimes imposed on the searchers is that at
every step in a play the set of vertices occupied by searchers needs to be
connected . This is, for instance, desirable if the searchers need to stay within
communication range. See, e.g., Fomin and Thilikos [2008] for references on
connected search.
Another variation is obtained by giving the searchers a greater radius of
visibility. For instance, we can consider the case where a searcher not only
dominates his own vertex but also all vertices adjacent to it. That is, to
catch the robber it is only necessary to trap the robber in the neighbourhood