Dominating sets in graphs are often used to model monitoring problems, by posting guards on the vertices of the dominating set. If an (unguarded) vertex is attacked, at least one guard can then react by moving there. This yields a new set of guards, which may not be dominating anymore. A dominating set is eternal if one 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 \(\textsf{PSPACE}\) -hard, even for graph classes where finding a minimum eternal dominating set is in \(\textsf{P}\) . We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with treedepth 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast Winning Strategies for the Attacker in Eternal Domination

  • Guillaume Bagan,
  • Nicolas Bousquet,
  • Nacim Oijid,
  • Théo Pierron

摘要

Dominating sets in graphs are often used to model monitoring problems, by posting guards on the vertices of the dominating set. If an (unguarded) vertex is attacked, at least one guard can then react by moving there. This yields a new set of guards, which may not be dominating anymore. A dominating set is eternal if one 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 \(\textsf{PSPACE}\) -hard, even for graph classes where finding a minimum eternal dominating set is in \(\textsf{P}\) . We then complement this result by giving polynomial time algorithms for cographs and trees, and showing a connection with treedepth 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.