Graph searching on some subclasses of chordal graphs (Q1578423)

Graph searching is the problem of cleaning the edges of a graph by a minimum number of searchers. An edge is cleaned by having searchers on both endpoints at the same time (node search) or by moving a searcher along this edge (edge search). Lots of equivalent problems are known, for instance, one plus the pathwidth of a graph equals its node search number [\textit{N. Robertson} and \textit{P. D. Seymour}, J.\ Comb.\ Theory, Ser.\ B 35, 39-61 (1983; Zbl 0521.05062)], and edge search number and cutwidth are identical for every graph of maximum degree three [\textit{F. Makedon} and \textit{I. H. Sudborough}, Discrete Appl.\ Math.\ 23, No.\ 3, 243-265 (1989; Zbl 0715.05012)]. A starlike graph is a chordal graph obtained from a split graph by blowing up the vertices in the independent set to clique modules. Node search remains NP-complete for starlike graphs [see \textit{J. Gustedt}, Discrete Appl.\ Math.\ 45, No.\ 3, 233-248 (1993; Zbl 0798.68134)], but can be solved in time \(O(mn^k)\) on \(k\)-starlike graphs (all the clique modules have size \(k\)). Edge search is NP-complete for chordal graphs but is solvable in linear time on interval graphs, in time \(O(mn^2)\) on split graphs and in time \(O(mn^k)\) on \(k\)-starlike graphs for \(k \geq 2\).