Computational complexity of the police officer patrol problem on weighted digraphs
Abstract
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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.2.10
References
Akoudad, K., and Jawab, F. : Recent survey on bases routing problems: CPP, RPP and CARP, International Journal of Engineering Research & Technology, Vol.2, pp.3652–3668(2013).
Cook, S.A.: The complexity of theorem-proving procedures, STOC ’71, Proceedings of the third annual ACM symposium on Theory of computing, pp.151–158, DOI: 10.1145/800157.805047 (1971).
Edmonds, J. and Johnson, E.L.: Matching, Euler Tours and the Chinese Postman, Math. Programming 5, 1, 88–124, DOI: 10.1007/BF01580113 (1973).
Garey, M.R. and Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete, SIAM Journal on Applied Mathematics, 32, 4, pp.826–834, DOI: 10.1137/0132071 (1977).
Karp, R.M.: Reducibility among combinatorial problems, Miller, R.E and Thatcher, J.W. (Eds.), Complexity of Computer Computations, pp.85–103, Plenum Press, DOI: 10.1007/978-1-4684-2001-2_9 (1972).
Lenstra, J.K. and Rinnooy-Kan, A.H.G: On general routing problems, Networks, 6, 273-–280, DOI: 10.1002/net.3230060305 (1976).
Lenstra, J.K. and Rinnooy-Kan, A.H.G.: Complexity of vehicle routing and scheduling problems, Networks 11, 221-–227, DOI: 10.1002/net.3230110211 (1981).
Mei-Ko, K.: Graphic Programming Using Odd or Even Points, Chinese Math., 1, 237–277 (1962).
Papadimitriou, C.H.: On the Complexity of Edge Traversing, J. Assoc. Comput. Mach. 23, 3, 544–554, DOI: 10.1145/321958.321974 (1976).
Sökmen, Ö. Ç., Emeç, Ş., Yilmaz, M. and Akkaya, G. : An overview of Chinese postman problem, 3rd International Conference on Advanced Engineering Technologies, Vol.10, (2019).
Tohyama, H. and Adachi, A.: Complexity of a Restricted Chinese Postman Problem, Trans. IPS. Japan, 37, 11, 1886–1896 (1996).
Tohyama, H. and Tomisawa, M.: Complexity of the Police Officer Patrol Problem, Journal of Information Processing, Vol.30, pp.307–314, DOI: 10.2197/ipsjjip.30.307 (Apr. 2022).
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.