Report
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 |
| المساهمون: | Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon, ANR-21-CE48-0001,P-GASE,Jeux positionnels : complexité, algorithmes et stratégies(2021) |
| المصدر: | https://hal.science/hal-04501118 ; 2024. |
| بيانات النشر: | HAL CCSD |
| سنة النشر: | 2024 |
| المجموعة: | Portail HAL de l'Université Lumière Lyon 2 |
| مصطلحات موضوعية: | eternal dominating set, tree-depth, PSPACE-completeness, parameterized complexity, [INFO]Computer Science [cs], [MATH]Mathematics [math] |
| الوصف: | 26 pages, 4 figures ; 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. |
| نوع الوثيقة: | report |
| اللغة: | English |
| Relation: | info:eu-repo/semantics/altIdentifier/arxiv/2401.10584; hal-04501118; https://hal.science/hal-04501118; https://hal.science/hal-04501118/document; https://hal.science/hal-04501118/file/2401.10584.pdf; ARXIV: 2401.10584 |
| الاتاحة: | https://hal.science/hal-04501118 https://hal.science/hal-04501118/document https://hal.science/hal-04501118/file/2401.10584.pdf |
| Rights: | info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.7E4BA217 |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |