2026-10-08T14:21:24Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:24142 2025-11-12T12:33:34Z ddc:004 open_access
A Note on the Complexity of Defensive Domination Chaplick, Steven Gutowski, Grzegorz Krawczyk, Tomasz graph domination computational complexity In a graph G, a k-attack A is any set of at most k vertices and 𝓁-defense D is a set of at most 𝓁 vertices. We say that defense D counters attack A if each a ∈ A can be matched to a distinct defender d ∈ 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 𝓁 given on input, if there exists an 𝓁-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 Ξ£^𝖯₂. 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 Ξ£^𝖯₂-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 Ξ£^𝖯₂-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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Steven Chaplick and Grzegorz Gutowski and Tomasz Krawczyk 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.35 urn:nbn:de:0030-drops-241420 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.35 eng https://creativecommons.org/licenses/by/4.0/legalcode