Exclusive graph searching vs. pathwidth

Euripides Markou 1 Nicolas Nisse 2 Stéphane Pérennes 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 : In Graph Searching, a team of searchers aims at capturing an invisible fugitive moving arbitrarily fast in a graph. Equivalently, the searchers try to clear a contaminated network. The problem is to compute the minimum number of searchers required to accomplish this task. Several variants of Graph Searching have been studied mainly because of their close relationship with the pathwidth of a graph. Blin et al. defined the Exclusive Graph Searching where searchers cannot " jump " and no node can be occupied by more than one searcher. In this paper, we study the complexity of this new variant. We show that the problem is NP-hard in planar graphs with maximum degree 3 and it can be solved in linear-time in the class of cographs. We also show that monotone Exclusive Graph Searching is NP-complete in split graphs where Pathwidth is known to be solvable in polynomial time. Moreover, we prove that monotone Exclusive Graph Searching is in P in a subclass of star-like graphs where Pathwidth is known to be NP-hard. Hence, the computational complexities of monotone Exclusive Graph Searching and Pathwidth cannot be compared. This is the first variant of Graph Searching for which such a difference is proved.
Type de document :
Article dans une revue
Information and Computation, Elsevier, 2017, 252, pp.243 - 260. <10.1016/j.ic.2016.11.007>
Liste complète des métadonnées


https://hal.inria.fr/hal-01534596
Contributeur : Nicolas Nisse <>
Soumis le : mercredi 7 juin 2017 - 18:24:42
Dernière modification le : jeudi 15 juin 2017 - 09:09:36

Fichier

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

Identifiants

Collections

Citation

Euripides Markou, Nicolas Nisse, Stéphane Pérennes. Exclusive graph searching vs. pathwidth. Information and Computation, Elsevier, 2017, 252, pp.243 - 260. <10.1016/j.ic.2016.11.007>. <hal-01534596>

Partager

Métriques

Consultations de
la notice

53

Téléchargements du document

20