Some Results on Non-deterministic Graph Searching in Trees

Omid Amini 1 David Coudert 2 Nicolas Nisse 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal.inria.fr/inria-00174965
Contributor : David Coudert <>
Submitted on : Friday, October 11, 2013 - 2:30:58 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM
Long-term archiving on: Friday, April 7, 2017 - 8:58:36 AM

File

ACN--hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00174965, version 3

Citation

Omid Amini, David Coudert, Nicolas Nisse. Some Results on Non-deterministic Graph Searching in Trees. [Research Report] 2013, pp.27. ⟨inria-00174965v3⟩

Share

Metrics

Record views

784

Files downloads

292