Graph Searching Problem

Participants, Overview, Selected results.



The graph searching problem is a graph-theoretical game played on an undirected graph considered as a system of tunnels in which all the tunnels are initially contaminated by a gas. There are three kinds of moves in edge searching: (1) placing a searcher on a vertex; (2) removing a searcher from a vertex; and (3) clear an edge by either (3.1) moving a searcher from one vertex to another along an edge or (3.2) placing two searchers on the two endpoints of the edge. A cleared edge may be recontaminated once there is a path without any searchers connecting the edge with a contaminated one. The goal of this game is to discover a sequence of moves, called strategy , clear the graph with the least number of searchers. The graph searching problem is not only interesting theoretically, but also have applications on combinatorial problems including the interval thickness, the pathwidth and the vertex separation number of a graph. There are three versions of this problem depending on the actions allowed to be used in (3). Searching allowing only (3.1) is called edge searching , while allowing only (3.2) is called node searching . In the past, many isolated, but active researches has been performed on different versions of searching on different classes of graphs. The results in edge searching normally cannot be used in node searching, and vice versa. We have devised a uniform approach in solving the two versions of the graph searching problem.

Selected results

Created by Tsan-sheng Hsu, last updated April 17, 2001.