Solving the Sabotage Game is PSPACE-hard
Christof Löding, Philipp Rohde
We consider the sabotage game presented by van Benthem in an essay on
the occasion of Jörg Siekmann's 60th birthday. In this game one player
moves along the edges of a finite, directed or undirected multi-graph and
the other player takes out a link after each step. There are several
algorithmic tasks over graphs which can be considered as winning
conditions for this game, for example reachability, Hamilton path or
complete search. As the game definitely ends after at most the number of
edges (counted with multiplicity) steps, it is easy to see that solving
the sabotage game for the mentioned tasks takes at most PSPACE in the
size of the graph. We will show that on the other hand solving this game
in general is PSPACE-hard for all conditions. We extend this result to
some variants of the game (removing more than one edge per round and
removing vertices instead of edges). Finally we introduce a modal logic
over changing models to express tasks corresponding to the sabotage
games. We will show that model checking this logic is PSPACE-complete.