Graph Searching and Related Problems

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

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.