Recontamination Does Not Help to Search a Graph

Andrea S. LaPaugh

Research output: Contribution to journalArticlepeer-review

210 Scopus citations


This paper is concerned with a game on graphs called graph searching. The object of this game is to clear all edges of a contaminated graph. Clearing is achieved by moving searchers, a kind of token, along the edges of the graph according to clearing rules. Certain search strategies cause edges that have been cleared to become contaminated again. Megiddo et al. [9] conjectured that every graph can be searched using a minimum number of searchers without this recontamination occurring, that is, without clearing any edge twice. In this paper, this conjecture is proved. This places the graph-searching problem in NP, completing the proof by Megiddo et al. that the graph-searching problem is NP-complete. Furthermore, by eliminating the need to consider recontamination, this result simplifies the analysis of searcher requirements with respect to other properties of graphs.

Original languageEnglish (US)
Pages (from-to)224-245
Number of pages22
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Jan 4 1993

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • NP-completeness
  • graph searching
  • pursuit and evasion


Dive into the research topics of 'Recontamination Does Not Help to Search a Graph'. Together they form a unique fingerprint.

Cite this