Computational complexity of the police officer patrol problem on weighted digraphs

A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph and can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. Given a graph G and a natural number k , the vertex cover problem is the problem of deciding whether there exists a vertex cover in G of size at most k . The vertex cover problem is one of Karp’s 21 NP -complete problems. Recently, we introduced an edge routing problem that a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. We showed that the problem of deciding whether there exists a patrol route for a given mixed graph in which each edge is either traversed exactly once or confirmed visually is NP -complete. In this paper, we show that the police officer patrol problem remains NP -complete even if given graphs are weighted digraphs.