TL;DR
This paper tackles the "one-cop-moves" variant of the classic Cops and Robbers game on planar graphs. The authors construct a specific planar graph where a single robber can evade capture indefinitely by three cops, demonstrating that the upper bound of three cops sufficient for capture in the standard game does not hold for this variant.
What Problem Does This Paper Address?
The classic Cops and Robbers game involves multiple cops trying to capture a single robber on a graph. A key result by Aigner and Fromme states that for any connected planar graph, three cops are always sufficient to guarantee a capture. However, a variant of the game, called the "one-cop-moves" game (or lazy cops and robbers), where only one cop can move per turn, has a different dynamic. It was an open question whether the three-cop upper bound still held for this variant on planar graphs. This paper addresses this by constructing a planar graph that specifically challenges the three-cop sufficiency, showing that the one-cop-moves cop number can exceed three.
Methods
The core of the paper is the construction of a complex planar graph, denoted as 'D', designed to facilitate the robber's evasion. This graph is built upon a dodecahedron, with each pentagonal face intricately subdivided into layers of smaller pentagons and hexagons. The construction aims to create "safe zones" within these faces and intricate paths between them. The proof of the robber's winning strategy relies on detailed case analysis of cop positions and a series of lemmas that establish bounds on distances and movement capabilities within the constructed graph. The strategy involves the robber moving to the center of faces, using the limited cop movement to her advantage, and strategically oscillating or moving between faces to maintain distance.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The "one-cop-moves" variant is fundamentally different: The restriction of only one cop moving per turn significantly alters the game's dynamics, breaking established bounds from the classic game.
- Graph construction is key: The paper's main contribution is a meticulously designed planar graph that exploits the one-cop-moves rule to create evasion opportunities. The complexity of the graph's internal structure (layers, spokes, etc.) is crucial for the robber's strategy.
- Robber's strategy relies on exploiting limited cop movement: The robber's success hinges on the fact that while she can move freely within a face, the cops' inability to coordinate their moves allows her to exploit gaps and maintain distance.
- Distance and path analysis is paramount: The proof relies heavily on precise calculations of distances between the robber and cops, and the lengths of various paths within the constructed graph.
Key Results
The paper proves that there exists a connected planar graph 'D' for which the one-cop-moves cop number is at least 4. This directly answers a question posed by Sullivan, Townsend, and Werzanski and demonstrates that the upper bound of 3 cops, sufficient for capture in the standard game, does not generalize to the one-cop-moves game on planar graphs.
Limitations and Future Work
The paper focuses on constructing a graph that proves the existence of a planar graph with a one-cop-moves cop number greater than 3. It does not establish an upper bound for this cop number on planar graphs, though the authors conjecture that 4 cops might be sufficient for their constructed graph 'D'. The paper also notes that applying existing characterizations of k-cop-win graphs to their constructed graph is computationally infeasible due to its large size. Future work could involve finding tighter bounds or exploring simpler graph constructions.
Summary updated