  Dominating sets in graphs are often used to model some monitoring of the
graph: guards are posted on the vertices of the dominating set, and they can
thus react to attacks occurring on the unguarded vertices by moving there
(yielding a new set of guards, which may not be dominating anymore). A
dominating set is eternal if it can endlessly resist to attacks. From the
attacker's perspective, if we are given a non-eternal dominating set, the
question is to determine how fast can we provoke an attack that cannot be
handled by a neighboring guard. We investigate this question from a
computational complexity point of view, by showing that this question is
PSPACE-hard, even for graph classes where finding a minimum eternal dominating
set is in P. We then complement this result by giving polynomial time
algorithms for cographs and trees, and showing a connection with tree-depth for
the latter. We also investigate the problem from a parameterized complexity
perspective, mainly considering two parameters: the number of guards and the
number of steps.
