Searching by Heterogeneous Agents
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917573313953792 |
|---|---|
| author | Dereniowski, Dariusz Kuszner, Łukasz Ostrowski, Robert |
| author_facet | Dereniowski, Dariusz Kuszner, Łukasz Ostrowski, Robert |
| contents | In this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs: once a search strategy initially assigns labels to the searchers, each searcher can be only present on an edge of its own label. We prove that this problem is not monotone even for trees and we give instances in which the number of recontamination events is asymptotically quadratic in the tree size. Other negative results regard the NP-completeness of the monotone, and NP-hardness of an arbitrary (i.e., non-monotone) heterogeneous search in trees. These properties show that this problem behaves very differently from the classical edge search. On the other hand, if all edges of a particular label form a (connected) subtree of the input tree, then we show that optimal heterogeneous search strategy can be computed efficiently. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_02609 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Searching by Heterogeneous Agents Dereniowski, Dariusz Kuszner, Łukasz Ostrowski, Robert Discrete Mathematics Combinatorics 68R10, 68W05 G.2.2 In this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs: once a search strategy initially assigns labels to the searchers, each searcher can be only present on an edge of its own label. We prove that this problem is not monotone even for trees and we give instances in which the number of recontamination events is asymptotically quadratic in the tree size. Other negative results regard the NP-completeness of the monotone, and NP-hardness of an arbitrary (i.e., non-monotone) heterogeneous search in trees. These properties show that this problem behaves very differently from the classical edge search. On the other hand, if all edges of a particular label form a (connected) subtree of the input tree, then we show that optimal heterogeneous search strategy can be computed efficiently. |
| title | Searching by Heterogeneous Agents |
| topic | Discrete Mathematics Combinatorics 68R10, 68W05 G.2.2 |
| url | https://arxiv.org/abs/2105.02609 |