We consider the mixed search game against an agile and visible fugitive. This is the variant of the classic fugitive search game on graphs where searchers may be placed to (or removed from) the vertices or slide along edges. Moreover, the fugitive resides on the edges of the graph and can move at any time along unguarded paths. The mixed search number against an agile and visible fugitive of a graph $G$, denoted $avms(G)$, is the minimum number of searchers required to capture to fugitive in this graph searching variant. Our main result is that this graph searching variant is monotone in the sense that the number of searchers required for a successful search strategy does not increase if we restrict the search strategies to those that do not permit the fugitive to visit an already clean edge. This means that mixed search strategies against an agile and visible fugitive can be polynomially certified, and therefore that the problem of deciding, given a graph $G$ and an integer $k,$ whether $avms(G)\leq k$ is in NP. Our proof is based on the introduction of the notion of tight bramble, that serves as an obstruction for the corresponding search parameter. Our results imply that for a graph $G$, $avms(G)$ is equal to the Cartesian tree product number of $G$ that is the minimum $k$ for which $G$ is a minor of the Cartesian product of a tree and a clique on $k$ vertices.
翻译:我们考虑对一个敏捷可见的逃犯的混合搜索游戏。 这是在图表上经典逃犯搜索游戏的变体, 搜索者可以被放置到( 或从) 脊椎或沿边缘滑动。 此外, 逃犯住在图形边缘, 并且可以随时沿着未加保护的路径移动。 与一个灵活可见的逃犯混在一起的搜索数字, 这个G$, 意指美元, 是在这个图形搜索变体中捕获逃犯所需的最低搜索者人数。 我们的主要结果是, 这个图形搜索变体是单调的, 因为如果我们把搜索策略限制在图形边缘, 使逃犯无法访问已经干净的边缘, 则成功搜索战略的数量不会增加。 这意味着, 与一个灵活可见的逃犯混杂的搜索策略, 可以是多式的认证, 因此, 以G$为单位的图形为最小的搜索者数量, 美元( G)\ k$是否是 NP。 我们根据的最小的搜索结果, 一个暗色的G$, 这个卡路的搜索结果等于G$。