<p>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 : <a href="http://www.sciencedirect.com/science/article/pii/S0012365X12000064" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0012365X12000064</a>. 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. </p>

<p>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. </p>

<p>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 (<a href="http://arxiv.org/abs/1309.5405" rel="nofollow">http://arxiv.org/abs/1309.5405</a>) 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).</p>

CC BY-SA 3.0
2014-06-30T14:40:04.110Z
2014-06-30T14:40:04.110Z
user25468
<p>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 <a href="http://www.newton.ac.uk/programmes/LAA/seminars/2006050411001.pdf" rel="nofollow">this</a> lecture notes.</p>

CC BY-SA 3.0
2014-06-30T23:02:48.037Z
2014-06-30T23:02:48.037Z
Saeed
<p>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).</p>

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

CC BY-SA 3.0
2014-07-01T14:02:35.957Z
2014-07-01T14:02:35.957Z
Cornelius Brand
<p><strong>Background</strong><br>
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:<br>
 1. The hunter player puts all hunters in cities. More than one hunter can be placed in the same city.<br>
 2. The vampire player puts the vampire in a city.<br>
 3. Players alternately move their creatures to the neighboring cities.<br>
 4. The hunter player in his turn may move as many hunters as he wants.<br>
 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.<br>
 6. When a hunter and the vampire meets in a city then the vampire player loses.</p>

<p><strong>Question</strong><br>
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.</p>

CC BY-SA 3.0
2011-04-16T11:51:36.837Z
This game is more widely known as Scotland Yard (or Police 07 in Hungary).
domotorp
CC BY-SA 3.0
2011-04-16T12:45:21.820Z
You may find some information under the name "pursuit-evasion game", see http://en.wikipedia.org/wiki/Pursuit-evasion
Marcus Ritt
CC BY-SA 3.0
2011-04-17T11:51:40.567Z
@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
<graph-theory><co.combinatorics><board-games><combinatorial-game-theory>
The Dracula game
Tomek Tarczynski
# The Dracula game

(Asked by: username_0 on 2011-04-16)

**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.

**Tags:** graph-theory, co.combinatorics, board-games, combinatorial-game-theory
> **Comments:**
> **username_1**: This game is more widely known as Scotland Yard (or Police 07 in Hungary).  
> **username_2**: You may find some information under the name "pursuit-evasion game", see http://en.wikipedia.org/wiki/Pursuit-evasion  
> **username_0**: @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.  

---

## 3 answers

### Answer by username_3 on 2014-06-30. Score: 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 by username_5 on 2014-07-01. Score: 0

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 by username_4 on 2014-06-30. Score: -1

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](http://www.newton.ac.uk/programmes/LAA/seminars/2006050411001.pdf) lecture notes.


---

