Continuous Defensive Domination Problems
This work provides complexity classifications for a generalization of defensive domination problems, which is of interest to researchers in computational geometry and graph theory.
The paper studies the complexity of the Continuous Defensive Domination problem, showing it is Σ^P_2-complete for vertex-restricted attacks with large δ, and NP-complete for unrestricted attacks. It also analyzes how complexity changes when attacks or defenses are multisets.
The problem Defensive $δ$-Covering, for some covering range $δ> 0$, is a continuous facility location problem on undirected graphs where all edges have unit length. It is a generalization of Defensive Dominating Set and $δ$-Covering. An attack and defense are sets of points, which are on vertices or on the interior of an edge. A defense counters an attack, if there is a matching of the points in the defense to the points in the attack, such that any matched points have distance at most $δ$, and every point in the attack is matched. The task is, given a graph $G$ and numbers $\ell, k \in \mathbb N$, to find a defense of size at most $\ell$ that counters every possible attack of size at most $k$. We study the complexity of this problem in various different settings. We show that if the attack is restricted to vertices, the problem is $Σ^P_2$-complete for large $δ$, but if the attack may consist of any points on the graph, it is NP-complete. Additionally, we analyze how the complexity changes if the attacks or defenses may be a multiset. If the defense is allowed to be a multiset, the complexity does not change in any case we consider, while if the attack is allowed to be a multiset, the problem often becomes easier. To show containment in the various complexity classes, we introduce a number of discretization arguments, which show that solutions with a regular structure must always exist.