Graph Searching Problem

• IIS members:
  • Tsan-sheng Hsu, IIS, Academia Sinica.
  • Ming-Tat Ko, IIS, Academia Sinica.
• Outside members:
  • Chin-Wen Ho, Department of Computer Science and Information Engineering, National Central University.
  • Sheng-Lung Peng, Department of Computer Science and Information Engineering, National Don Hwa University.
  • Chuan-Yi Tang, Department of Computer Science, National Tsing Hua University.

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.

• Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu, and Chuan-Yi Tang, ``Graph Searching on Some Subclasses of Chordal Graphs,'' Algorithmica, volume 27, pages 395--426, 2000. Extended abstract in Proc. 7th International Symposium on Algorithms and Computation (ISAAC), Springer-Verlag LNCS #1178, pages 156--165, 1996, under the title ``Graph Searching on Chordal Graphs.''
  • In this paper, we use a uniform high-level approach to solve the edge and node searching problems on several special subclasses of chordal graphs. As a result, we have derived polynomial-time algorithms on split graphs, interval graphs and $k$-starlike graphs.
• Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and Chuan-Yi Tang, "Edge and Node Searching Problems on Trees," Theoretical Computer Science, volume 240, number 2, pages 429--446, 2000. Extended abstract in Proc. 3rd International Computing and Combinatorics Conf. (COCOON), Springer-Verlag LNCS #1276, pages 284--293, 1997.
  • Though the above two searching problems appear to be similar, different techniques have been devised to solve these two problems. In this paper, we present a linear-time transformation to relate these two version of searching together when the input graph is a tree. We prove that if an optimal node searching strategy is known, then an optimal edge searching can be obtained in linear time.
• Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, and Chuan-Yi Tang, "A Linear-time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree," Proc. 4th International Computing and Combinatorics Conf. (COCOON), Springer-Verlag LNCS# 1449, pages 279--288, 1998.
  • In this paper, we present a linear-time algorithm to solve the node searching problem on trees. Thus combining our previous result, we have also solved the edge searching problem on trees.