There are pursuers and evaders in the vertices of a directed graph G with one component. Each vertex must have atleast one outgoing edge (can be a loop).
At each time t:
- The evaders must move along an edge to another vertex (may use loop)
- Each pursuer must check one vertex (it can be any vertex in G).
A vertex is considered contaminated at time t if an evader can be there without having been caught by the pursuers. A vertex v is decontaminated at time t if:
- A pursuer is checking v.
- All edges to v originate from vertices which were decontaminated at time t-1.
At time t=0 all vertices are contaminated. The goal is that all vertices are decontaminated. This translates to the evaders being guaranteed to be caught. A search strategy for k pursuers is a sequence of k-tuples referencing k vertices i.e. "check these k vertices at time t=0, then these k vertices at time t=1" and so on.
What is the minimum amount of pursuers needed to decontaminate all vertices in G?
What is the optimal (shortest sequence) search strategy given a graph G and k pursuers?
So, where can I find this problem definition or an equal one? Is this problem NP-complete and if it is, how can that be shown?