تقرير
Fast winning strategies for the attacker in eternal domination
| العنوان: | Fast winning strategies for the attacker in eternal domination |
|---|---|
| المؤلفون: | Bagan, Guillaume, Bousquet, Nicolas, Oijid, Nacim, Pierron, Théo |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Discrete Mathematics, Mathematics - Combinatorics, 68R10, G.2.2 |
| الوصف: | 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. Comment: 26 pages, 4 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2401.10584 |
| رقم الأكسشن: | edsarx.2401.10584 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |