Fast winning strategies for the attacker in eternal domination
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910527638208512 |
|---|---|
| author | Bagan, Guillaume Bousquet, Nicolas Oijid, Nacim Pierron, Théo |
| author_facet | Bagan, Guillaume Bousquet, Nicolas Oijid, Nacim Pierron, Théo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10584 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast winning strategies for the attacker in eternal domination Bagan, Guillaume Bousquet, Nicolas Oijid, Nacim Pierron, Théo Discrete 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. |
| title | Fast winning strategies for the attacker in eternal domination |
| topic | Discrete Mathematics Combinatorics 68R10 G.2.2 |
| url | https://arxiv.org/abs/2401.10584 |