Finding a princess in a palace: A pursuit-evasion problem

2012/04/24 by John R. Britnell, Mark Wildon, Britnell, John R. +1 · 1 citation
Computer Science · Engineering · #(secondary) 91A24 #05C57 #91A43 #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Guidance and Control Systems

paper · pdf · doi:10.48550/arxiv.1204.5490

openalex publication_date 2012/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper solves a pursuit-evasion problem in which a prince must find a princess who is constrained to move on each day from one vertex of a finite graph to another. Unlike the related and much studied `Cops and Robbers Game', the prince has no knowledge of the position of the princess; he may, however, visit any single room he wishes on each day. We characterize the graphs for which the prince has a winning strategy, and determine, for each such graph, the minimum number of days the prince requires to guarantee to find the princess.

Citations

• Vertex-to-vertex pursuit in a graph

Cited by

• Seeing is not believing in limited visibility cops and robbers

Related

• Algorithms, hardness and graph products on a pursuit-evasion game
• Escape and Evasion on Finite Graphs
• Fully Active Cops and Robbers
• Searching for an Intruder on Graphs and Their Subdivisions
• An anti-incursion algorithm for unknown probabilistic adversaries on connected graphs