# The Dracula game

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.

• This game is more widely known as Scotland Yard (or Police 07 in Hungary). – domotorp Apr 16 '11 at 11:51
• You may find some information under the name "pursuit-evasion game", see en.wikipedia.org/wiki/Pursuit-evasion – Marcus Ritt Apr 16 '11 at 12:45
• @Marcus: I think You can write it as an answer. Now I know the most important thing - 'real' name of this problem, which will help to me to find references. – Tomek Tarczynski Apr 17 '11 at 11:51

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.