A Note on the Complexity of Defensive Domination

We present a reduction from CliqueNodeDeletion. Assume that we are given an instance $G,s,t$, where $s$ is the number of vertices to remove from $G$ and $t$ is the size of clique to avoid as a subgraph. For technical reasons, we assume that $t⩾4$. Let $n=\left|V(G)\right|$ denote the number of vertices in $G$.

We construct an equivalent instance $G^{\prime },k,\mathrm{\ell }$ of DefensiveDominatingSet. We set the maximum size of an attack $k=n+s$, the maximum size of a defense $\mathrm{\ell }=4(n+s)+nt-(t-1)$, and construct the graph $G^{\prime }$ as depicted in Figure 1:

• $\mathrm{■}$

  For each vertex $v\in V(G)$, we introduce two vertices $v^{\prime }$ and $v^{\prime \prime }$ representing $v$ in $G^{\prime }$. Set $W$ denotes vertices $v^{\prime }$, $v^{\prime \prime }$ introduced for all $v\in V(G)$.

• $\mathrm{■}$

  For each edge $e=(u,v)$ in $E(G)$, we introduce the vertex $e^{\prime }$ and add the edges joining $e^{\prime }$ with four vertices $u^{\prime }$, $u^{\prime \prime }$, $v^{\prime }$, $v^{\prime \prime }$ in $W$. Set $F$ denotes vertices $e^{\prime }$ introduced for all $e\in E(G)$.

• $\mathrm{■}$

  We introduce four independent sets: $I_1$ of size $n+s$; $I_2$ of size $n+s-\left(\genfrac{}{}{0pt}{}{t}{2}\right)$; $I_3$ of size $n+s$; and $I_4$ of size $n+s+\mathrm{\ell }$.

• $\mathrm{■}$

  We introduce three cliques: $Q_1$ of size $n+s$; $Q_2$ of size $n+s-(t+1)$; and $Q_3$ of size $n+s$.

• $\mathrm{■}$

  For each vertex $v\in V(G)$, we introduce a complete bipartite graph with one bipartition class $I_v$ of size $\left(\genfrac{}{}{0pt}{}{t}{2}\right)$, and the other class $I_v^{\prime }$ of size $t$. Set $I_V$ denotes the union of sets $I_v$ for all $v\in V(G)$ and $I_V^{\prime }$ denotes the union of sets $I_v^{\prime }$ for all $v\in V(G)$.

• $\mathrm{■}$

  We add edges of complete bipartite graphs given by the biparition classes: $(Q_1,I_1)$; $(Q_2,Q_1\cup I_2\cup F\cup I_V)$; $(Q_3,I_3)$; $(W,Q_3\cup I_4)$; and $(\{v^{\prime },v^{\prime \prime }\},I_v)$ for each $v\in V(G)$.

We claim that $s$ vertices can be removed from $G$ so that the resulting graph does not include $K_t$ as a subgraph if and only if there is an $\mathrm{\ell }$-defense that counters every $k$-attack in $G^{\prime }$. Before presenting the proof, let us give some ideas on the role of different “gadgets” used in the construction of $G^{\prime }$. The sets $I$ force any successful defense to position many defenders in their neighborhood. This allows for good control over the degrees of freedom in successful $\mathrm{\ell }$-defenses. The set $W$ contains two copies of each vertex of $G$ and the defense is forced to position at least one defender on them. We use the possibility of choosing some of the second copies in each pair to express the selection of a clique hitting set. We are able to limit the “dangerous” choices of $k$-attacks so that they express the choice of edges of a clique $K_t$ in the set $F$. We independently prove the implications in both directions.

($\Rightarrow$) Let $X$ be a solution to the instance $G,s,t$. We have $\left|X\right|=s$ and $G\setminus X$ does not include $K_t$ as a subgraph. We construct the following defense $D$:

Note that $D$ positions exactly $n+s$ defenders on $W$. Additionally, $D$ has $nt$ defenders on $I_V^{\prime }$ and $3(n+s)-(t+1)$ defenders on $Q_1\cup Q_2\cup Q_3$, which gives $\mathrm{\ell }$ defenders in total. We show that $D$ counters every attack of size at most $n+s$. Suppose for a contradiction that $A$ is an inclusion minimal attack with . First, we observe that every vertex in the sets $W$, $I_1$, $I_3$, $I_4$, $Q_1$, $Q_2$, and $Q_3$ is adjacent to at least $n+s$ defenders (either from the set $Q_1$, $Q_2$, $Q_3$ or $W$). If any of these vertices is included in $A$, then ${\mathrm{count}}_D(N[A])⩾n+s⩾\left|A\right|$. We conclude that

As every vertex in $I_V^{\prime }$ is in $D$, we do not have $A\subseteq I_V^{\prime }$ and hence $A\cap (I_2\cup F\cup I_V)\ne \mathrm{\varnothing }$. In particular, $Q_2\subseteq N[A]$, and hence ${\mathrm{count}}_D(N[A])⩾\left|Q_2\right|=n+s-(t+1)$. Since every vertex in $I_V$ is adjacent to additional $t+1$ defenders in $W\cup I_V^{\prime }$, we have $A\cap I_V=\mathrm{\varnothing }$. Now, $N[I_V^{\prime }]\cap A=I_V^{\prime }\cap A$, and $I_V^{\prime }\subseteq D$, so by the minimality of $A$ we get $A\cap I_V^{\prime }=\mathrm{\varnothing }$. We conclude that

As for $t⩾4$ and $\left|A\right|>{\mathrm{count}}_D(N[A])⩾n+s-(t+1)>n+s-\left(\genfrac{}{}{0pt}{}{t}{2}\right)=\left|I_2\right|$, we also have $A\cap F\ne \mathrm{\varnothing }$. As $A$ includes at least one vertex in $F$, $N[A]$ includes at least two vertices in $W\cap D$ and $\left|A\right|>n+s-(t+1)+2$. We conclude that

Now, as $A$ includes more than $\left(\genfrac{}{}{0pt}{}{t-1}{2}\right)$ vertices in $F$, $N[A]$ includes at least $t$ vertices in $W\cap D$, and $\left|A\right|>n+s-(t+1)+t$. Hence, $\left|A\right|=n+s$ and $I_2⊊A$, as otherwise we would have ${\mathrm{count}}_D(N[A])>n+s$. We call an attack $A$ to be serious if

We have shown that attack $A$ is serious. Any $\left(\genfrac{}{}{0pt}{}{t}{2}\right)$ edges in $G$ span at least $t+1$ vertices or span $t$ vertices that form a clique $K_t$ in $G$. As we know that $G\setminus X$ does not contain $K_t$ as a subgraph, we get that if the edges span only $t$ vertices then at least one of them is in $X$. In either case, we get ${\mathrm{count}}_D(N[A])⩾n+s-(t+1)+(t+1)=n+s$ and $D$ counters $A$.

($\Leftarrow$) Let $D$ be an $\mathrm{\ell }$-defense that counters every $k$-attack in $G^{\prime }$. We make the following observations.

1. 1.

   As $D$ counters attack $I_1$, there are at least $n+s$ defenders in $I_1\cup Q_1$.

2. 2.

   As $D$ counters attack $I_3$, there are at least $n+s$ defenders in $I_3\cup Q_3$.

3. 3.

   As $D$ counters every possible $(n+s)$-attack in $I_4\setminus D$, there are at least $n+s$ defenders in $W$.

4. 4.

   For every $v\in V(G)$, as $D$ counters attack $I_v^{\prime }$, there are at least $t$ defenders in $I_v\cup I_v^{\prime }$. Thus, in total, there are at least $nt$ defenders in $I_V\cup I_V^{\prime }$.

5. 5.

   By calculation, there are at most $n+s-(t+1)$ defenders in $I_2\cup Q_2\cup F$.

6. 6.

   For every $v\in V(G)$, as $D$ counters attack $I_2\cup I_v$ and there are at most $n+s-(t+1)$ defenders in $I_2\cup Q_2$, there are at least $t+1$ defenders in $I_v\cup I_v^{\prime }\cup \{v^{\prime },v^{\prime \prime }\}$. As $\left|I_v^{\prime }\right|=t$, at least one of the defenders is in $I_v\cup \{v^{\prime },v^{\prime \prime }\}$.

We now construct a modified defense $D^{\prime }$ and claim that $D^{\prime }$ counters every serious attack on $G$. As we focus on serious attacks, and the defenders in $I_V$ are not used to counter any serious attack, we move some of them. For each $v\in V(G)$ if $v^{\prime }\notin D$ and $v^{\prime \prime }\notin D$, we move one defender from $I_v$ to $v^{\prime }$ (guaranteed to be there by point 6). Observe that even after this move there are at least $t$ defenders in $I_v\cup I_v^{\prime }$. As there are still at least $nt+(n+s)+(n+s)$ defenders in $I_V\cup I_V^{\prime }\cup I_1\cup Q_1\cup I_3\cup Q_3$, there are at most $(n+s)+(n+s-(t+1)$ in $I_2\cup Q_2\cup F\cup W$. Second, since serious attacks include only vertices in $I_2\cup F$, and vertices in $Q_2$ dominate $I_2\cup F$, and there are at most $n+s-(t+1)$ defenders in $I_2\cup Q_2\cup F$, we move all defenders from $I_2$ and $F$ to $Q_2$. Third, while $\left|D\cap W\right|>n+s$, we select any $v\in V(G)$ with defenders both in $v^{\prime }$ and $v^{\prime \prime }$ and move the defender from $v^{\prime \prime }$ to $Q_2$. The resulting defense $D^{\prime }$ has the property that it also counters every serious attack, as $D$ did.

The resulting defense $D^{\prime }$ has exactly $n+s$ defenders in $W$, at most $n+s-(t+1)$ defenders in $Q_2$, at least one defender in each $\{v^{\prime },v^{\prime \prime }\}$ for every $v\in V(G)$, and counters every serious attack. Let $X$ be a set of vertices $v$ in $V(G)$ for which both $v^{\prime }$ and $v^{\prime \prime }$ are in $D^{\prime }$. There are exactly $s$ such vertices. We claim that $G\setminus X$ does not contain $K_t$ as a subgraph. Indeed, given a $t$-element set $Q$ of vertices of $G$ with $Q\cap X=\mathrm{\varnothing }$ and $G[Q]$ isomorphic to $K_t$, we can create a $k$-attack composed of $I_2$ and the set of $\left(\genfrac{}{}{0pt}{}{t}{2}\right)$ vertices $e^{\prime }$ representing edges of $G[Q]$. This attack has size $n+s$ and has at most $n+s-(t+1)$ neighboring defenders in $Q_2$ and exactly $t$ neighboring defenders in $W$. Thus, this serious attack is not countered by $D^{\prime }$, which contradicts the construction of $D^{\prime }$.

We leave it to the reader to verify that exactly the same reduction also shows that DefensiveDominatingMultiset is also a ${\mathrm{\Sigma }}_2^{𝖯}$-complete problem. $◀$

Consider a multiset defense $D$. If it is not proper, then there exist two vertices $u,v\in D$ such that $I_u⊊I_v$. Let $D^{\prime }$ be the multiset defense obtained from $D$ by replacing every copy of $u$ with an additional copy of $v$. Clearly, $\left|D^{\prime }\right|=\left|D\right|$. Since $I_u⊊I_v$, we have that $N[u]\subseteq N[v]$ and that any attack $A$ that is countered by $D$ using defenders in $u$ is countered by $D^{\prime }$ using added defenders in $v$. Therefore, $D^{\prime }$ counters every attack countered by $D$. Observe that this replacement increases the total length of the intervals that represent vertices in the defense. Thus, repeating this replacement procedure eventually stops and yields a proper defense that counters any attack that the original defense counters. $◀$

Note that Observation 6 holds specifically for the multiset setting and does not have a direct analogue for DefensiveDominatingSet. The next observation is that sets with smaller union are more dangerous for any defense than those with larger union.

We have that ${\mathrm{count}}_D(N[A_2])$ is the number of intervals in $D$ that have a nonempty intersection with $\mathrm{sum}(A_2)$ which is a subset of $\mathrm{sum}(A_1)$. Thus,

$◀$

Let $x=\mathrm{right}(I_v)$ for some vertex $v\in V(G)$. Let $V_x=\{v\in V(G):\mathrm{right}(I_v)\le x\}$ denote the nonempty set of vertices that lie completely to the left of $x$ in the representation. Let $c=\left|V_x\right|$ and for every integer $1\le i\le c$ we define the $i$-th block at $x$, denoted $B_{x,i}$, in the following way. Let $v_1,v_2,\mathrm{\dots },v_c$ be $V_x$ arranged in a sequence sorted descending by the left endpoint of the representing interval, that is, $\mathrm{left}(I_u)>\mathrm{left}(I_w)$ if and only if $u$ appears earlier than $w$ in the sequence. We select $B_{x,i}=\{v_1,v_2,\mathrm{\dots },v_i\}$ to be the first $i$ elements in the sequence. Note that if defined, $B_{x,i}$ contains exactly $i$ vertices, $B_{x,i+1}$ is a superset of $B_{x,i}$, and $B_{x,i}$ maximizes $\mathrm{left}(\mathrm{span}(X))$ among all subsets $X\subseteq V_x$ with $\left|X\right|=i$.

We say that $D$ is a $k$-block defense if it counters every attack $B_{x,i}$ for every possible right endpoint $x$ and every $i\le k$.

Assume to the contrary that a proper $k$-block defense $D$ does not counter some $k$-attack. By Observation 1 we have a set $A$ with . Among such sets, we select $A$ with the minimum size $m$.

Let $w\in A$ be the vertex that maximizes $\mathrm{right}(I_w)$ among the vertices in $A$. Let $x=\mathrm{right}(I_w)$, $c=\left|V_x\right|$, and $v_1,v_2,\mathrm{\dots },v_c$ be $V_x$ arranged in a sequence sorted descending by the left endpoint of the representing interval. All elements of $A$ are represented to the left of $x$, so we have $m\le c$. Recall that $B_{x,i}=\{v_1,v_2,\mathrm{\dots },v_i\}$ for every $1\le i\le c$. By the assumption of the lemma, we know that $A\ne B_{x,m}$. Since $D$ counters $B_{x,m}$, we have and there is $d\in D$ with $d\in N[B_{x,m}]$ and $d\notin N[A]$. Every interval representing a vertex in $A$ is either completely to the left or completely to the right of $I_d$. Let

Since $x\in I_w$ and $x\notin I_d$, we have $w\in A_2$. Since , we have $A_1\ne \mathrm{\varnothing }$. We have partitioned $A$ into two nonempty subsets $A_1$ and $A_2$.

By the minimality of $A$ we have ${\mathrm{count}}_D(N[A_1])\ge \left|A_1\right|$ and ${\mathrm{count}}_D(N[A_2])\ge \left|A_2\right|$. We get that there is at least one $d^{\prime }\in D\cap N[A_1]\cap N[A_2]$, as otherwise we would have ${\mathrm{count}}_D(N[A])={\mathrm{count}}_D(N[A_1])+{\mathrm{count}}_D(N[A_2])\ge \left|A_1\right|+\left|A_2\right|=\left|A\right|$. Interval $I_{d^{\prime }}$ intersects both $\mathrm{span}(A_1)$ and $\mathrm{span}(A_2)$. This allows us to write the following inequalities:

and conclude that $I_d$ is a proper subset of $I_{d^{\prime }}$ contradicting with $D$ being a proper defense. $◀$

We are ready for the proof of the main result of this section. See 4

The proposed algorithm, see Algorithm 1 for the pseudocode, works as follows. It assumes that $G$ has $n$ vertices and is given in the interval representation by the intervals $I_1,I_2,\mathrm{\dots },I_n$. It sorts the intervals ascending by their right endpoints. Then, for every $1\le i\le n$, let $x$ be the right endpoint of the $i$-th interval in the list. The algorithm calculates the number $count$ of defenders missing to counter every $m$-block attack $B_{x,m}$ for $m\le k$. Then, it selects the interval $d$ that maximizes the right endpoint among all intervals that include $x$. The algorithm adds $count$ copies of the interval $d$ to $D$.

Clearly, Algorithm 1 runs in polynomial time. The algorithm only adds inclusion maximal intervals to $D$, so the constructed multiset defense $D$ is proper. The algorithm explicitly adds the required number of defenders to counter every possible attack $B_{x,m}$, so $D$ is also $k$-block. Thus, by Lemma 8 we get that $D$ counters every $k$-attack in $G$.

For the proof that the defense $D$ is of minimum size, let $\mathrm{\ell }=\left|D\right|$, $J_1,J_2,\mathrm{\dots },J_{\mathrm{\ell }}$ be the multiset of intervals in $D$ sorted ascending by their left endpoints. Assuming to the contrary, let $D^{\prime }$ be another proper defense that counters every $k$-attack with and $K_1,K_2,\mathrm{\dots },K_{{\mathrm{\ell }}^{\prime }}$ be the multiset of intervals in $D^{\prime }$ sorted ascending by their left endpoints. Among such defenses, select one that maximizes the number $p$ such that $J_i=K_i$ for all $1\le i\le p$. We have . Let $d=J_{p+1}$ and $d^{\prime }=K_{p+1}$. We do not have $d^{\prime }⊊d$, as otherwise we could exchange $d^{\prime }$ for $d$ in $D^{\prime }$ and get another defense that counters every $k$-attack of the same size, but with larger $p$. We also do not have $d⊊d^{\prime }$, as the algorithm only adds inclusion maximal intervals to $D$. Let $x,m$ be such that the algorithm added $d$ to $D$ when considering attack $B_{x,m}$.

If $\mathrm{left}(d^{\prime })>\mathrm{left}(d)$ then $\mathrm{right}(d^{\prime })>\mathrm{right}(d)$ and as the algorithm did not add $d^{\prime }$ to $D$ we have $\mathrm{left}(d^{\prime })>x$. This means that $D^{\prime }$ has exactly $p$ intervals $K_1,\mathrm{\dots },K_p=J_1,\mathrm{\dots },J_p$ with the left endpoint less than or equal to $x$. The algorithm calculated that these intervals do not counter $B_{x,m}$ and no other interval in $D^{\prime }$ intersects $\mathrm{span}(B_{x,m})$. We conclude that $D^{\prime }$ does not counter $B_{x,m}$, a contradiction.

If then and we can exchange $d^{\prime }$ for $d$ in $D^{\prime }$ and get another defense $D^{\prime \prime }$ that counters every $k$-attack with $\left|D^{\prime \prime }\right|=\left|D^{\prime }\right|$ but with bigger $p$. Indeed, we can show that the resulting defense $D^{\prime \prime }$ satisfies ${\mathrm{count}}_{D^{\prime \prime }}(N[B_{y,q}])\ge q$ for every possible right endpoint $y$ and every $q\le k$. For , this follows from the fact that $D^{\prime \prime }$ agrees with $D$ on the first $p$ intervals that are enough to counter these attacks. For $y\ge x$, we have $d^{\prime }\in N[B_{y,q}]\Rightarrow d\in N[B_{y,q}]$ and ${\mathrm{count}}_{D^{\prime \prime }}(N[B_{y,q}])\ge {\mathrm{count}}_{D^{\prime }}(N[B_{y,q}])\ge q$. We get a contradiction with the choice of $D^{\prime }$. $◀$

We claim that Algorithm 1 can be implemented to run in $O\left(nk\right)$ time using standard techniques, and we omit the details of this implementation.