Approximating the position of a hidden agent in a graph

Abstract

A cat and mouse play a pursuit and evasion game on a connected graph $G$ with $n$ vertices. The mouse moves to vertices $m_1,m_2,\dots$ of $G$ where $m_i$ is in the closed neighbourhood of $m_{i-1}$ for $i\ge 2$. The cat tests vertices $c_1,c_2,\dots$ of $G$ without restriction and is told whether the distance between $c_i$ and $m_i$ is at most the distance between $c_{i-1}$ and $m_{i-1}$. The mouse knows the cat's strategy, but the cat does not know the mouse's strategy. We will show that the cat can determine the position of the mouse up to distance $O(\sqrt{n})$ within finite time and that this bound is tight up to a constant factor. This disproves a conjecture of Dayanikli and Rautenbach.

13 pages