Graph searching on some subclasses of chordal graphs

In the graph-searching problem, initially a graph with all the edges contam inated is presented. The objective is to obtain a state of the graph in whi ch all the edges are simultaneously cleared by using the least number of se archers. Two variations of the graph-searching problem are considered. One is edge searching, in which an edge is cleared by moving a searcher along t his edge, and the other is node searching, in which an edge is cleared by c oncurrently having searchers on both of its two endpoints. We present a uniform approach to solve the above two variations on several subclasses of chordal graphs. For edge searching, we give an O(mn(2))-time algorithm on split graphs (i.e., 1-starlike graphs), an O(m + n)-time algor ithm on interval graphs, and an O(mn(k))-time algorithm on k-starlike graph s (a generalization of split graphs), for a fixed k greater than or equal t o 2, where m and n are the numbers of edges and vertices in the input graph , respectively. There is no polynomial algorithm known previously for any o f the above problems. In addition, we also show that the edge-searching pro blem remains NP-complete on chordal graphs. For node searching, we give an O(mn(k))-time algorithm on k-starlike graphs for a fixed k greater than or equal to 1. This result implies that the pathwidth problem on k-starlike gr aphs can also be solved in this time bound which greatly improves the previ ous results.