论文标题
与敏捷且可见的逃犯的混合搜索游戏是单调的
The mixed search game against an agile and visible fugitive is monotone
论文作者
论文摘要
我们认为与敏捷且可见的逃犯的混合搜索游戏。这是图表上经典的逃亡搜索游戏的变体，可以将搜索器放置在（或从边缘滑动）或滑动边缘。此外，逃亡者位于图表的边缘上，可以随时沿着无护理路径移动。与图形$ g $的敏捷且可见的逃亡者（表示为$ avms（g）$）的混合搜索号是在此图表搜索变体中捕获到逃犯所需的最小搜索者数量。我们的主要结果是，这种图形搜索变体是单调的，因为如果我们将搜索策略限制在不允许逃犯可以访问已经清洁的边缘的搜索策略的情况下，成功的搜索策略所需的搜索者数量不会增加。这意味着可以通过多项式认证与敏捷和可见的逃犯的混合搜索策略，因此，确定的问题，给定图形$ g $和整数$ k，$ avms（g）\ leq k $是否在NP中。我们的证明是基于引入紧密烤的概念，这是对相应搜索参数的阻碍。我们的结果表明，对于图$ g $，$ avms（g）$等于$ g $的笛卡尔树产品编号，这是$ g $的最低$ g $，$ g $是树木的笛卡尔产品的少数，而在$ k $ totices上是$ k $ to的clique。
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.
