Name
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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1016/S0166-218X(97)00011-5 | Discrete Applied Mathematics |
Keywords | Field | DocType |
game theory,immobile hider,np-completeness,covering and packing,graph search,polynomial time,np completeness,computational complexity,zero sum game | Graph theory,Discrete mathematics,Graph,Combinatorics,Packing problems,Game theory,Zero-sum game,Logarithm,Time complexity,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
78 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
9 | 0.81 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernhard von Stengel | 1 | 275 | 38.51 |
| Ralph Werchner | 2 | 113 | 9.56 |