Graph Searching and Related Problems

点击翻译按钮获取中文摘要

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.