TY - GEN

T1 - Searching for a visible, lazy fugitive

AU - Richerby, David

AU - Thilikos, Dimitrios M.

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=58349099525&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58349099525&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-92248-3_31

DO - 10.1007/978-3-540-92248-3_31

M3 - Conference contribution

AN - SCOPUS:58349099525

SN - 3540922474

SN - 9783540922476

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 348

EP - 359

BT - Graph-Theoretic Concepts in Computer Science - 34th International Workshop, WG 2008, Revised Papers

T2 - 34th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2008

Y2 - 30 June 2008 through 2 July 2008

ER -