COMPLEXITY OF SEARCHING AN IMMOBILE HIDER IN A GRAPH

We study the computational complexity of certain search-hide games on a graph. There are two players, called searcher and hider. The hider i s immobile and hides in one of the nodes of the graph. The searcher se lects a starting node and a search path of length at most k. His objec tive 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 r ather than a path of k nodes. If k is logarithmic in the number of nod es of the graph, then the problem can be solved in polynomial time. Th is is shown using a recent technique called color-coding due to Alon, Yuster and Zwick. The same results hold for edges instead of nodes, th at is, if the hider hides in an edge and the searcher searches k edges on a path or on a connected subgraph.