Complexity Results for a Cops and Robber Game on Directed Graphs

Walid Ben‐Ameur; Alessandro Maddaloni

doi:10.1002/net.22284

journal article Apr 30, 2025

Complexity Results for a Cops and Robber Game on Directed Graphs

Walid Ben‐Ameur Alessandro Maddaloni

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

[1]

10.1002/net.22234

[2]

10.1016/j.dam.2022.12.008

[3]

10.1016/j.ejc.2015.08.002

[4]

10.37236/2296

[5]

10.1016/j.disc.2018.10.011

[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)

[11]

10.1006/jctb.1993.1027

[12]

10.1016/0020-0190(92)90234-m

[13]

10.1016/0012-365x(85)90046-9

[14]

10.1016/j.tcs.2008.02.040

[15]

10.1007/s00373-005-0627-y

[16]

Berwanger D. (2006)

[17]

10.20429/tag.2020.070108

[18]

Obdržálek J. (2006) 10.1145/1109557.1109647

[19]

10.1016/j.dam.2007.08.045

[20]

10.1016/j.disc.2008.04.004

[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

[22]

10.1016/j.disc.2018.05.025

[23]

A.Amarilli H.Gahlawat andV.‐S.Vergelea “Private Communication ”2024.

[24]

Garey M. R. (1979)

[25]

Cygan M. (2015)

[26]

10.1007/s10878-014-9753-x

[27]

10.1007/s10107-018-1255-7

[28]

10.1007/s00453-022-01004-z

[29]

Huang J. "Which Digraphs Are Round?" Australasian Journal of Combinatorics (1999)

[30]

10.1137/0201010

[31]

Lokshtanov D. "A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set" CoRR, Abs/1609.04347 (2016)

[32]

10.1016/j.jda.2009.08.001

[33]

10.1002/sapm1970491105

[34]

10.1137/19m1250893

[35]

10.1016/j.tcs.2009.07.049

[36]

10.1007/978-3-031-72621-7_8

Metrics

2

Citations

36

References

Details

Published: Apr 30, 2025
Vol/Issue: 86(2)
Pages: 144-156
License: View

Authors

W

Walid Ben‐Ameur

SAMOVAR Télécom SudParis, Institut Polytechnique de Paris Palaiseau France

A

Alessandro Maddaloni

SAMOVAR Télécom SudParis, Institut Polytechnique de Paris Palaiseau France

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

Complexity Results for a Cops and Robber Game on Directed Graphs

You May Also Like