Graph Searching and Related Problems

图搜索是图论中一个非常活跃的课题，涉及到很多图的参数。在典型的图搜索问题中，搜索者（或警察）希望捕获图上的一个或多个移动实体（或劫匪）。许多现实世界的问题都可以通过适当的图搜索问题来建模。一些例子包括：警察搜寻逃犯，搜救队搜寻失踪者，军队清除敌人区域，机器人在建筑物内搜寻爆炸装置，或计算机技术人员在计算机网络上搜寻病毒。我们对研究人们常用的搜索策略的计算问题特别感兴趣。******Cops and Robbers是文献中研究最多的图搜索模型之一。这是一款基于图形的顶点追踪游戏。在《Cops and Robbers》游戏中，一组警察和一名抢劫犯占据了图形的顶点，并沿着图形的边缘交替移动，彼此的位置信息都是完美的。如果一个警察最终占据了与抢劫犯相同的顶点，那么警察就赢了；如果强盗能无限期地逃脱追捕，他就赢了。******图为道路和网络等领域提供了自然模型。图搜索是解决这些领域问题的一种特别有用的方法，因为在考虑搜索数或cop数时可以使用图论的许多相关结果。在这个提议中，我们考虑图搜索和相关问题。我们提出的研究重点是“警察与强盗”游戏及其变体。我们将研究长期存在的开放问题，如Meyniel猜想和Schroeder猜想，它们为cop数提供了界。我们还将考虑在可见节点搜索问题和Cops and Robbers博弈的变体中搜索策略的计算，其中包括one-cop-moves博弈（也称为Lazy Cops and Robbers）和零可见性Cops and Robbers博弈。我们将设计算法和近似算法来计算保证捕获抢劫犯的搜索策略。与这个问题有关，产生了许多有趣的问题。例如，给定一个图表，抓获抢劫犯最少需要多少搜查者或警察？那么搜索图的最小步数是多少呢？这些问题对于搜索者数量有限的应用程序尤为重要。拟议的项目使用图论和算法设计领域的最先进工具来解决这些问题。我们的研究将提供新的算法和最终的软件，将有助于各种搜索应用程序。

Graph Searching is a very active topic in graph theory, which is related to many graph parameters. In a typical graph searching problem, searchers (or cops) want to capture one or more moving entities (or robbers) on a graph. Many real-world problems can be modeled by an appropriate graph searching problem. Some examples include: police officers searching for fugitives, a search-and-rescue team searching for a missing person, a military troop clearing an area of enemies, robots searching for explosive devices in a building, or computer technicians searching for a virus on a computer network. We are especially interested in investigating computational issues of search strategies that are commonly used by people. ******Cops and Robbers is one of the most studied models for graph searching problems in the literature. It is a vertex-pursuit game played on graphs. In the Cops and Robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph's edges with perfect information about each other's positions. The cops win if a cop eventually occupies the same vertex as the robber; the robber wins if he can indefinitely evade capture. ******Graphs provide natural models for domains such as roadways and networks. Graph searching is an especially useful way of solving problems in such domains because many relevant results from graph theory can be employed when considering the search number or cop number. In this proposal, we consider graph searching and related problems. Our proposed research focuses on the game of Cops and Robbers and its variants. We will investigate long-standing open problems such as Meyniel's conjecture and Schroeder's conjecture, which provide bounds for the cop number. We will also consider the computation of search strategies in the visible node search problem and variants of the Cops and Robbers game, which include the one-cop-moves game (also called Lazy Cops and Robbers) and the zero-visibility Cops and Robbers game. We will design algorithms and approximation algorithms for computing search strategies that are guaranteed to capture the robber. Many interesting questions arise with relation to this problem. For example, given a graph, what is the minimum number of searchers or cops required to catch the robber? And what is the minimum number of steps to search the graph? These questions are particularly important for applications where the number of searchers is limited. The proposed project addresses these questions using state-of-the-art tools from the areas of graph theory and algorithm design. Our research will provide new algorithms and eventually software that will assist in various search applications.