Searching for a visible, lazy fugitive

David Richerby, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 fugitivess with unbounded speed and speed at most 3 and to be 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)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 34th International Workshop, WG 2008, Revised Papers
Number of pages12
StatePublished - 2008
Event34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008 - Durham, United Kingdom
Duration: Jun 30 2008Jul 2 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5344 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this