Find an algorithm to win this battle against crime！

A crime committed in a city and the suspect starts to run away. A map of the city is given. At the moment, there are some police cars at some given places and they try to stop the suspect. The car of police and the suspect have a same maximum speed. The suspect can only pass a point if he reaches it earlier than any police car. There are several exits in the map, and the suspect evades if he reaches any of them. Find an algorithm allocating the police cars so that no path can the suspect take to evade.

For example, below is a possible city map.

White circle is where the suspect starts, black circles are police cars, and little squares are exits. In this situation, suspect can be stopped. A possible plan is开发者_C百科 police car A goes to A', B stays and C goes to C'.

---

An equivalent description of my problem could be:

A chemical factory (marked by the white circle) explodes and poisonous fluid starts to flow at each possible direction at speed v, and the rescue teams (marked by black circles) whose maximum speed is also v are trying to block it. The little squares are villagers they are protecting.

---

My Thoughts

If we have n police cars, a highly inefficient approach is to list all possible k-element subsets P of vertices such that:

a) k <= n;

b) Remove all vertices in P in the map will cause any exit unreachable to the suspect;

c) Remove any proper subset of P will let at least one exit reachable to the suspect.

Then we can easily determine if every vertex in P can be covered by a police no later than the suspect.

But how do I list all the possible Ps?

---

@Lior Kogan:

Look at this map:

If it is a turning game in which both sides knowing other's strategy, the police will win because he can just guard the side where the suspect go.

But in my problem, the police loses because he'll never know which side the suspect may choose.

---

Edit2: Based on your clarifications:

I couldn't find any research concerning the exact posed problem.

Another close subject is virus spread and inoculation in networks. Here are some papers:

• Inoculation strategies for victims of viruses and the sum-of-squares partition problem
• Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?
• Protecting Against Network Infections: A Game Theoretic Perspective

I think that the posed problem is very interesting. Though I believe it is NP-hard.

Sorry for being unable to help any further.

--

Edit1: Changed from Cops and Robbers game to Graph guarding game.

New answer:

This is a variant of the Graph Guarding game.

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the agents and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges.

See: Guard Games on Graphs and How to Guard a Graph?

In your variant, there are two differences:

• You are trying to guard more than one area
• Each guarded area is a single node

--

Original answer:

This is a variant of the well studied Cops and Robbers game.

The Cops and Robbers game is played on undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still an open question.

The problem of determining if k cops can capture a robber on an undirected graph, as well as the problem of computing the minimum number of cops that can catch a robber on a given graph were proven to be NP-hard.

Here are some resources:

• Chapter 6 of The Game of Cops and Robbers on Graphs
• On tractability of Cops and Robbers game
• Complexity of Cops and Robber Game
• Talks on GRASTA 2011 (see ch.3)

---

Now I have a clearer view of my problem. Although simpler than the Cops and Robbers Game or Graph Guarding game, it is nevertheless an NP-hard problem.

Two separate tasks this problem can actually be divided into:

Task a) Find a possible set of vertices that cuts the suspect unreachable to any exits.
Task b) Validate if this set of vertices can be all in-timely covered by police cars.

Now we are going to prove that Task a) is NP-complete.

First we consider when there is only one exit. Look at this simple map:

Assign False to a vertex if it is blocked by police and True if it's passable. We know that the suspect can evade if A & (B | D) & C == True. Now we clearly see that Task a) is equivalent to the famous NP-complete Boolean satisfiability problem.

If we have several exits, simply create several boolean expressions and connect them with AND(&).

Task b) is simply a bipartite graph matching problem, can be easily solved by Hungarian algorithm. It's time complexity is O(n^4).

So this whole problem is an NP-hard.