Complexity of Searching an Immobile Hider in a Graph

TitleComplexity of Searching an Immobile Hider in a Graph
Publication TypeTechnical Report
Year of Publication1995
Authorsvon Stengel, B., & Werchner R.
Other Numbers984
KeywordsCovering and packing, game theory, graph search, NP-completeness

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.

Bibliographic Notes

ICSI Technical Report TR-95-044

Abbreviated Authors

B. von Stengel and R. Werchner

ICSI Publication Type

Technical Report