Abstract:
We study the computational complexity of certain search-hide games
on a graph. There are two players, called searcher and hider.
The hider is immobile and hides in one of the nodes of the graph.
The searcher selects a starting node and a search
path of length at most k.
His objective is to detect the hider, which he does
with certainty if he visits the node chosen for hiding.
Finding the optimal randomized strategies in this zero-sum game defines a
fractional path covering problem and its dual, a fractional packing problem.
If the length k of the search path
is arbitrary, then the problem is NP-hard.
The problem remains NP-hard if the searcher may freely revisit nodes
that he has seen before. In that case, the searcher selects a
connected subgraph of k nodes rather than a path of k nodes.
If k is logarithmic in the number of nodes of the graph,
then the problem can be solved in polynomial time.
This is shown using a recent technique called
color-coding due to Alon, Yuster, and Zwick.
The same results hold for edges instead of nodes, that is,
if the hider hides in an edge and the searcher
searches k edges on a path or on a connected subgraph.
Keywords: Covering and packing, game theory, graph search,
NP-completeness.
In: Discrete Applied Mathematics 78 (1997), 235-249.
gz-compressed POSTSCRIPT-file (117 kB, 16 pages).
Back to Bernhard von Stengel's
list of publications