# Fugitive-search games on graphs and related parameters

Nick D. Dendris, Lefteris M. Kirousis, Dimitris M. Thilikos

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

## Abstract

The goal of a fugitive-search game on a graph is to trap a fugitive that hides on the vertices of the graph by systematically placing searchers on the vertices. The fugitive is assumed to have complete knowledge of the graph and of the searchers' moves, but is restricted to move only along paths whose vertices are not guarded by searchers. The search number of the graph is the least number of searchers necessary to trap the fugitive. Variants of the fugitive-search game have been related to important graph parameters like treewidth and pathwidth. In this paper, we introduce a class of fugitive-search games where the searchers do not see the fugitive and the fugitive can only move just before a searcher is placed on the vertex it occupies. Letting the fugitive's speed (i.e. the maximum number of edges the fugitive can traverse at a single move) vary, we get different games. We show that if the speed of the fugitive is unbounded then the search number minus 1 is equal to the treewidth of the graph, while if the speed is 1 then the search number minus 1 is equal to the width, a polynomially computable graph parameter. We also show that in the above two cases, the search number remains the same even if we consider only these search strategies that at every step further restrict the fugitive's possible resorts (this monotonicity phenomenon is usually expressed as: “recontamination does not help”). Finally, we show that for any graph, if the length of any chordless cycle is bounded by a constant s (s≥3), then the treewidth of the graph plus 1 is equal to the search number for fugitive speed s−2.

Original language English (US) Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer Springer Verlag 331-342 12 3540590714, 9783540590712 https://doi.org/10.1007/3-540-59071-4_59 Published - 1995 20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994 - Herrsching, GermanyDuration: Jun 16 1994 → Jun 18 1994

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 903 0302-9743 1611-3349

### Conference

Conference 20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994 Germany Herrsching 6/16/94 → 6/18/94

## ASJC Scopus subject areas

• Theoretical Computer Science
• General Computer Science

## Fingerprint

Dive into the research topics of 'Fugitive-search games on graphs and related parameters'. Together they form a unique fingerprint.