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 , 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 ∞ (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 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 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.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 580, pp.101-121. 〈10.1016/j.tcs.2015.02.038〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01132032
Contributeur : David Coudert <>
Soumis le : lundi 16 mars 2015 - 15:31:20
Dernière modification le : jeudi 20 juillet 2017 - 09:28:32
Document(s) archivé(s) le : dimanche 13 septembre 2015 - 22:20:22

Fichier

ACN15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Omid Amini, David Coudert, Nicolas Nisse. Non-deterministic graph searching in trees. Journal of Theoretical Computer Science (TCS), Elsevier, 2015, 580, pp.101-121. 〈10.1016/j.tcs.2015.02.038〉. 〈hal-01132032〉

Partager

Métriques

Consultations de
la notice

212

Téléchargements du document

90