  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.
