2017/04/19 by Anthony Bonato, Bonato, Anthony, Gary MacGillivray +1 · 8 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics (math.CO) #Computer science #FOS: Mathematics #Game Theory and Applications #Mathematics #Optimization and Search Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1704.05655
published in arXiv (Cornell University) (Cornell University)
arxiv created 2017/04/19 · openalex publication_date 2017/04/19 · arxiv updated 2017/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a definition of generalized Cops and Robbers games where there are two players, the Pursuer and the Evader, who each move via prescribed rules. If the Pursuer can ensure that the game enters into a fixed set of final positions, then the Pursuer wins; otherwise, the Evader wins. A relational characterization of the games where the Pursuer wins is provided. A precise formula is given for the length of the game, along with an algorithm for computing if the Pursuer has a winning strategy whose complexity is a function of the parameters of the game. For games where the position of one player does not affect the available moves of he other, a vertex elimination ordering characterization, analogous to a cop-win ordering, is given for when the Pursuer has a winning strategy.