2015/11/03 by Arefin Huq, Huq, Arefin
Computer Science · #Algorithms and Data Compression #Artificial Intelligence in Games #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1511.00984
openalex publication_date 2015/11/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cat-and-mouse is a two-player game on a finite graph. Chandra and Stockmeyer showed cat-and-mouse is P-complete on directed graphs. We show cat-and-mouse is P-complete on undirected graphs. To our knowledge, no proof of the directed case was ever published. To fill this gap we give a proof for directed graphs and extend it to undirected graphs. The proof is a reduction from a variant of the circuit value problem.