Constrained Graph Searching on Trees

Megiddo et al. (1988) introduced the edge searching problem, which is to find the minimum number of searchers to capture the robber in the edge searching model. Dyer et al. (2008) introduced the fast searching problem that is to find the minimum number of searchers to capture the robber in the fast searching model. In this paper, we consider these two graph searching problems under some constraints. One constraint is that a subset of vertices, called start vertices, are initially occupied by searchers before we place additional searchers on the graph. Another constraint is that some of the searchers must end their search at certain vertices called halt vertices. We focus on trees with n vertices. Let k be the number of times to move searchers from start vertices. For the edge searching problem, we give an O(kn)-time algorithm for computing the edge search number of a tree that contains only start vertices or only halt vertices. For a tree that contains both start vertices and halt vertices, we present an O(n²)-time algorithm to compute the edge search number. We show that all these problems are monotonic. For the fast searching problem, we propose a linear-time algorithm for computing the fast search number of a tree that contains only start vertices or only halt vertices. For a tree with n vertices that contains s start vertices and h halt vertices, we give an O((s + h)n)-time algorithm to compute the fast search number. © 2023, Springer Nature Switzerland AG.