Some Results on Non-deterministic Graph Searching in Trees

Description

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_0(G) corresponds to the pathwidth of a graph G, and s_{\infty}(G) to its treewidth. Determining s_q(G) is NP-complete for any fixed q>=0 in general graphs and s_0(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 that we call restricted non-deterministic. The corresponding parameter is denoted by rs_q and is shown to be equal to s_q for q=0,1, and at most twice s_q for any q>=2 (for any graph G). Our main result is the design of 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_1 is polynomial in the class of trees. Our proofs are based on a new decomposition technique for trees which might be of independent interest. We also prove that the number of queries required to search a tree with two searchers can be computed in linear time. Tight upper bounds on the minimum number of queries for an arbitrary fixed number of searchers are also provided.

Additional details