Search code examples
algorithmgraph

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.

enter image description here

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 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:

enter image description here

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.


Solution

  • 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:

    enter image description here

    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.