Searching for a visible, lazy fugitive

David Richerby, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


Graph searching problems are described as games played on graphs, between a set of cops and a fugitive. Variants of the game restrict the abilities of the cops and the fugitive and the corresponding search numbers (the least number of cops that have a winning strategy) are related to several well-known parameters in graph theory. We study the case where the fugitive is visible (the cops' strategy can take into account his current position) and lazy (he moves only when the cops move to his position). Our results are stated and proven in a general setting where the fugitive's speed (i.e., the lengths of paths he can move along) can be unbounded or bounded by some constant. We give a min-max characterization of the corresponding parameters, which we show to be computable in polynomial time for fugitives with unbounded speed and speed at most 3 and to be nondeterministic polynomial-time complete (NP-complete) for all other finite speeds. This is in contrast to the other standard versions of the game, where the parameters corresponding to fugitives with unbounded speed are NP-complete. Several consequences of our results are also discussed.

Original languageEnglish (US)
Pages (from-to)497-513
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Issue number2
StatePublished - 2011


  • Graph searching
  • Obstructions
  • Pursuit evasion games

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Searching for a visible, lazy fugitive'. Together they form a unique fingerprint.

Cite this