Cops vs Invisible Robber

Cops vs Invisible Robber is a variation on the normal cops and robber game, but it is played with partial information. In this game, the rules are as follows:

• The cops and robber take turns moving
• They can only move to vertices adjacent to their current position
• The robber knows where the cop is
• The cop does not know where the robber is

Characterization of Cop Win Graphs

So, in this game, how do we know if a graph is cop-win? We can use the ideas presented in the Hunter vs Mole variation to find out. In Hunter vs Mole, the hunter does not know where the mole is, but the mole knows where he is. Graphs were hunter-win in Hunter vs. Mole, if they were a lobster.

Just a reminder:

A lobster is a tree containing a path P such that all vertices are within distance 2 of P.  

We can use a very similar idea to find that in Cops vs. Invisible Robber:

A graph is cop-win if G is a tree containing a path P such that all vertices are within distance 1 of P.

Let’s take a look at this example:

Just like in Hunter vs. Mole, the cop can catch the robber in this graph in optimal time if he starts on one end of path P.

Remember the robber is trying to avoid capture, so let’s place him at the other end of the path.

However, the cop doesn’t know where he is (since he's invisible), so she’ll have to search every vertex to make sure the robber gets caught. That means she’ll need to visit every branch coming off of the main path, and then come back to path P before continuing on. This game would go like this until the robber was caught.

Round 1:

Round 2:

Round 3:

Round 4:

Round 5:

Round 6:

Round 7:

 

Round 8:

Some of you might be asking why the robber can’t just switch to the other side of the path while the cop is down one of the branches. However, you have to remember that unlike Hunter vs. Mole, the cop and the robber do not move simultaneously.  If the cop were down a branch, and the robber moved to the junction of the path and the branch, then on her next move, the cop would move back to the path and catch the robber.

Initial Situation:

Cop Move:

Robber Move:

Cop Move, on which the robber is caught:

This is why, for any tree graph G with path P such that all vertices are within distance 1 of P, G is cop-win.

What about capture time?

The optimal strategy for the cop, as already discussed, is to start at one end of P, and move her way down the path, stopping at every branch to check if the robber is there. This means that for a cop-win graph of this nature, capt(G) = (n-1) + 2(number of branches), where n is the number of vertices in the path P.

This equation comes from the fact that the cop must traverse each edge on the path P once (n-1 edges), and each branch edge twice (2* number of branches).

What about multiple cops?

What can you say about cop-win graphs with multiple cops? It turns out that we can generalize the definition of a cop-win graph above to find our answer.

Trees containing a path P such that all vertices are within distance k of P, are cop-win with k cops.

So, according to this assumption, how many cops do you need to catch the invisible robber on these graphs? (We’ll try these examples in class)

                         

Further Research:

With the addition of probability, it turns out you can make any connected graph G with an invisible robber cop-win. This is according to the following theorem:

Suppose that c(G) cops perform a random walk on a connected graph G, starting from any initial position, and that the robber is adversarial (wants to avoid capture). Then E(T) < infinity.

Basically, if you have the necessary number of cops to capture the robber (ie it’s a cop-win graph with c(G) cops in normal cops and robbers), then even when you don’t know where the robber is, eventually you can find him if you walk around randomly. I will further explain this with the 3-cycle graph in class.

This lets us know two things about Cops vs. Invisible Robber:

1. The cop number of a graph is the same in the visible and invisible CR game (but only if you move randomly)
2. Generally, the capture time of Cops vs. Invisible Robber will be larger than the visible version

Conclusions:

While there is much less known about Cops vs. Invisible Robber, it is clear that certain ideas from other Cops and Robber variations such as Hunter vs. Mole can be helpful in determining information about this variation. Using ideas from Hunter vs. Mole, we found what kinds of graphs are cop-win in Cops vs. Invisible Robber, and we were also able to say something about the cop-number of certain graphs when the robber is invisible. With the introduction of probability, we could show that the cop number of graphs with an invisible robber is the same as the cop number of that graph with a visible robber, even though the expected capture time increases. All in all, even with partial information, there are sometimes ways for the cops to win and capture our invisible robber.

Citations:

Kehagias, Athanasios, Dieter Mitsche, and Paweł Prałat. "Cops and Invisible Robbers: The Cost of Drunkenness." Theoretical Computer Science 481 (2013): 100-20. Web.