A Note on the Complexity of Defensive Domination

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₂. 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₂-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₂-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.