A Note on the Complexity of Defensive Domination
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914068837695488 |
|---|---|
| author | Chaplick, Steven Gutowski, Grzegorz Krawczyk, Tomasz |
| author_facet | Chaplick, Steven Gutowski, Grzegorz Krawczyk, Tomasz |
| contents | In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to a distinct defender d in D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and l given on input, if there exists an l-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs.
The defensive domination problem is naturally in the complexity class $Σ^P_2$. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note we prove that the defensive domination problem is $Σ^P_2$-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also $Σ^P_2$-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_14390 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Note on the Complexity of Defensive Domination Chaplick, Steven Gutowski, Grzegorz Krawczyk, Tomasz Computational Complexity In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to a distinct defender d in D with a equal to d or a adjacent to d in G. In the defensive domination problem, we are interested in deciding, for a graph G and positive integers k and l given on input, if there exists an l-defense that counters every possible k-attack on G. Defensive domination is a natural resource allocation problem and can be used to model network robustness and security, disaster response strategies, and redundancy designs. The defensive domination problem is naturally in the complexity class $Σ^P_2$. The problem was known to be NP-hard in general, and polynomial-time algorithms were found for some restricted graph classes. In this note we prove that the defensive domination problem is $Σ^P_2$-complete. We also introduce a natural variant of the defensive domination problem in which the defense is allowed to be a multiset of vertices. This variant is also $Σ^P_2$-complete, but we show that it admits a polynomial-time algorithm in the class of interval graphs. A similar result was known for the original setting in the class of proper interval graphs. |
| title | A Note on the Complexity of Defensive Domination |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2504.14390 |