Abstract of Paper

Solving the Sabotage Game is PSPACE-hard
by Christof Loding and Philipp Rohde

Abstract:

We consider the sabotage game presented by van Benthem in an essay on the
occasion of J\"org 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 introduce a modal logic over changing models to express
tasks corresponding to the sabotage games and we show that model checking
this logic is PSPACE-complete.