Non-deterministic graph searching in trees

Non-deterministic graph searching was introduced by Fomin et al. to provide a unified approach for pathwidth, treewidth, and their interpretations in terms of graph searching games. Given q≥0, the q-limited search number, s_q(G), of a graph G is the smallest number of searchers required to capture an invisible fugitive in G, when the searchers are allowed to know the position of the fugitive at most q times. The search parameter s₀(G) corresponds to the pathwidth of a graph G, and s_∞(G) to its treewidth. Determining s_q(G) is NP-complete for any fixed q≥0 in general graphs and s₀(T) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q>0. We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rs_q and is shown to be equal to the non-deterministic graph searching parameter s_q for q=0, 1, and at most twice s_q for any q≥2 (for any graph G). Our main result is a polynomial time algorithm that computes rs_q(T) for any tree T and any q≥0. This provides a 2-approximation of s_q(T) for any tree T, and shows that the decision problem associated to s₁ is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest.