Sheng-Lung Peng, Ming-Tat Ko, Chin-Wen Ho, Tsan-sheng Hsu and
Chuan-Yi Tang
In the graph searching problem, initially a graph with all edges contaminated is presented. We would like to obtain a state of the graph in which all edges are simultaneously clear by a sequence of moves using searchers. The objective is to achieve the desired state by using the least number of searchers. Two variations of the graph searching problem are considered in this paper. One is the edge searching, in which the clearing of an edge is accomplished by moving a searcher along the edge, and the other is the node searching, in which an edge is cleared by concurrently having searchers on both of its endpoints.
In this paper, we present a uniform approach to solve the above two graph searching problems on several classes of chordal graphs. For edge searching problem, we give an O(mn^2)-time algorithm on split graphs, an O(m+n) -time algorithm on interval graphs, and an O(mn^k)-time algorithm on k-starlike graphs (a generalization of split graphs), for a fixed k>= 2, where m and n are the numbers of edges and vertices in the input graph, respectively. There are no polynomial algorithms known previously for any of the above problems. As a by-product, we also show that the edge searching problem remains NP-complete on chordal graphs. For node searching problem, we give an O(mn^k)-time algorithm on k-starlike graphs for a fixed k. This result implies that the pathwidth problem on k-starlike graphs is also in this time bound which greatly improves the previous results.