Game Development Reference

In-Depth Information

by three parallel edges, then the edge search number of
G
is one more than

the node search number of
G
.

LaPaugh [1993] proved that the edge searching game is monotone thereby

giving the first monotonicity proof for a graph searching game. Using the

correspondence between edge searching and node searching, Kirousis and

Papadimitriou [1986] establish monotonicity for the node searching game.

Bienstock and Seymour [1991] consider a version of invisible graph searching,

called
mixed searching
, where the searcher can both slide along an edge or

move to other nodes clearing an edge as soon as both endpoints are occupied.

They give a simpler monotonicity proof for this type of game which implies

the previous two results.

A very general monotonicity proof for games with an invisible robber

based on the concept of sub-modularity was given by Fomin and Thilikos

[2003]. We will present an even more general result using sub-modularity in

Section 7.4 below.

Using a reduction from the Min-Cut Into Equal-Sized Subsets prob-

lem, Megiddo et al. [1988] showed that edge searching is NP-complete. Using

the correspondence between edge and node searching outlined above, this

translates into NP-completeness of the node searching variant, i.e., the Invis-

ible Cops and Robber Game defined above.

7.3.3 Visible Robber games

We have already introduced the visible cops and robber game above. This

game was studied by Seymour and Thomas [1993] in relation to tree-width, a

connection which we will present in more depth in Section 7.6. In this paper

they introduce a formalisation of the robber strategies in terms of
screens
,

nowadays more commonly referred to as
brambles
, and use this to prove

monotonicity of the visible cops and robber game. A monotonicity proof

unifying this result and the results obtained for invisible robber games has

been given by Mazoit and Nisse [2008]. We will review this proof method in

Section 7.4 below.

Arnborg et al. [1987] proved by a reduction from the Minimum Cut

Linear Arrangement problem that determining for a given graph the

minimal
k
such that
G
can be represented as a
partial k-tree
is NP-complete.

This number is equal to the tree-width of
G
and therefore deciding the

tree-width of a graph is NP-complete. We will see in Section 7.6 that the

minimal number of searchers, called the
visible search width
of
G
, required

to catch a visible fugitive in the visible Cops and Robber game on a graph
G

Search Nedrilad ::

Custom Search