Single step graph search problem

Abstract A variation of the graph search problem is presented. The assumption is that each edge can be searched by any searcher in a single step and the fugitive can move with unbounded speed. The problem is to search a graph in a single step such that no fugitive can hide between the searchers. A sufficient and necessary condition is presented for a graph G = ( V , E ) to be single step searchable with ⫫; E ⫫ searchers. If ⫫ E ⫫ searchers are not enough, it can be shown that to determine the minimum number of extra searchers needed is intractable. An O(⫫ E ⫫) algorithm to single step search an interval graph of ⫫ E ⫫ edges with the minimum number of extra searchers is also presented.