journal article Apr 30, 2025

Complexity Results for a Cops and Robber Game on Directed Graphs

Networks Vol. 86 No. 2 pp. 144-156 · Wiley
View at Publisher Save 10.1002/net.22284
Abstract
ABSTRACTWe investigate a cops and robber game on directed graphs, where the robber moves along the arcs of the graph, whereas the cops can select any position at each time step. Our main focus is on the cop number: the minimum number of cops required to guarantee the capture of the robber. We prove that deciding whether the cop number of a digraph is equal to 1 is NP‐hard, whereas this is decidable in polynomial time for tournaments. Furthermore, we show that computing the cop number for general digraphs is fixed parameter tractable when parameterized by a generalization of vertex cover. However, for tournaments, tractability is achieved with respect to the minimum size of a feedback vertex set. Among our findings, we prove that the cop number of a digraph is equal to that of its reverse digraph, and we draw connections to the matrix mortality problem.
Topics

No keywords indexed for this article. Browse by subject →

References
36
[6]
An evasion game on a graph

John Haslegrave

Discrete Mathematics 10.1016/j.disc.2013.09.004
[7]
Gruslys V. "Catching a Mouse on a Tree" arXiv:1502.06591 (2015)
[8]
Dissaux T. (2023)
[9]
Quillot A. (1978)
[10]
Bonato A. (2020)
[16]
Berwanger D. (2006)
[18]
Obdržálek J. (2006) 10.1145/1109557.1109647
[21]
A tight lower bound for the capture time of the Cops and Robbers game

Sebastian Brandt, Yuval Emek, Jara Uitto et al.

Theoretical Computer Science 10.1016/j.tcs.2020.06.004
[23]
A.Amarilli H.Gahlawat andV.‐S.Vergelea “Private Communication ”2024.
[24]
Garey M. R. (1979)
[25]
Cygan M. (2015)
[29]
Huang J. "Which Digraphs Are Round?" Australasian Journal of Combinatorics (1999)
[31]
Lokshtanov D. "A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set" CoRR, Abs/1609.04347 (2016)
Metrics
2
Citations
36
References
Details
Published
Apr 30, 2025
Vol/Issue
86(2)
Pages
144-156
License
View
Cite This Article
Walid Ben‐Ameur, Alessandro Maddaloni (2025). Complexity Results for a Cops and Robber Game on Directed Graphs. Networks, 86(2), 144-156. https://doi.org/10.1002/net.22284
Related

You May Also Like

Complexity of vehicle routing and scheduling problems

J. K. Lenstra, A. H. G. Rinnooy Kan · 1981

938 citations

A generalized assignment heuristic for vehicle routing

Marshall L. Fisher, Ramchandran Jaikumar · 1981

736 citations

SNDlib 1.0—Survivable Network Design Library

S. Orlowski, R. Wessäly · 2009

691 citations

Total domination in graphs

E. J. Cockayne, R. M. Dawes · 1980

419 citations