2026-07-23T12:54:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25726 2026-06-23T12:45:17Z ddc:004 open_access

Nemesis, an Escape Game in Graphs Bergé, Pierre Dailly, Antoine Gerard, Yan Graphs Evasion and Pursuit Games PSPACE-completeness Quantified SAT Canadian Traveler Problem Cat Herding Problem We define a new escape game in graphs that we call Nemesis. The game is played on a graph having a subset of vertices labeled as exits and the goal of one of the two players, called the fugitive, is to reach one of these exit vertices. The second player, i.e. the fugitive adversary, is called the Nemesis. Her goal is to trap the fugitive in a connected component which does not contain any exit. At each round of the game, the fugitive moves from one vertex to an adjacent vertex. Then the Nemesis deletes one edge anywhere in the graph. The game ends when either the fugitive reached an exit or when he is in a connected component that does not contain any exit. In trees and graphs of maximum degree bounded by 3, Nemesis can be solved in linear time. For arbitrary graphs, we show that Nemesis is PSPACE-complete, and that it is NP-hard on planar multigraphs. We extend our results to the related Cat Herding problem, proving its PSPACE-completeness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Bergé and Antoine Dailly and Yan Gerard 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.7 urn:nbn:de:0030-drops-257261 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode