Searching is not jumping

Lali Barrière, Pierre Fraigniaud, Nicola Santoro, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingChapter


This paper is concerned with the graph searching game: we are given a graph containing a fugitive (or lost) entity or item; the goal is to clear the edges of the graph, using searchers; an edge is clear if it cannot contain the searched entity, contaminated otherwise. The search number s(G) of a graph G is the smallest number of searchers required to "clear" G. A search strategy is monotone (m) if no recontamination ever occurs. It is connected (c) if the set of clear edges always forms a connected subgraph. It is internal (i) if the removal of searchers is not allowed (i.e., searchers can not jump but only move along the edges). The difficulty of the "connected" version and of the "monotone internal" version of the graph searching problem comes from the fact that none of these problems is minor closed for arbitrary graphs, as opposed to all known variants of graph searching. We prove that there is a unique chain of inequalities linking all the search numbers above. More precisely, for any graph G, s(G) = is(G) = ms(G) ≤ mis(G) ≤ cs(G) = ics(G) ≤ mcs(G) = mics(G). The first two inequalities can be strict. Motivated by the fact that connected graph searching and monotone internal graph searching are both minor closed in trees, we provide a complete characterization of the set of trees that can be cleared by a given number of searchers. In fact, we show that, in trees, there is exactly one obstruction for monotone internal search, as well as for connected search, and this obstruction is the same for the two problems. This allows us to prove that, for any tree T, mis(T) = cs(T) and cs(T) ≤ 2 s(T) - 2, using that ics(T) = mcs(T). This implies that there are only two different search numbers, and these search numbers differ by a factor of 2 at most.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsHans L. Bodlaender
PublisherSpringer Verlag
Number of pages12
ISBN (Electronic)9783540204527
StatePublished - 2003

Publication series

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Searching is not jumping'. Together they form a unique fingerprint.

Cite this