17
$\begingroup$

Consider a game of cops and robbers on a finite graph. The robber, for reasons left to the imagination, moves entirely randomly: at each step, he moves to a randomly chosen neighbour of his current vertex. The cop's job is to catch the robber as quickly as possible:

How do we find a strategy for the cop which minimizes the expected number of steps before she catches the robber?

If I'm reading this paper correctly, the minimum expected catch time is finite even if the graph is not cop-win. [Edit: as mentioned in the comments below, the cop and robber will never meet if they move at the same time and are in opposite parts of a bipartite graph. Provided this is not the case, I think the paper's argument can be modified to show that the expected catch time is finite. If the cop and robber take turns, there is no need for an additional assumption and the paper can be used directly. I'd be interested in either setup.] For example, chasing a robber around the cycle $C_n$ gives an expected catch time of $$\sum_{k=0}^\infty\ k\cdot\frac{\binom{k}{d/2}}{2^k},$$ where $d$ is the initial distance between the cop and the robber. (Since the cycle has so much symmetry, it can be shown that this strategy is the best possible.)

I'm curious as to whether, for instance, the usual optimal strategy in a cop-win graph is optimal in this sense. I'm also interested in some generalizations of this problem (by giving weights to various things). But I don't know whether the basic problem is open, trivial, or somewhere in between, so I'll ask the catch-all question:

What is known about this problem?

$\endgroup$
8
  • 3
    $\begingroup$ What's it mean for cop to catch robber? They land on the same vertex? So if they start an odd distance apart on an even cycle, cop can't ever catch robber? $\endgroup$ Mar 11, 2011 at 6:26
  • 1
    $\begingroup$ Presumably the drunken robber can also run right into the policeman. $\endgroup$ Mar 11, 2011 at 7:32
  • $\begingroup$ I think you're not reading the paper correctly. I think the paper is about the sleeping cop and the drunken robber. As Gerry says if they are both moving on an even cycle the drunken robber gets to go forever as long as they move synchronously and start on opposite parity sites and so the expected time is infinite. $\endgroup$ Mar 11, 2011 at 8:27
  • 3
    $\begingroup$ The question makes sense as stated. The cop is playing intelligently, while the robber plays randomly. On an $n$ cycle, if the cop always moves clockwise, and the robber choses randomly which way to move, the distance between the cop and robber will equal zero in finite time almost surely. The second part is a very good question: if the graph is copwin-- meaning there is a strategy for catching an intelligent robber-- is following this strategy the best way to catch a drunken robber? I have not read about this result in the literature, but I have only dabbled in this area. $\endgroup$ Mar 11, 2011 at 13:19
  • $\begingroup$ @Anthony Quas: If the cop doesn't move, then the expected time for the drunken robber to reach the cop would depend on $n$. That formula assumes the cop starts an even distance away and follows in that direction, so that it takes $d/2$ steps toward the cop to get caught, and $n$ does not matter. $\endgroup$ Mar 11, 2011 at 13:25

2 Answers 2

10
$\begingroup$

I think that I have an example where the optimal strategy for a random robber is different from the normal winning strategy.

Let me specify the graph first. We have 5 points A,B,C,D and E forming a cycle. So an edge connects A to B, and an edge connects B to C etc. points A and C are also connected by an edge. We also add a billion points connected to only D and a billion points connected to only E.

Now let me specify the position. The cop is on vertex A and the robber is on vertex D.

Now the winning strategy is for the cop to move to vertex B then If the robber moves to E then The cop moves to C and then if the robber moves back to D The cop moves to D and we are done. If then instead of moving to D the robber moves to one of the many points connected only to E the cop moves to A and now the robber must move to E and then the cop captures the robber there.

Now if the robber's moves are random The optimal strategy is for the cop to move to vertex C because the robber will with odds a billion to one move that the robber will move to one of the points adjacent only to D. Then the cop will move to D and in the next move the robber must move into D and and the cop will catch the robber after only two moves. Then if the robber moves to E the cop moves to A and again the odds are a billion to one that the robber will move to a point adjacent only to E and the cop would move To E and catch the robber. So the cop would alternate between A and C waiting for the robber to go to a point adjacent to only E or only D and this would generate and infinite series that sums to less than 3.

Now if the cop follows the normal strategy he will move to B then the robber will move to a vertex adjacent only to D and then the cop will move to C the robber will have to move to d and then the cop will move to C catching the robber in three moves. So here the winning strategy is different from the optimal winning strategy is different from the optimal random strategy.

$\endgroup$
3
  • $\begingroup$ Interesting! Well, you learn something new every day. I originally thought that this graph couldn't possibly be cop-win because of the $C_4$, but the "dismantlability" characterization of cop-win graphs relies on the robber being able to stay put. As you point out, the cop has a winning strategy on this graph when the robber is forced to move every turn. $\endgroup$ Mar 14, 2011 at 0:25
  • $\begingroup$ I see that your optimal strategy, along with the optimal strategy for cycles, has the cop always decreasing her distance with the robber (although you show that this isn't sufficient to describe the optimal strategy; the cop has to move to A, not D, if the robber moves to E). However, I think it's possible to construct examples where this isn't the case. $\endgroup$ Mar 14, 2011 at 0:35
  • $\begingroup$ Anyways, thanks! This problem seems to be really interesting and perhaps a little bit unpredictable (at least to me!). If nobody knows of any papers covering this problem, I might have to devote a big chunk of time to this once I'm done my thesis research. $\endgroup$ Mar 14, 2011 at 0:49
5
$\begingroup$

Here are some recent papers on the topic:

  1. Natasha Komarov, Peter Winkler, Capturing the Drunk Robber on a Graph
  2. Athanasios Kehagias, Paweł Prałat: Some remarks on cops and drunk robbers
  3. Athanasios Kehagias, Dieter Mitsche, Paweł Prałat: Cops and invisible robbers: The cost of drunkenness

There are also some related slides: here and here (by the OP).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.