2018/05/11 by Hannah Guggiari, Alexander Roberts, Guggiari, Hannah +3
Computer Science · #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1805.04386
openalex publication_date 2018/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A cat and mouse play a pursuit and evasion game on a connected graph G with n vertices. The mouse moves to vertices m1,m2,… of G where mi is in the closed neighbourhood of mi-1 for i≥2. The cat tests vertices c1,c2,… of G without restriction and is told whether the distance between ci and mi is at most the distance between ci-1 and mi-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(√(n)) within finite time and that this bound is tight up to a constant factor. This disproves a conjecture of Dayanikli and Rautenbach.