The following technical report is available from
http://aib.informatik.rwth-aachen.de/:
Christof Löding and Philipp Rohde
Solving the Sabotage Game is PSPACE-hard
2003-05
Abstract:
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.
Regards,
Volker
--
http://www-i2.informatik.rwth-aachen.de/stolz/
