This paper concerns itself with the following problem: one has a graph and somewhere in the graph there is a “robber” who is invisible to the cops. The cops are to be placed on the graph and can move between the vertices of the graph. Similarly, the robber can also move between vertices. The goal is to determine the minimum number of cops and a strategy that will ensure that at some point a cop will be on the same vertex as the robber. The cops and the robber alternate turns taking their moves. The minimum number of cops is known to be essentially the path-width of the graph. It is called the zero-visibility cop number of the graph.

The authors consider the case where the graph is a tree and present an algorithm that computes the zero-visibility cop number of any tree in linear time. The algorithm is presented in pseudocode form. In the other direction, the authors show that the corresponding problem is NP-complete on a non-trivial class of graphs.

The authors view the game as an exercise in graph cleaning where the dirty vertices are those that could contain the robber. The paper gives full details of the proofs and is essentially self-contained. The authors provide a reference for other material on the subject of zero-visibility cops and robbers.