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≥0q≥0, the q  -limited search number, sq(G)sq(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 s0(G)s0(G) corresponds to the pathwidth of a graph G  , and s∞(G)s∞(G) to its treewidth. Determining sq(G)sq(G) is NP-complete for any fixed q≥0q≥0 in general graphs and s0(T)s0(T) can be computed in linear time in trees, however the complexity of the problem on trees has been unknown for any q>0q>0.We introduce a new variant of graph searching called restricted non-deterministic. The corresponding parameter is denoted by rsqrsq and is shown to be equal to the non-deterministic graph searching parameter sqsq for q=0,1q=0,1, and at most twice sqsq for any q≥2q≥2 (for any graph G).Our main result is a polynomial time algorithm that computes rsq(T)rsq(T) for any tree T   and any q≥0q≥0. This provides a 2-approximation of sq(T)sq(T) for any tree T  , and shows that the decision problem associated to s1s1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest.