Search Games: A Review - Search Theory: A Game Theoretic Perspective - page 4

The search strategy used for Eulerian graphs can be extended to non-Eulerian
graphs by using a random Chinese postman tour that encircles S ∗ equiprobably in
each direction. It was proven by Gal [ 25 ] that a random Chinese postman tour is an
optimal search strategy if and only if Q is weakly Eulerian (a set of Eulerian sub-
graphs connected in a tree-like fashion). The optimal hiding strategy is obtained by
an attractive algorithm using a tree which is equivalent in some sense to the original
graph.
If the graph is not weakly Eulerian then the optimal solution of the search game
is very complicated. The following deceptively simple example illustrates the dif-
ficulties. Assume that Q consists of just three arcs of unit length. connecting two
nodes, the origin O and another node A (Fig. 1.1 ).

Fig. 1.1 The three arcs graph

It is obvious that an optimal search strategy has to pick a random arc and go to A
but what to do then? Surprisingly it is not optimal to pick another arc at random and
fully traverse it (and later the remaining arc). It turns out that the optimal strategy,
upon reaching A is to randomly pick one of the unvisited arcs, go a random distance

on it and return to A

,

Only then fully traverse the third arc and the partly visited
arc. (For details, see [ 4 ] p. 33.) This strategy was suggested by Donald J. Newman
in the late 1970s but the rigorous proof of its optimality is very complicated and
took about 15 years to establish [ 40 ]. In general, the problem of finding the optimal
search strategy is NP-hard as shown (see [ 43 ]). The search game on a graph can, in

.