The Cop Number of the One-Cop-Moves Game on Planar Graphs.

Ziyuan Gao, Boting YangarXiv 2017 · OpenReview

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

Abstract

Cops and robbers is a vertex-pursuit game played on graphs. In the classical 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. If a cop eventually occupies the same vertex as the robber, then the cops win; the robber wins if she can indefinitely evade capture. Aigner and Frommer established that in every connected planar graph, three cops are sufficient to capture a single robber. In this paper, we consider a recently studied variant of the cops-and-robbers game, alternately called the one-active-cop game, one-cop-moves game or the lazy-cops-and-robbers game, where at most one cop can move during any round. We show that Aigner and Frommer's result does not generalise to this game variant by constructing a connected planar graph on which a robber can indefinitely evade three cops in the one-cop-moves game. This answers a question recently raised by Sullivan, Townsend and Werzanski.
BibTeX
@misc{gao2017cop,
  author = {Ziyuan Gao and Boting Yang},
  title = {{The Cop Number of the One-Cop-Moves Game on Planar Graphs.}},
  year = {2017},
  eprint = {1705.11184},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.11184},
}
Figure