The Dracula game

Question

Background
This question is motivated by a board game called 'Dracula'. In this game there is one vampire and four hunters, the purpose of the hunters is to catch the vampire. The game takes place in Europe. The game looks as follows:
1. The hunter player puts all hunters in cities. More than one hunter can be placed in the same city.
2. The vampire player puts the vampire in a city.
3. Players alternately move their creatures to the neighboring cities.
4. The hunter player in his turn may move as many hunters as he wants.
5. The main difficulty is that the vampire player knows all the time where the hunters are, but the hunter player knows only the starting position of the vampire.
6. When a hunter and the vampire meets in a city then the vampire player loses.

Question
For a given graph $G$ and numbers $n$ and $k$, is there a strategy that guarantees the hunter player, who controls $n$ hunters, to catch vampire in less than $k$ turns? It may be assumed that $G$ is planar. Has this problem been studied? Some references would be appreciated.

Answer 1

The game you've described looks a lot like the game of k Cops and 1 Robber, as described in this article by Clarke and Macgillivray : http://www.sciencedirect.com/science/article/pii/S0012365X12000064. Basically, it is played by placing k cops and a robber on the vertices of a graph and asking the cops to catch the robber by moving along the edges.

The main difference from your game and this one is the partial visibility of the hunters, whereas in classical cops and robbers, the cops know exactly where the robber is and vice-versa. Also, in cops and robbers the time is not limited.

Even with complete information, if the time is not limited it has been shown that determining if k-cops could eventually capture the robber in finite time when the robber and the cops play optimally is exponential-time complete (http://arxiv.org/abs/1309.5405) when k isn't fixed. Hence, since your game is harder to play for the cops, I would guess it also can't be solved in polynomial time when time is not limited. I think the number of moves necessary for k cops to catch a robber can be bounded above, by say c, and if the number of steps k allowed to the hunters is close to this number c, then the game of hunters and vampire would be at least as hard to solve than k cops and robber (see the article of Bonato et al. : The capture time of graph).

Answer 2

As noted by @MarcusRitt in the comments, this is known as graph searching. I'd like to add, however, that the specific variant you describe (i.e., relating the number of rounds played with the number of searchers employed) has also been investigated, which is not noted in the Wikipedia article. Interestingly, the transition from search space to search time retains the characterizations of the problem (by introducing appropriate "dual" versions of the respective parameters).

See the article "Graph searching and search time" by Brandenburg and Herrmann at SOFSEM 2006.

Answer 3

If we generalize the game condition then it's equal to Cop-Robber game of path-width. The only relaxation is that robber can move to any vertex $v$ he wants if there is a clean path (no cop along that path) from his current position to $v$. Then the minimum number of cops needed to catch the robber is path-width(G) - $1$. If cops are allowed to see a robber in similar game as I stated, then the minimum number of cops are needed to catch the robber is equal to the tree-width(G) - $1$. In both cases there is a polynomial algorithm to find the robber for a fixed $k$, also for a planar graphs it's possible to approximate the number of cops (and then obtaining corresponding decomposition) in polynomial time. May be you are interested to read more from this lecture notes.