Chasing robbers on random geometric graphs - An alternative approach

Noga Alon, Pawel Pralat

TL;DR

This paper tackles the classic "cops and robbers" pursuit game on random geometric graphs. The authors introduce a novel, simpler approach to prove that with high probability, a single cop can capture a robber on these graphs when the connectivity is sufficiently high, and they derive a tight bound on the capture time.

What Problem Does This Paper Address?

The "cops and robbers" game is a well-studied problem in graph theory where a team of cops tries to capture a single robber on the vertices of a graph. The minimum number of cops required to guarantee a win is called the "cop number" of the graph. A major open question is Meyniel's conjecture, which posits that the cop number of any $n$-vertex connected graph is $O(\sqrt{n})$. While this conjecture is believed to hold for many classes of graphs, understanding the cop number on random graphs is crucial for exploring its limits. This paper focuses on random geometric graphs, denoted $G_d(n,r)$, where $n$ vertices are randomly placed in a $d$-dimensional unit cube, and edges connect vertices within a distance $r$. Specifically, the authors investigate the cop number of these graphs, aiming to provide a new, more accessible proof for a known result and extend it to higher dimensions.

Methods

The paper presents a new strategy for the cop player in the continuous version of the game (where vertices are points in a unit square and edges connect points within distance $r$). The cop starts at the center and, after each robber move, moves towards the robber along the line connecting them. Crucially, the cop ensures their distance from the center increases by a significant amount in each step, guaranteeing capture within $O(1/r^2)$ moves. This strategy is then adapted to the discrete random geometric graph setting. Instead of moving to an exact point, the cop chooses a vertex within a specially constructed "cone" (a geometric region designed to contain a vertex with high probability). This cone is defined such that any vertex within it is sufficiently close to the desired continuous position, allowing the cop to maintain the winning strategy. The proof relies on probabilistic arguments to show that these cones are likely to contain vertices in the random graph.

Datasets

Not discussed in the paper. The paper deals with theoretical graph properties and random graph models, not empirical datasets.

Key Insights and Ideas

  • A Simpler Continuous Strategy: The paper offers a more intuitive and direct winning strategy for the cop in the continuous version of the game, which forms the foundation for the discrete case.
  • Geometric Regions for Discrete Movement: The ingenious use of "cones" (or triangles in 2D) to guide the cop's movement in the discrete graph is a key innovation. These regions are designed to guarantee the presence of a vertex with high probability.
  • Tight Capture Time Bound: The method yields a tight $O(1/r^2)$ upper bound for the capture time, which is shown to be asymptotically tight from the robber's perspective as well.
  • Generalization to Higher Dimensions: The approach is shown to be generalizable to $d$-dimensional random geometric graphs, providing a unified result.

Key Results

  • Theorem 2.1: For $d=2$, if $r^5 > C_2 \log n$ for some constant $C_2$, then the cop number of $G_2(n,r)$ is 1 with high probability (asymptotically almost surely).
  • Theorem 2.2: For any fixed $d > 1$, if $r^{3d-1} > C_d \log n$ for some constant $C_d$, then the cop number of $G_d(n,r)$ is 1 with high probability.
  • Capture Time: In both cases, the capture time is shown to be $\Theta(1/r^2)$ with high probability.

Limitations and Future Work

The authors explicitly state they make no attempt to optimize the absolute constants in their arguments, aiming for simplicity. While the paper provides a new proof for a known result and extends it to higher dimensions, it doesn't resolve Meyniel's conjecture for general graphs. Future work could focus on optimizing these constants or exploring the cop number for different regimes of $r$ in random geometric graphs. The robber's strategy for escaping is also discussed, highlighting the tightness of the derived capture time.

Summary updated

Abstract

We study the vertex pursuit game of \emph{Cops and Robbers}, in which cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph $G$ is called the cop number of $G$. We focus on $G_{d}(n,r)$, a random geometric graph in which $n$ vertices are chosen uniformly at random and independently from $[0,1]^d$, and two vertices are adjacent if the Euclidean distance between them is at most $r$. The main result is that if $r^{3d-1}>c_d \frac{\log n}{n}$ then the cop number is $1$ with probability that tends to $1$ as $n$ tends to infinity. The case $d=2$ was proved earlier and independently in \cite{bdfm}, using a different approach. Our method provides a tight $O(1/r^2)$ upper bound for the number of rounds needed to catch the robber.
BibTeX
@article{alon2014chasing,
  author = {Noga Alon and Pawel Pralat},
  title = {{Chasing robbers on random geometric graphs - An alternative approach}},
  journal = {Discret. Appl. Math.},
  year = {2014},
  doi = {10.1016/j.dam.2014.06.004},
}
Figure