Graph searching in a crime wave

David Richerby, Dimitrios M. Thilikos

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


We define helicopter cop and robber games with multiple robbers, extending previous research, which only considered the pursuit of a single robber. Our model is defined for robbers that are visible (the cops know their position) and active (able to move at every turn) but is easily adapted to other common variants of the game. The game with many robbers is non-monotone: more cops are needed if their moves are restricted so as to monotonically decrease the space available to the robbers. Because the cops may decide their moves based on the robbers' current position, strategies in the game are interactive but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game captures a hierarchy of parameters between proper pathwidth and proper treewidth. We give a complete characterization of the parameter for trees and an upper bound for general graphs.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 33rd International Workshop, WG 2007, Revised Papers
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540748385, 9783540748380
StatePublished - 2007
Event33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007 - Dornburg, Germany
Duration: Jun 21 2007Jun 23 2007

Publication series

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


Conference33rd International Conference Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Graph searching in a crime wave'. Together they form a unique fingerprint.

Cite this