# Defensive Alliances in Graphs of Bounded Treewidth111This work was supported
by the Austrian Science Fund (FWF) projects P25607 and Y698.

Bernhard Bliem and Stefan Woltran

###### Abstract

A set $S$ of vertices of a graph is a defensive alliance if, for each element
of $S$, the majority of its neighbors is in $S$. The problem of finding a
defensive alliance of minimum size in a given graph is $\mathsf{NP}$-hard and
there are polynomial-time algorithms if certain parameters are bounded by a
fixed constant. In particular, fixed-parameter tractability results have been
obtained for some structural parameters such as the vertex cover number.
However, for the parameter treewidth, the question of whether the problem is
FPT has remained open. This is unfortunate because treewidth is perhaps the
most prominent graph parameter and has proven successful for many problems. In
this work, we give a negative answer by showing that the problem is
$\mathsf{W[1]}$-hard when parameterized by treewidth, which rules out FPT
algorithms under common assumptions. This is surprising since the problem is
known to be FPT when parameterized by solution size and “subset problems” that
satisfy this property usually tend to be FPT for bounded treewidth as well. We
prove $\mathsf{W[1]}$-hardness by using techniques from a recent hardness
result for the problem of finding so-called secure sets in a graph.

##  1 Introduction

The objective of many problems that can be modeled as graphs is finding a
group of vertices that together satisfy some property. In this respect, one of
the concepts that has been quite extensively studied is the notion of a
defensive alliance [28, 27], which is a set of vertices such that for each
element $v$ at least half of its neighbors are also in the alliance. The name
“defensive alliance” stems from the intuition that the neighbors of an element
$v$ that are also in the alliance can help out in case $v$ is attacked by its
other neighbors.

Notions like this can be applied to finding groups of nations, companies or
individuals that depend on each other, but also to more abstract situations
like finding groups of websites that form communities [18]. Another possible
application for defensive alliances are computer networks, where a defensive
alliance represents computers that can provide a certain desired resource; any
computer in an alliance can then, with the help of its neighbors that are also
in the alliance, allow access to this resource from all of its neighbors
simultaneously [20].

Several variants of defensive alliances have also been studied. The papers
that originally proposed defensive alliances also propose related notions like
offensive and powerful alliances. An offensive alliance is a set $S$ of
vertices such that every _neighbor_ of an element of $S$ has at least half of
its neighbors in $S$, and a powerful alliance is both a defensive and an
offensive alliance. Any of these alliances is called _global_ if it is at the
same time a dominating set. Another variant is to consider alliances $S$
where, for each vertex $v\in S$, the difference between the number of
neighbors of $v$ in $S$ and the number of other neighbors of $v$ is at most a
given integer [31]. For comprehensive overviews of different kinds of
alliances in graphs, we refer to the surveys [34, 17].

The Defensive Alliance problem can be specified as follows: Given a graph $G$
and an integer $k$, is there a defensive alliance $S$ in $G$ such that
$1\leqslant{\lvert S\rvert}\leqslant k$? It is known that this problem is
$\mathsf{NP}$-complete [22, 23], and so is the corresponding problem for
global defensive alliances [9]. However, if we restrict ourselves to trees,
Defensive Alliance becomes trivial and in fact the corresponding problems for
several non-trivial variants become solvable in linear time [22].

There has also been some work on the parameterized complexity of alliance
problems. In particular, determining whether a defensive, offensive and
powerful alliance of a given (maximum) size exists is fixed-parameter
tractable when parameterized by the solution size [16, 15]. Also structural
parameters have been considered to some extent. Recently, [24] proved that
these problems can be solved in polynomial time if the clique-width of the
instances is bounded by a constant. The authors also provide an FPT algorithm
when the parameter is the size of the smallest vertex cover. Moreover, [15]
showed that the decision problems for defensive alliances and global defensive
alliances are fixed-parameter tractable when parameterized by the combination
of treewidth and maximum degree. Despite these advances regarding, the
question of whether or not Defensive Alliance parameterized by treewidth is
fixed-parameter tractable has so far remained open.

Treewidth [30, 5, 7] is one of the most extensively studied structural
parameters and indicates how close a graph is to being a tree. It is
particularly attractive because many hard problems become tractable on
instances of bounded treewidth, and in several practical applications it has
been observed that the considered problem instances exhibit small treewidth
[5, 33, 26]. Hence it would be very appealing to obtain an FPT algorithm for
the Defensive Alliance problem using this parameter.

The main contribution of this paper is a parameterized complexity analysis of
Defensive Alliance with treewidth as the parameter. The question of whether or
not this problem is fixed-parameter tractable when parameterized by treewidth
has so far been unresolved [24]. In the current chapter, we provide a negative
answer to this question: We show that the problem is hard for the class
$\mathsf{W[1]}$, which rules out fixed-parameter tractable algorithms under
commonly held complexity-theoretic assumptions. This result is rather
surprising for two reasons: First, the problem is tractable on trees [22] and
quite often problems that become easy on trees turn out to become easy on
graphs of bounded treewidth.222To be precise, [22, 21, 10] show that some
variants of Defensive Alliance are tractable on trees, since Defensive
Alliance on trees is trivial. Second, this puts Defensive Alliance among the
very few “subset problems” that are fixed-parameter tractable w.r.t. solution
size but not w.r.t. treewidth. Problems with this kind of behavior are rather
rare, as observed by Dom et al. [13].

We show $\mathsf{W[1]}$-hardness of the problem by first reducing a problem
known to be $\mathsf{W[1]}$-hard to a variant of Defensive Alliance, where
vertices can be forced to be in or out of every solution, and pairs of
vertices can be specified to indicate that every solution must contain exactly
one element of each such pair. In order to prove the desired complexity
result, we then successively reduce this variant to the standard Defensive
Alliance problem.

At the same time, we show $\mathsf{W[1]}$-hardness for the exact variants of
these problems, where we are interested in defensive alliances _exactly_ of a
certain size. Note that a set may lose the property of being a defensive
alliance by adding or removing elements, so these are non-trivial problem
variants. Indeed, exact versions of alliance problems have also been mentioned
as interesting variants in [16] because some algorithms that work for the non-
exact case stop to work for the exact case: A graph has a defensive alliance
of size at most $k$ if and only if it has a _connected_ defensive alliance of
size at most $k$ since every component of a defensive alliance is itself a
defensive alliance. Algorithms that exploit this by looking only for connected
solutions hence fail for the exact versions. (In fact, we will also study the
complexity of other problem variants where this connectedness property does
not apply even in the non-exact case.)

This paper is organized as follows: We first introduce our problems of
interest and describe preliminary concepts in Section 2. In Section 3 we then
show that the Defensive Alliance problem is $\mathsf{W[1]}$-hard when
parameterized by treewidth. Section 4 concludes the paper with a discussion.

The reductions in the current work are based on ideas used in the paper [4],
which analyzed the complexity of a problem related to Defensive Alliance
called Secure Set. That paper has since been extended by a
$\mathsf{W[1]}$-hardness proof for the Secure Set problem parameterized by
treewidth [3]. In the current paper, we take up the ideas behind this hardness
proof and apply them to the Defensive Alliance problem. Due to the different
nature of these two problems, the reductions and proofs for Secure Set do not
work directly for Defensive Alliance but require substantial modifications.

##  2 Background

All graphs are undirected and simple unless stated otherwise. We denote the
set of vertices and edges of a graph $G$ by $\operatorname{V}(G)$ and
$\operatorname{E}(G)$, respectively. We denote an undirected edge between
vertices $u$ and $v$ as $(u,v)$ or equivalently $(v,u)$. It will be clear from
the context whether an edge $(u,v)$ is directed or undirected. Given a graph
$G$, the _open neighborhood_ of a vertex $v\in\operatorname{V}(G)$, denoted by
$N_{G}(v)$, is the set of all vertices adjacent to $v$, and
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$ is called the _closed neighborhood_ of $v$. If
it is clear from the context which graph is meant, we write $N(\cdot)$ and
$N[\cdot]$ instead of $N_{G}(\cdot)$ and $N_{G}[\cdot]$, respectively.

The intuition behind defensive alliances is the following: If we consider a
set $S$ of vertices as “good” vertices and all other vertices as “bad” ones,
then $S$ being a defensive alliance means that each element of $S$ has at
least as many “good” neighbors as “bad” neighbors.

######  Definition 1.

Given a graph $G$, a set $S\subseteq\operatorname{V}(G)$ is a _defensive
alliance in $G$_ if for each $v\in S$ it holds that ${\lvert N[v]\cap
S\rvert}\geqslant{\lvert N[v]\setminus S\rvert}$.

We often write “$S$ is a defensive alliance” instead of “$S$ is a defensive
alliance in $G$” if it is clear from the context which graph is meant. By
definition, the empty set is a defensive alliance in any graph. Thus, in the
following decision problems we ask for a defensive alliances of size at least
1.

$a$$b$$c$$d$$e$ Figure 1: A graph with a minimum non-empty defensive alliance
indicated by circled vertices

For example, in Figure 1, the set $S=\\{a,b\\}$ is a defensive alliance as
${\lvert N[v]\cap S\rvert}\geqslant{\lvert N[v]\setminus S\rvert}$ holds for
each $v\in S$. Note that, for instance, $\\{a,d\\}$ is no defensive alliance
since $d$ is attacked by three vertices but only has the neighbor $a$ to help
defend itself.

Next we introduce several variants of Defensive Alliance that we require in
our proofs. The problem Defensive AllianceF generalizes Defensive Alliance by
designating some “forbidden” vertices that may never be in any solution. This
variant can be formalized as follows:

Defensive AllianceF Input: A graph $G$, an integer $k$ and a set
$V_{\square}\subseteq\operatorname{V}(G)$ Question: Does there exist a set
$S\subseteq\operatorname{V}(G)\setminus V_{\square}$ with $1\leqslant{\lvert
S\rvert}\leqslant k$ that is a defensive alliance?

Defensive AllianceFN is a further generalization that, in addition, allows
“necessary” vertices to be specified that must occur in every solution.

Defensive AllianceFN Input: A graph $G$, an integer $k$, a set
$V_{\square}\subseteq\operatorname{V}(G)$ and a set
$V_{\triangle}\subseteq\operatorname{V}(G)$ Question: Does there exist a set
$S\subseteq\operatorname{V}(G)\setminus V_{\square}$ with
$V_{\triangle}\subseteq S$ and $1\leqslant{\lvert S\rvert}\leqslant k$ that is
a defensive alliance?

Finally, we introduce the generalization Defensive AllianceFNC. Here we may
state pairs of “complementary” vertices where each solution must contain
exactly one element of every such pair.

Defensive AllianceFNC Input: A graph $G$, an integer $k$, a set
$V_{\square}\subseteq\operatorname{V}(G)$, a set
$V_{\triangle}\subseteq\operatorname{V}(G)$ and a set
$C\subseteq\operatorname{V}(G)^{2}$ Question: Does there exist a set
$S\subseteq\operatorname{V}(G)\setminus V_{\square}$ with
$V_{\triangle}\subseteq S$ and $1\leqslant{\lvert S\rvert}\leqslant k$ that is
a defensive alliance and, for each pair $(a,b)\in C$, contains either $a$ or
$b$?

For our results on the parameter treewidth, we need a way to represent the
structure of a Defensive AllianceFNC instance by a graph that augments $G$
with the information in $C$:

######  Definition 2.

Let $I$ be a Defensive AllianceFNC instance, let $G$ be the graph in $I$ and
let $C$ the set of complementary vertex pairs in $I$. By the _primal graph_ of
$I$ we mean the undirected graph $G^{\prime}$ with
$\operatorname{V}(G^{\prime})=\operatorname{V}(G)$ and
$\operatorname{E}(G^{\prime})=\operatorname{E}(G)\cup C$.

When we speak of the treewidth of an instance of Defensive Alliance, Defensive
AllianceF or Defensive AllianceFN, we mean the treewidth of the graph in the
instance. For an instance of Defensive AllianceFNC, we mean the treewidth of
the primal graph.

While the Defensive Alliance problem asks for defensive alliances of size _at
most_ $k$, we also consider the Exact Defensive Alliance problem that concerns
defensive alliances of size _exactly_ $k$. Analogously, we also define exact
versions of the three generalizations of Defensive Alliance presented above.

In this paper’s figures, we often indicate necessary vertices by means of a
triangular node shape, and forbidden vertices by means of either a square node
shape or a superscript square in the node name. If two vertices are
complementary, we often express this in the figures by putting a $\neq$ sign
between them.

$a$$b$$\neq$$c$$d^{\square}$$e$ Figure 2: Illustration of forbidden, necessary
and complementary vertices

For example, in Figure 2, the vertices $b$ and $c$ are complementary and occur
in no solution together; $a$ and the “anonymous” vertex adjacent to $c$ are
necessary and occur in every solution; $d^{\square}$ and the “anonymous”
vertex adjacent to $e$ are forbidden and occur in no solution. In this figure,
the unique minimum non-empty defensive alliance satisfying the conditions of
forbidden, necessary and complementary vertices consists of $a$, $b$ and the
“anonymous” necessary vertex adjacent to $c$.

The following terminology will be helpful: We often use the terms _attackers_
and _defenders_ of an element $v$ of a defensive alliance candidate $S$. By
these we mean the sets $N[v]\setminus S$ and $N[v]\cap S$, respectively. To
show that an element $v$ of a defensive alliance candidate $S$ is _not_ a
counterexample to $S$ being a solution, we sometimes employ the notion of a
_defense_ of $v$ w.r.t. $S$, which assigns to each attacker a dedicated
defender: If we are able to find an injective mapping $\mu:N[v]\setminus S\to
N[v]\cap S$, then obviously ${\lvert N[v]\setminus S\rvert}\leqslant{\lvert
N[v]\cap S\rvert}$, and we call $\mu$ a _defense_ of $v$ w.r.t. $S$. Given
such a defense $\mu$, we say that a defender $d$ _repels_ an attack on $v$ by
an attacker $a$ whenever $\mu(a)=d$. Consequentially, when we say that a set
of defenders $D$ _can repel_ attacks on $v$ from a set of attackers $A$, we
mean that there is a defense that assigns to each element of $A$ a dedicated
defender in $D$.

To warm up, we make some easy observations that we will use in our proofs.
First, for every set $R$ consisting of a majority of neighbors of a vertex
$v$, whenever $v$ is in a defensive alliance, also some element of $R$ must be
in it:

######  Observation 3.

Let $S$ be a defensive alliance in a graph, let $v\in S$ and let $R\subseteq
N(v)$. If ${\lvert R\rvert}>\frac{1}{2}N[v]$, then $S$ contains an element of
$R$.

###### Proof.

Suppose that ${\lvert R\rvert}>\frac{1}{2}{\lvert N[v]\rvert}$ and $S$
contains no element of $R$. Since all elements of $R$ attack $v$, ${\lvert
N[v]\setminus S\rvert}>\frac{1}{2}{\lvert N[v]\rvert}$. Hence $2{\lvert
N[v]\setminus S\rvert}>{\lvert N[v]\rvert}={\lvert N[v]\cap S\rvert}+{\lvert
N[v]\setminus S\rvert}$, and we obtain the contradiction ${\lvert
N[v]\setminus S\rvert}>{\lvert N[v]\cap S\rvert}$. ∎

Next, if one half of the neighbors of an element $v$ of a defensive alliance
attacks $v$, then the other half of the neighbors must be in the defensive
alliance:

######  Observation 4.

Let $S$ be a defensive alliance in a graph, let $v\in S$ and let $N(v)$ be
partitioned into two equal-sized sets $A,D$. If $A\cap S=\emptyset$, then
$D\subseteq S$.

###### Proof.

Since $N(v)$ is partitioned into $A$ and $D$ such that $A\cap S=\emptyset$, we
get $N(v)\cap S=D\cap S$. If some element of $D$ is not in $S$, then $D\cap
S\subset D$ and $A\subset N[v]\setminus S$. By ${\lvert D\rvert}={\lvert
A\rvert}$, we get ${\lvert D\cap S\rvert}+2\leqslant{\lvert N[v]\setminus
S\rvert}$. From ${\lvert N[v]\cap S\rvert}=1+{\lvert N(v)\cap
S\rvert}=1+{\lvert D\cap S\rvert}$ we now obtain the contradiction ${\lvert
N[v]\cap S\rvert}<{\lvert N[v]\setminus S\rvert}$. ∎

In particular, if half of the neighbors of $v$ are forbidden, then $v$ can
only be in a defensive alliance if all non-forbidden neighbors are also in the
defensive alliance.

Finally, we recapitulate some background from complexity theory. In
parameterized complexity theory [14, 19, 29, 11], we study problems that
consist not only of an input and a question, but also of some parameter of the
input that is represented as an integer. A problem is in the class
$\mathsf{FPT}$ (“fixed-parameter tractable”) if it can be solved in time
$f(k)\cdot n^{c}$, where $n$ is the input size, $k$ is the parameter, $f$ is a
computable function that only depends on $k$, and $c$ is a constant that does
not depend on $k$ or $n$. We call such an algorithm an _FPT algorithm_ , and
we call it _fixed-parameter linear_ if $c=1$. Similarly, a problem is in the
class $\mathsf{XP}$ (“slice-wise polynomial”) if it can be solved in time
$f(k)\cdot n^{g(k)}$, where $f$ and $g$ are computable functions. Note that
here the degree of the polynomial may depend on $k$, so such algorithms are
generally slower than FPT algorithms. For the class $\mathsf{W[1]}$ it holds
that $\mathsf{FPT}\subseteq\mathsf{W[1]}\subseteq\mathsf{XP}$, and it is
commonly believed that the inclusions are proper, i.e., $\mathsf{W[1]}$-hard
problems do not admit FPT algorithms. $\mathsf{W[1]}$-hardness of a problem
can be shown using FPT reductions, which are reductions that run in FPT time
and produce an equivalent instance whose parameter is bounded by a function of
the original parameter.

For problems whose input can be represented as a graph, one important
parameter is _treewidth_ , which is a structural parameter that, roughly
speaking, measures the “tree-likeness” of a graph. It is defined by means of
tree decompositions, originally introduced in [30]. The intuition behind tree
decompositions is to obtain a tree from a (potentially cyclic) graph by
subsuming multiple vertices under one node and thereby isolating the parts
responsible for cyclicity.

######  Definition 5.

A _tree decomposition_ of a graph $G$ is a pair $\mathcal{T}=(T,\chi)$ where
$T$ is a (rooted) tree and $\chi:\operatorname{V}(T)\to
2^{\operatorname{V}(G)}$ assigns to each node of $T$ a set of vertices of $G$
(called the node’s _bag_), such that the following conditions are met:

  1. 1.

For every vertex $v\in\operatorname{V}(G)$, there is a node
$t\in\operatorname{V}(T)$ such that $v\in\chi(t)$.

  2. 2.

For every edge $(u,v)\in\operatorname{E}(G)$, there is a node
$t\in\operatorname{V}(T)$ such that $\\{u,v\\}\subseteq\chi(t)$.

  3. 3.

For every $v\in\operatorname{V}(G)$, the subtree of $T$ induced by
$\\{t\in\operatorname{V}(T)\mid v\in\chi(t)\\}$ is connected.

We call $\max_{t\in\operatorname{V}(T)}\lvert\chi(t)\rvert-1$ the _width_ of
$\mathcal{T}$. The _treewidth_ of a graph is the minimum width over all its
tree decompositions.

In general, constructing an optimal tree decomposition (i.e., a tree
decomposition with minimum width) is intractable [1]. However, the problem is
solvable in linear time on graphs of bounded treewidth (specifically in time
$w^{\mathcal{O}(w^{3})}\cdot n$, where $w$ is the treewidth) [6] and there are
also heuristics that offer good performance in practice [12, 8].

In this paper we will consider so-called _nice_ tree decompositions:

######  Definition 6.

A tree decomposition $\mathcal{T}=(T,\chi)$ is _nice_ if each node
$t\in\operatorname{V}(T)$ is of one of the following types:

  1. 1.

Leaf node: The node $t$ has no child nodes.

  2. 2.

Introduce node: The node $t$ has exactly one child node $t^{\prime}$ such that
$\chi(t)\setminus\chi(t^{\prime})$ consists of exactly one element.

  3. 3.

Forget node: The node $t$ has exactly one child node $t^{\prime}$ such that
$\chi(t^{\prime})\setminus\chi(t)$ consists of exactly one element.

  4. 4.

Join node: The node $t$ has exactly two child nodes $t_{1}$ and $t_{2}$ with
$\chi(t)=\chi(t_{1})=\chi(t_{2})$.

Additionally, the bags of the root and the leaves of $T$ are empty.

A tree decomposition of width $w$ for a graph with $n$ vertices can be
transformed into a nice one of width $w$ with $\mathcal{O}(wn)$ nodes in
fixed-parameter linear time [25].

$G$: $a$$b$$c$$d$ $\mathcal{T}$:
$\emptyset$$\\{a\\}$$t^{\mathcal{T}}_{a}$$\\{a,c\\}$$t^{\mathcal{T}}_{c}$$\\{a,c\\}$$\\{a,b,c\\}$$t^{\mathcal{T}}_{b}$$\\{a,b\\}$$\\{a\\}$$\emptyset$$\\{a,c\\}$$\\{a,c,d\\}$$t^{\mathcal{T}}_{d}$$\\{c,d\\}$$\\{d\\}$$\emptyset$

Figure 3: A graph $G$ and a nice tree decomposition $\mathcal{T}$ of $G$
rooted at the leftmost node

For any tree decomposition $\mathcal{T}$ and an element $v$ of some bag in
$\mathcal{T}$, we use the notation $t_{v}^{\mathcal{T}}$ to denote the unique
“topmost node” whose bag contains $v$ (i.e., $t_{v}^{\mathcal{T}}$ does not
have a parent whose bag contains $v$). Figure 3 depicts a graph and a nice
tree decomposition, where we also illustrate the $t^{\mathcal{T}}_{v}$
notation.

When we speak of the treewidth of an instance of Defensive Alliance, Defensive
AllianceF, Defensive AllianceFN, Exact Defensive Alliance, Exact Defensive
AllianceF or Exact Defensive AllianceFN, we mean the treewidth of the graph in
the instance. For an instance of Defensive AllianceFNC or Exact Defensive
AllianceFNC, we mean the treewidth of the primal graph.

##  3 Hardness of Defensive Alliance Parameterized by Treewidth

In this section, we prove the following theorem:

######  Theorem 7.

The following problems are all $\mathsf{W[1]}$-hard when parameterized by
treewidth: Defensive Alliance, Exact Defensive Alliance, Defensive AllianceF,
Exact Defensive AllianceF, Defensive AllianceFN, Exact Defensive AllianceFN,
Defensive AllianceFNC, and Exact Defensive AllianceFNC.

We prove hardness by providing a chain of FPT reductions from a
$\mathsf{W[1]}$-hard problem to the problems under consideration. Under the
widely held assumption that $\mathsf{FPT}\neq\mathsf{W[1]}$, this rules out
fixed-parameter tractable algorithms for these problems.

###  3.1 Hardness of Defensive Alliance with Forbidden, Necessary and
Complementary Vertices

To show $\mathsf{W[1]}$-hardness of Defensive AllianceFNC, we reduce from the
following problem [2], which is known to be $\mathsf{W[1]}$-hard [32]
parameterized by the treewidth of the graph:

Minimum Maximum Outdegree Input: A graph $G$, an edge weighting
$w:\operatorname{E}(G)\to\mathbb{N}^{+}$ given in unary and a positive integer
$r$ Question: Is there an orientation of the edges of $G$ such that, for each
$v\in\operatorname{V}(G)$, the sum of the weights of outgoing edges from $v$
is at most $r$?

######  Lemma 8.

Defensive AllianceFNC and Exact Defensive AllianceFNC, both parameterized by
the treewidth of the primal graph, are $\mathsf{W[1]}$-hard.

###### Proof.

Let an instance of Minimum Maximum Outdegree be given by a graph $G$, an edge
weighting $w:\operatorname{E}(G)\to\mathbb{N}^{+}$ in unary and a positive
integer $r$. From this we construct an instance of both Defensive AllianceFNC
and Exact Defensive AllianceFNC. An example is given in Figure 4. For each
$v\in\operatorname{V}(G)$, we define the set of new vertices
$H_{v}=\\{h^{v}_{1},\dots,h^{v}_{2r-1}\\}$, and for each
$(u,v)\in\operatorname{E}(G)$, we define the sets of new vertices
$V_{uv}=\\{u^{v}_{1},\dots,u^{v}_{w(u,v)}\\}$,
$V_{uv}^{\square}=\\{u^{v\square}_{1},\dots,u^{v\square}_{w(u,v)}\\}$,
$V_{vu}=\\{v^{u}_{1},\dots,v^{u}_{w(u,v)}\\}$ and
$V_{vu}^{\square}=\\{v^{u\square}_{1},\dots,v^{u\square}_{w(u,v)}\\}$. We now
define the graph $G^{\prime}$ with

$\displaystyle\operatorname{V}(G^{\prime})={}$
$\displaystyle\operatorname{V}(G)\cup\bigcup_{v\in\operatorname{V}(G)}H_{v}\cup\bigcup_{(u,v)\in\operatorname{E}(G)}(V_{uv}\cup
V_{uv}^{\square}\cup V_{vu}\cup V_{vu}^{\square}),$
$\displaystyle\operatorname{E}(G^{\prime})={}$ $\displaystyle\\{(v,h)\mid
v\in\operatorname{V}(G),\;h\in H_{v}\\}$ $\displaystyle{}\cup{}$
$\displaystyle\\{(u,x)\mid(u,v)\in\operatorname{E}(G),\;x\in V_{uv}\cup
V_{uv}^{\square}\\}$ $\displaystyle{}\cup{}$
$\displaystyle\\{(x,v)\mid(u,v)\in\operatorname{E}(G),\;x\in V_{vu}\cup
V_{vu}^{\square}\\}.$

We also define the set of complementary vertex pairs
$C=\\{(u^{v}_{i},v^{u}_{i})\mid(u,v)\in\operatorname{E}(G),\;1\leqslant
i\leqslant
w(u,v)\\}\cup\\{(v^{u}_{i},u^{v}_{i+1})\mid(u,v)\in\operatorname{E}(G),\;1\leqslant
i<w(u,v)\\}$. Finally, we define the set of necessary vertices
$V_{\triangle}=\operatorname{V}(G)\cup\bigcup_{v\in\operatorname{V}(G)}H_{v}$,
the set of forbidden vertices
$V_{\square}=\bigcup_{(u,v)\in\operatorname{E}(G)}(V_{uv}^{\square}\cup
V_{vu}^{\square})$ and $k={\lvert
V_{\triangle}\rvert}+\sum_{(u,v)\in\operatorname{E}(G)}w(u,v)$. We use $I$ to
denote $(G^{\prime},k,C,V_{\triangle},V_{\square})$, which is an instance of
Defensive AllianceFNC and also of Exact Defensive AllianceFNC.

$a$$b$$a^{b}_{1}$$a^{b}_{2}$$a^{b}_{3}$$a^{b\square}_{1}$$a^{b\square}_{2}$$a^{b\square}_{3}$$b^{a}_{1}$$b^{a}_{2}$$b^{a}_{3}$$b^{a\square}_{1}$$b^{a\square}_{2}$$b^{a\square}_{3}$$h^{a}_{1}$$h^{a}_{2}$$h^{a}_{3}$$h^{a}_{4}$$h^{a}_{5}$$h^{b}_{1}$$h^{b}_{2}$$h^{b}_{3}$$h^{b}_{4}$$h^{b}_{5}$
Figure 4: Result of our transformation on a sample Minimum Maximum Outdegree
instance with $r=3$ and two vertices $a,b$ that are connected by an edge of
weight $3$. Complementary vertex pairs are shown via dashed lines. Necessary
and forbidden vertices have a $\triangle$ and $\square$ symbol next to their
name, respectively.

Clearly $I$ can be computed in polynomial time. We now show that the treewidth
of the primal graph of $I$ depends only on the treewidth of $G$. We do so by
modifying an optimal tree decomposition $\mathcal{T}$ of $G$ as follows:

  1. 1.

For each $(u,v)\in\operatorname{E}(G)$, we take an arbitrary node whose bag
$B$ contains both $u$ and $v$ and add to its children a chain of nodes
$N_{1},\dots,N_{w(u,v)-1}$ such that the bag of $N_{i}$ is
$B\cup\\{u^{v}_{i},u^{v}_{i+1},v^{u}_{i},v^{u}_{i+1}\\}$.

  2. 2.

For each $(u,v)\in\operatorname{E}(G)$, we take an arbitrary node whose bag
$B$ contains $u$ and add to its children a chain of nodes
$N_{1},\dots,N_{w(u,v)}$ such that the bag of $N_{i}$ is
$B\cup\\{u^{v\square}_{i}\\}$.

  3. 3.

For each $(u,v)\in\operatorname{E}(G)$, we take an arbitrary node whose bag
$B$ contains $v$ and add to its children a chain of nodes
$N_{1},\dots,N_{w(u,v)}$ such that the bag of $N_{i}$ is
$B\cup\\{v^{u\square}_{i}\\}$.

  4. 4.

For each $v\in\operatorname{V}(G)$, we take an arbitrary node whose bag $B$
contains $v$ and add to its children a chain of nodes $N_{1},\dots,N_{r-1}$
such that the bag of $N_{i}$ is $B\cup\\{h^{v}_{i}\\}$.

It is easy to verify that the result is a valid tree decomposition of the
primal graph of $I$ and its width is at most the treewidth of $G$ plus four.

It remains to show that our reduction is correct. Obviously $I$ is a positive
instance of Defensive AllianceFNC iff it is a positive instance of Exact
Defensive AllianceFNC because the forbidden, necessary and complementary
vertices make sure that every solution of the Defensive AllianceFNC instance
$I$ has exactly $k$ elements. Hence we only consider Defensive AllianceFNC.

The intention is that for each orientation of $G$ we have a solution candidate
$S$ in $I$ such that an edge orientation from $u$ to $v$ entails
$V_{vu}\subseteq S$ and $V_{uv}\cap S=\emptyset$, and the other orientation
entails $V_{uv}\subseteq S$ and $V_{vu}\cap S=\emptyset$. For each vertex
$v\in\operatorname{V}(G)$ and every incident edge
$(v,u)\in\operatorname{E}(G)$ regardless of its orientation, the vertex $v$ is
attacked by the forbidden vertices $V_{vu}^{\square}$. So every vertex
$v\in\operatorname{V}(G)$ has as least as many attackers as the sum of the
weights of all incident edges. If in the orientation of $G$ all edges incident
to $v$ are incoming edges, then each attack on $v$ from $V_{vu}^{\square}$ can
be repelled by $V_{vu}$, since $V_{vu}\subseteq S$. Due to the fact that the
helper vertices $H_{v}$ consist of exactly $2r-1$ elements, $v$ can afford to
have outgoing edges of total weight at most $r$.

We claim that $(G,w,r)$ is a positive instance of Minimum Maximum Outdegree
iff $I$ is a positive instance of Defensive AllianceFNC.

_“Only if” direction._ Let $D$ be the directed graph given by an orientation
of the edges of $G$ such that for each vertex the sum of weights of outgoing
edges is at most $r$. The set
$S=V_{\triangle}\cup\\{v^{u}_{1},\dots,v^{u}_{w(u,v)}\mid(u,v)\in\operatorname{E}(D)\\}$
is a defensive alliance in $G^{\prime}$: Let $x$ be an arbitrary element of
$S$. If $x$ is an element of a set $H_{v}$ or $V_{uv}$, then the only neighbor
of $x$ in $G^{\prime}$ is a necessary vertex, so $x$ can trivially defend
itself; so suppose $x\in\operatorname{V}(G)$. Let the sum of the weights of
outgoing and incoming edges be denoted by $w^{x}_{\mathrm{out}}$ and
$w^{x}_{\mathrm{in}}$, respectively. The neighbors of $x$ that are also in $S$
consist of the elements of $H_{x}$ and all elements of sets $V_{xv}$ such that
$(v,x)\in\operatorname{E}(D)$. Hence, including itself, $x$ has
$2r+w^{x}_{\mathrm{in}}$ defenders in $G^{\prime}$. The attackers of $x$
consist of all elements of sets $V_{xv}$ such that
$(x,v)\in\operatorname{E}(D)$ (in total $w^{x}_{\mathrm{out}}$) and all
elements of sets $V_{xv}^{\square}$ such that either
$(v,x)\in\operatorname{E}(D)$ or $(x,v)\in\operatorname{E}(D)$ (in total
$w^{x}_{\mathrm{in}}+w^{x}_{\mathrm{out}}$). Hence $x$ has
$w^{x}_{\mathrm{in}}+2w^{x}_{\mathrm{out}}$ attackers in $G^{\prime}$. This
shows that $x$ has at least as many defenders as attackers, as by assumption
$w^{x}_{\mathrm{out}}\leqslant r$. Finally, it is easy to verify that ${\lvert
S\rvert}=k$, $V_{\square}\cap S=\emptyset$, $V_{\triangle}\subseteq S$, and
exactly one element of each pair of complementary vertices is in $S$.

_“If” direction._ Let $S$ be a solution of $I$. For every
$(u,v)\in\operatorname{E}(G)$, either $V_{uv}\subseteq S$ or $V_{vu}\subseteq
S$ due to the complementary vertex pairs. We define a directed graph $D$ by
$\operatorname{V}(D)=\operatorname{V}(G)$ and
$\operatorname{E}(D)=\\{(u,v)\mid V_{vu}\subseteq S\\}\cup\\{(v,u)\mid
V_{uv}\subseteq S\\}$. Suppose there is a vertex $x$ in $D$ whose sum of
weights of outgoing edges is greater than $r$. Clearly $x\in S$. Let the sum
of the weights of outgoing and incoming edges be denoted by
$w^{x}_{\mathrm{out}}$ and $w^{x}_{\mathrm{in}}$, respectively. The defenders
of $x$ in $G^{\prime}$ beside itself consist of the elements of $H_{x}$ and of
$w^{x}_{\mathrm{in}}$ neighbors due to incoming edges in $D$. These are in
total $2r+w^{x}_{\mathrm{in}}$ defenders. The attackers of $x$ in $G^{\prime}$
consist of $2w^{x}_{\mathrm{out}}$ elements (of the form $x^{v}_{i}$ as well
as $x^{v\square}_{i}$) due to outgoing edges in $D$ and $w^{x}_{\mathrm{in}}$
elements (of the form $x^{v\square}_{i}$) due to incoming edges. These are in
total $2w^{x}_{\mathrm{out}}+w^{x}_{\mathrm{in}}$ attackers. But then $x$ has
more attackers than defenders, as by assumption $w^{x}_{\mathrm{out}}>r$. ∎

###  3.2 Hardness of Defensive Alliance with Forbidden and Necessary Vertices

Next we present a transformation $\tau^{\text{FNC}}$ that eliminates
complementary vertex pairs by turning a Defensive AllianceFNC instance into an
equivalent Defensive AllianceFN instance. Along with $\tau^{\text{FNC}}$, we
define a function $\sigma_{I}^{\text{FNC}}$, for each Defensive AllianceFNC
instance $I$, such that the solutions of $I$ are in a one-to-one
correspondence with those of $\tau^{\text{FNC}}(I)$ in such a way that any two
solutions of $I$ have the same size iff the corresponding solutions of
$\tau^{\text{FNC}}(I)$ have the same size. We use these functions to obtain a
polynomial-time reduction from Defensive AllianceFNC to Defensive AllianceFN
as well as from Exact Defensive AllianceFNC to Exact Defensive AllianceFN.

Before we formally define our reduction, we briefly describe the intuition
behind the used gadgets. The gadget in Figure 5 adds neighbors
$a_{1},\dots,a_{n},a_{1}^{\square},\dots,a_{n}^{\square}$ to every vertex $a$,
which are so many that $a$ can only be in a solution if some of the new
neighbors are also in the solution. The new vertices are structured in such a
way that every solution must in fact either contain all of
$a,a_{1},\dots,a_{n}$ or none of them. Next, the gadget in Figure 6 is added
for every complementary pair $(a,b)$. This gadget is constructed in such a way
that every solution must either contain all of
$a_{n},a^{ab},a^{ab}_{1},\dots,a^{ab}_{n^{2}+n}$ or none of them, and the same
holds for $b_{n},b^{ab},b^{ab}_{1},\dots,b^{ab}_{n^{2}+n}$. By making the
vertex $\triangle^{ab}$ necessary, every solution must contain one of these
two sets. At the same time, the bound on the solution size makes sure that we
cannot afford to take both sets for any complementary pair.

######  Definition 9.

We define a function $\tau^{\text{FNC}}$, which assigns a Defensive AllianceFN
instance to each Defensive AllianceFNC instance
$I=(G,k,V_{\square},V_{\triangle},C)$. For this, we use $n$ to denote
${\lvert\operatorname{V}(G)\rvert}$ and first define a function

$\sigma_{I}^{\text{FNC}}:x\mapsto x\cdot(n+1)+{\lvert
C\rvert}\cdot(n^{2}+n+2).$

For each $v\in\operatorname{V}(G)$, we introduce the following sets of new
vertices.

$\displaystyle Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$ $\displaystyle{}=\\{v_{1},\dots,v_{n}\\}$
$\displaystyle Y_{v}^{\square}$
$\displaystyle{}=\\{v^{\square}_{1},\dots,v^{\square}_{n}\\}$

Next, for each $(a,b)\in C$, we introduce new vertices $a^{ab}$, $b^{ab}$ and
$\triangle^{ab}$ as well as, for any $x\in\\{a,b\\}$, the following sets of
new vertices.

$\displaystyle Z^{ab}_{x{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}}$
$\displaystyle{}=\\{x^{ab}_{1},\dots,x^{ab}_{n^{2}+n}\\}$ $\displaystyle
Z^{ab}_{x\square}$
$\displaystyle{}=\\{x^{ab\square}_{1},\dots,x^{ab\square}_{n^{2}+n}\\}$

We use the notation $u\oplus v$ to denote the set of edges $\\{(u,v),$
$(u,u^{\square}),$ $(v,v^{\square}),$ $(u,v^{\square}),$ $(v,u^{\square})\\}$.

$a$$a_{1}$$a_{2}$$\cdots$$a_{n}$$a_{1}^{\square}$$a_{2}^{\square}$$\cdots$$a_{n}^{\square}$
Figure 5: Gadget for each vertex $a$ of the original graph in the reduction
from Secure SetFNC to Secure SetFN. The vertex $a$ may have additional
neighbors from the original graph, and the vertices $a_{n}$ and
$a_{n}^{\square}$ may have additional neighbors as depicted in Figure 6.
$a^{ab}$$a_{n}$$a_{1}^{ab}$$a_{2}^{ab}$$\cdots$$a_{n^{2}+n}^{ab}$$a_{n}^{\square}$$a_{1}^{ab\square}$$a_{2}^{ab\square}$$\cdots$$a_{n^{2}+n}^{ab\square}$$\triangle^{ab}$$b^{ab}$$b_{n^{2}+n}^{ab}$$\cdots$$b_{2}^{ab}$$b_{1}^{ab}$$b_{n}$$b_{n^{2}+n}^{ab\square}$$\dots$$b_{2}^{ab\square}$$b_{1}^{ab\square}$$b_{n}^{\square}$
Figure 6: Gadget for each pair of complementary vertices $(a,b)$ in the
reduction from Secure SetFNC to Secure SetFN. The vertices $a_{n}$,
$a_{n}^{\square}$, $b_{n}$ and $b_{n}^{\square}$ have additional neighbors as
depicted in Figure 5.

Now we define the Defensive AllianceFN instance
$\tau^{\text{FNC}}(I)=(G^{\prime},k^{\prime},V_{\square}^{\prime},V_{\triangle}^{\prime})$,
where $k^{\prime}=\sigma_{I}^{\text{FNC}}(k)$,
$V_{\square}^{\prime}=V_{\square}\cup\bigcup_{v\in\operatorname{V}(G)}Y_{v}^{\square}\cup\bigcup_{(a,b)\in
C}(Z^{ab}_{a\square}\cup Z^{ab}_{b\square})$,
$V_{\triangle}^{\prime}=V_{\triangle}\cup\bigcup_{(a,b)\in
C}\\{\triangle^{ab}\\}$ and $G^{\prime}$ is the graph defined by

$\displaystyle\operatorname{V}(G^{\prime})=\operatorname{V}(G)$
$\displaystyle{}\cup\bigcup_{v\in\operatorname{V}(G)}(Y_{v}^{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cup
Y_{v}^{\square})\cup{}$ $\displaystyle{}\cup\bigcup_{(a,b)\in
C}\big{(}\\{\triangle^{ab},a^{ab},b^{ab}\\}\cup
Z^{ab}_{a{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}}\cup Z^{ab}_{b{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}}\cup
Z^{ab}_{a\square}\cup Z^{ab}_{b\square}\big{)},$
$\displaystyle\operatorname{E}(G^{\prime})=\operatorname{E}(G)$
$\displaystyle{}\cup\bigcup_{v\in\operatorname{V}(G)}\big{(}(\\{v\\}\times
Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}})\cup(\\{v\\}\times
Y_{v}^{\square})\cup\bigcup_{1\leqslant i<n}v_{i}\oplus v_{i+1}\big{)}\cup{}$
$\displaystyle{}\cup\bigcup_{(a,b)\in
C}\bigcup_{x\in\\{a,b\\}}\big{(}\\{(\triangle^{ab},x^{ab})\\}\cup(\\{x^{ab}\\}\times
Z^{ab}_{x{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}})\cup{}$
$\displaystyle\phantom{{}\cup\bigcup_{(a,b)\in
C}\bigcup_{x\in\\{a,b\\}}\big{(}}{}\cup x_{n}\oplus
x_{1}^{ab}\cup\bigcup_{1\leqslant i<n^{2}+n}x_{i}^{ab}\oplus
x_{i+1}^{ab}\big{)}.$

We illustrate our construction in Figures 5 and 6.

######  Lemma 10.

Let $I=(G,k,V_{\square},V_{\triangle},C)$ be a Defensive AllianceFNC instance,
let $A$ be the set of solutions of $I$ and let $B$ be the set of solutions of
the Defensive AllianceFN instance $\tau^{\text{FNC}}(I)$. There is a bijection
$f:A\to B$ such that ${\lvert f(S)\rvert}=\sigma_{I}^{\text{FNC}}({\lvert
S\rvert})$ holds for every $S\in A$.

###### Proof.

We use the same auxiliary notation as in Definition 9 and we define $f$ as
$S\mapsto S\cup\bigcup_{v\in S}Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cup\bigcup_{(a,b)\in C,\,x\in
S\cap\\{a,b\\}}(\\{\triangle^{ab},x^{ab}\\}\cup
Z^{ab}_{x{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}})$. For every $S\in A$, we thus obtain ${\lvert
f(S)\rvert}=\sigma_{I}^{\text{FNC}}({\lvert S\rvert})$, and we first show that
indeed $f(S)\in B$.

Let $S\in A$ and let $S^{\prime}$ denote $f(S)$. Obviously $S^{\prime}$
satisfies $V_{\square}^{\prime}\cap S^{\prime}=\emptyset$ and
$V_{\triangle}^{\prime}\subseteq S^{\prime}$. To see that $S^{\prime}$ is a
defensive alliance in $G^{\prime}$, let $x$ be an arbitrary element of
$S^{\prime}$. If $x\notin S$, then $x$ clearly has as least as many neighbors
in $S^{\prime}$ as neighbors not in $S^{\prime}$ by construction of $f$, so
suppose $x\in S$. There is a defense $\mu:N_{G}[x]\setminus S\to N_{G}[x]\cap
S$ since $S$ is a defensive alliance in $G$. We use this to construct a
defense $\mu^{\prime}:N_{G^{\prime}}[x]\setminus S^{\prime}\to
N_{G^{\prime}}[x]\cap S^{\prime}$. For any attacker $v$ of $x$ in
$G^{\prime}$, we distinguish two cases.

  * •

If $v$ is some $x_{i}^{\square}\in Y_{x}^{\square}$ for some
$x\in\operatorname{V}(G)$, we set $\mu^{\prime}(v)=x_{i}$. This element is in
$N_{G^{\prime}}[x]$ by construction.

  * •

Otherwise $v$ is in $N_{G}[x]\setminus S$ (by our construction of
$S^{\prime}$). Since the codomain of $\mu$ is a subset of the codomain of
$\mu^{\prime}$, we may set $\mu^{\prime}(v)=\mu(v)$.

Since $\mu^{\prime}$ is injective, each attack on $x$ in $G^{\prime}$ can be
repelled by $S^{\prime}$. Hence $S^{\prime}$ is a defensive alliance in
$G^{\prime}$.

Clearly $f$ is injective. It remains to show that $f$ is surjective. Let
$S^{\prime}$ be a solution of $\tau^{\text{FNC}}(I)$. First we make the
following observations for each $v\in\operatorname{V}(G)$:

  * •

If $v\in S^{\prime}$, then $Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cap S^{\prime}\neq\emptyset$ due to
Observation 3, since $Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cup Y_{v}^{\square}$ contains a
majority of neighbors of $v$, and the vertices in $Y_{v}^{\square}$ are
forbidden.

  * •

For each $v^{ab}\in S^{\prime}$, where $(a,b)\in C$ such that $v=a$ or $v=b$,
it holds that $Z^{ab}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}}\cap S^{\prime}\neq\emptyset$ again
due to Observation 3.

  * •

If $S^{\prime}$ contains an element of $Y_{v}^{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then
$\\{v\\}\cup Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\cup\bigcup_{(v,z)\in
C}Z^{vz}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}}\cup\bigcup_{(z,v)\in
C}Z^{zv}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}}\subseteq S^{\prime}$ by repeated applications of
Observation 4. To see this, note in particular that $N(v_{n})$ can be
partitioned into the two equal-sized sets
$\\{v,v_{n-1}\\}\cup\\{v^{vz}_{1}\mid(v,z)\in
C\\}\cup\\{v^{zv}_{1}\mid(z,v)\in C\\}$ and
$\\{v_{n-1}^{\square},v_{n}^{\square}\\}\cup\\{v^{vz\square}_{1}\mid(v,z)\in
C\\}\cup\\{v^{zv\square}_{1}\mid(z,v)\in C\\}$, and all vertices in the latter
set are forbidden.

  * •

If $S^{\prime}$ contains an element of $Z^{ab}_{v{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}}$, where $(a,b)\in
C$ such that $v=a$ or $v=b$, then $\\{v^{ab}\\}\cup
Y_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\cup\bigcup_{(v,z)\in
C}Z^{vz}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}}\cup\bigcup_{(z,v)\in
C}Z^{zv}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}}\subseteq S^{\prime}$ for similar reasons.

It follows that for each $v\in\operatorname{V}(G)$, $S^{\prime}$ contains
either all or none of $\\{v\\}\cup Y_{v}^{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\cup\bigcup_{(v,z)\in C}\big{(}\\{v^{vz}\\}\cup
Z^{vz}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}}\big{)}\cup\bigcup_{(z,v)\in
C}\big{(}\\{v^{zv}\\}\cup Z^{zv}_{v{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}}\big{)}$.

For every $(a,b)\in C$, $S^{\prime}$ contains $a^{ab}$ or $b^{ab}$, since
$\triangle^{ab}\in S^{\prime}$, whose neighbors are $a^{ab}$ and $b^{ab}$. It
follows that ${\lvert S^{\prime}\rvert}>{\lvert C\rvert}\cdot(n^{2}+n+2)$ even
if $S^{\prime}$ contains only one of each $(a,b)\in C$. If, for some $(a,b)\in
C$, $S^{\prime}$ contained both $a$ and $b$, we could derive a contradiction
to ${\lvert
S^{\prime}\rvert}\leqslant\sigma_{I}^{\text{FNC}}(k)=k\cdot(n+1)+{\lvert
C\rvert}\cdot(n^{2}+n+2)$ because then ${\lvert S^{\prime}\rvert}>({\lvert
C\rvert}+1)\cdot(n^{2}+n+2)>\sigma_{I}^{\text{FNC}}(k)$. So $S^{\prime}$
contains either $a$ or $b$ for any $(a,b)\in C$.

We construct $S=S^{\prime}\cap\operatorname{V}(G)$ and observe that
$S^{\prime}=f(S)$, $V_{\triangle}\subseteq S$, $V_{\square}\cap S=\emptyset$,
and ${\lvert S\cap\\{a,b\\}\rvert}=1$ for each $(a,b)\in C$. It remains to
show that $S$ is a defensive alliance in $G$. Let $x$ be an arbitrary element
of $S$. We observe that $N_{G^{\prime}}[x]\cap S^{\prime}=(N_{G}[x]\cap S)\cup
Y_{x}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$ and similarly $N_{G^{\prime}}[x]\setminus
S^{\prime}=(N_{G}[x]\setminus S)\cup Y_{x}^{\square}$. Since the cardinality
of each set $Y_{x}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$ is equal to the cardinality of $Y_{x}^{\square}$,
this implies ${\lvert N_{G^{\prime}}[x]\cap S^{\prime}\rvert}-{\lvert
N_{G}[x]\cap S\rvert}={\lvert N_{G^{\prime}}[x]\setminus
S^{\prime}\rvert}-{\lvert N_{G}[x]\setminus S\rvert}$. Since $S^{\prime}$ is a
defensive alliance in $G^{\prime}$ and $x\in S^{\prime}$, it holds that
${\lvert N_{G^{\prime}}[x]\cap S^{\prime}\rvert}\geqslant{\lvert
N_{G^{\prime}}[x]\setminus S^{\prime}\rvert}$. We conclude that ${\lvert
N_{G}[x]\cap S\rvert}\geqslant{\lvert N_{G}[x]\setminus S\rvert}$. Hence $S$
is a defensive alliance in $G$. ∎

To obtain the hardness result for Defensive AllianceFN parameterized by
treewidth, it remains to show that the reduction specified by
$\tau^{\text{FNC}}$ preserves bounded treewidth.

######  Lemma 11.

Defensive AllianceFN, parameterized by the treewidth of the graph, is
$\mathsf{W[1]}$-hard.

###### Proof.

Let $I$ be a Defensive AllianceFNC instance whose primal graph we denote by
$G$. We obtain an equivalent Defensive AllianceFN instance
$\tau^{\text{FNC}}(I)$, whose graph we denote by $G^{\prime}$. This reduction
is correct, as shown in Lemma 10. It remains to show that the treewidth of
$G^{\prime}$ is bounded by a function of the treewidth of $G$. Let
$\mathcal{T}$ be an optimal nice tree decomposition of $G$. We build a tree
decomposition $\mathcal{T}^{\prime}$ of $G^{\prime}$ by modifying a copy of
$\mathcal{T}$ in the following way: For each vertex $v\in\operatorname{V}(G)$,
we add $v_{n}$ and $v_{n}^{\square}$ to every bag containing $v$. Then we pick
an arbitrary node $t$ in $\mathcal{T}$ whose bag contains $v$, and we add new
children $N_{1},\dots,N_{n-1}$ to $t$ such that the bag of $N_{i}$ is
$\\{v,v_{i},v_{i}^{\square},v_{i+1},v_{i+1}^{\square}\\}$. Next, for every
pair $(a,b)$ of complementary vertices, we pick an arbitrary node $t$ in
$\mathcal{T}$ whose bag $B$ contains both $a_{n}$ and $b_{n}$, and we add a
chain of nodes $N_{1},\dots,N_{2n^{2}+2n-1}$ between $t$ and its parent such
that, for $1\leqslant i<n^{2}+n$, the bag of $N_{i}$ is
$B\cup\\{a^{ab},a_{i}^{ab},a_{i}^{ab\square},a_{i+1}^{ab},a_{i+1}^{ab\square}\\}$,
the bag of $N_{n^{2}+n}$ is $B\cup\\{a^{ab},b^{ab},\triangle^{ab}\\}$, and the
bag of $N_{n^{2}+n+i}$ is
$B\cup\\{b^{ab},b_{n^{2}+n+1-i}^{ab},b_{n^{2}+n+1-i}^{ab\square},b_{n^{2}+n-i}^{ab},b_{n^{2}+n-i}^{ab\square}\\}$.
It is easy to verify that $\mathcal{T}^{\prime}$ is a valid tree decomposition
of $G^{\prime}$. Furthermore, the width of $\mathcal{T}^{\prime}$ is at most
three times the width of $\mathcal{T}$ plus five. ∎

The instances of Defensive AllianceFNC are identical to the instances of the
exact variant, so $\tau^{\text{FNC}}$ is also applicable to the exact case. In
fact it turns out that this gives us also a reduction from Exact Defensive
AllianceFNC to Exact Defensive AllianceFN.

######  Lemma 12.

Exact Defensive AllianceFN, parameterized by the treewidth of the graph, is
$\mathsf{W[1]}$-hard.

###### Proof.

Let $I$ and $I^{\prime}=\tau^{\text{FNC}}(I)$ be our Exact Defensive
AllianceFNC and Exact Defensive AllianceFN instances, respectively, and let
$k$ and $k^{\prime}$ denote their respective solution sizes. By Lemma 10,
there is a bijection $f$ between the solutions of $I$ and the solutions of
$I^{\prime}$ such that, for every solution $S$ of $I$, $f(S)$ has
$\sigma_{I}^{\text{FNC}}(k)=k^{\prime}$ elements, and for every solution
$S^{\prime}$ of $I^{\prime}$, $f^{-1}(S^{\prime})$ has $k$ elements since
$\sigma_{I}^{\text{FNC}}$ is invertible. We can derive the bound on the
treewidth of $I^{\prime}$ as in the proof of Lemma 11. ∎

###  3.3 Hardness of Defensive Alliance with Forbidden Vertices

Now we present a transformation $\tau^{\text{FN}}$ that eliminates necessary
vertices. Our transformation not only operates on a problem instance, but also
requires an ordering $\preceq$ of the non-forbidden vertices of the graph. Our
reductions based on $\tau^{\text{FN}}$ will be correct for every ordering
${\preceq}$, but in order to keep the treewidth of the resulting problem
instance bounded by the treewidth of the original problem instance, we must
choose a suitable ordering. We will describe this in detail later; for now we
can consider ${\preceq}$ to be an arbitrary ordering of the non-forbidden
vertices.

$a$$g_{a}$$h_{a}$$a^{\prime}$$b$ Figure 7: Result of the transformation
$\tau^{\text{FN}}{}$ applied to an example graph with two adjacent vertices
$a$ and $b$, where $b$ is necessary. Every solution in the depicted graph
contains $a^{\prime}$, $h_{a}$ and $b$.

Before formally defining the transformation $\tau^{\text{FN}}$, we refer to
Figure 7, which shows the result for a simple example graph with only two
vertices $a$ and $b$, of which $b$ is necessary. The basic idea is that the
vertex $a^{\prime}$ must be in every solution $S$: If $a$ or any vertex to the
left of $a$ is in $S$, it eventually forces $a^{\prime}$ to be in $S$ as well.
Likewise, if $b$ or any vertex to the right of $b$ is in $S$, it also forces
$a^{\prime}$ to be in $S$. Once $a^{\prime}\in S$, the construction to the
right of $a^{\prime}$ makes sure that $b\in S$. We will generalize this to
instances containing more vertices so that every necessary vertex as well as
the primed copy of each non-necessary vertex is in every solution.

######  Definition 13.

We define a function $\tau^{\text{FN}}$, which assigns a Defensive AllianceF
instance to each pair $(I,{\preceq})$, where
$I=(G,k,V_{\square},V_{\triangle})$ is a Defensive AllianceFN instance and
${\preceq}$ is an ordering of the non-forbidden elements of
$\operatorname{V}(G)$. For this, let $V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$ denote
$\operatorname{V}(G)\setminus(V_{\square}\cup V_{\triangle})$. We use $n$ to
denote ${\lvert\operatorname{V}(G)\rvert}$, and we first define a function
$\sigma_{I}^{\text{FN}}:x\mapsto(n+3)\cdot(x+{\lvert V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\rvert})-{\lvert
V_{\triangle}\rvert}$. We use $H$ to denote the set of new vertices
$\\{v^{\prime},g_{v},h_{v},g_{v}^{\square},h_{v}^{\square}\mid v\in
V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\\}$. The intention is for each $g_{v}^{\square}$ and $h_{v}^{\square}$
to be forbidden, for each $v^{\prime}$ and $h_{v}$ to be in every solution,
and for $g_{v}$ to be in a solution iff $v$ is in it at the same time. We
write $V^{+}$ to denote $V_{\triangle}\cup V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\cup\\{v^{\prime}\mid v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\\}$; for each $v\in V^{+}$, we use
$A_{v}$ to denote the set of new vertices
$\\{v_{1},\dots,v_{n+1},v_{1}^{\square},\dots,v_{n+1}^{\square}\\}$, and we
use shorthand notation $A_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}=\\{v_{1},\dots,v_{n+1}\\}$ and
$A_{v}^{\square}=\\{v_{1}^{\square},\dots,v_{n+1}^{\square}\\}$. The intention
is for each $v_{i}^{\square}$ to be forbidden and for each $v_{i}$ to be in a
solution iff $v$ is in it at the same time. We use the notation $u\oplus v$ to
denote the set of edges
$\\{(u,v),(u,u^{\square}),(v,v^{\square}),(u,v^{\square}),(v,u^{\square})\\}$.
For any vertex $v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cup V_{\triangle}$, we define
$p(v)=v$ if $v\in V_{\triangle}$ and $p(v)=v^{\prime}$ if $v\in
V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}$. Let $P$ be the set consisting of all pairs $(p(u),p(v))$ such that
$v$ is the direct successor of $u$ according to ${\preceq}$. Now we define
$\tau^{\text{FN}}(I,{\preceq})=(G^{\prime},k^{\prime},V_{\square}^{\prime})$,
where
$V^{\prime}_{\square}=V_{\square}\cup\\{g_{v}^{\square},h_{v}^{\square}\mid
v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\\}\cup\bigcup_{v\in V^{+}}A_{v}^{\square}$,
$k^{\prime}=\sigma_{I}^{\text{FN}}(k)$, and $G^{\prime}$ is the graph defined
by

$\displaystyle\operatorname{V}(G^{\prime})={}$
$\displaystyle\operatorname{V}(G)\cup H\cup\bigcup_{v\in V^{+}}A_{v},$
$\displaystyle\operatorname{E}(G^{\prime})={}$
$\displaystyle\operatorname{E}(G)\cup\\{(v,v_{i}),(v,v_{i}^{\square})\mid v\in
V^{+},\;1\leqslant i\leqslant n+1\\}$ $\displaystyle{}\cup{}$
$\displaystyle\bigcup_{v\in V^{+},\;1\leqslant i\leqslant n}v_{i}\oplus
v_{i+1}\cup\bigcup_{(u,v)\in P}u_{n+1}\oplus v_{1}$ $\displaystyle{}\cup{}$
$\displaystyle\bigcup_{v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}}v_{n+1}\oplus
g_{v}\cup\\{(v^{\prime},g_{v}),(v^{\prime},h_{v}),(g_{v},h_{v}),(g_{v},h_{v}^{\square})\mid
v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\\}.$

We illustrate our construction in Figure 8 and 9.

$a$$a_{1}$$a_{2}$$\cdots$$a_{n}$$a_{n+1}$$a_{1}^{\square}$$a_{2}^{\square}$$a_{n}^{\square}$$a_{n+1}^{\square}$$g_{a}$$g_{a}^{\square}$$h_{a}^{\square}$$h_{a}$$a^{\prime}$
Figure 8: Illustration of the gadget that makes sure that every solution
containing $a$ also contains $f_{a}$, $g_{a}$ and $a^{\prime}$. The vertex $a$
is a non-necessary, non-forbidden vertex from the Secure SetFN instance and
may have other neighbors from this instance. The vertex $a^{\prime}$
additionally has the neighbors depicted in Figure 9.
$x$$x_{1}$$x_{2}$$\cdots$$x_{n}$$x_{n+1}$$x_{1}^{\square}$$x_{2}^{\square}$$x_{n}^{\square}$$x_{n+1}^{\square}$$y$$y_{1}$$\cdots$$y_{n+1}$$y_{1}^{\square}$$y_{n+1}^{\square}$$a^{\prime}$$a^{\prime}_{1}$$\cdots$$a^{\prime}_{n+1}$$a^{\prime\square}_{1}$${a^{\prime\square}_{n+1}}$$b^{\prime}$$b^{\prime}_{1}$$\cdots$$b^{\prime}_{n+1}$$b^{\prime\square}_{1}$$b^{\prime\square}_{n+1}$
Figure 9: Illustration of the gadget that makes sure that every solution
contains all necessary vertices if it contains some necessary vertex or if it
contains $v^{\prime}$ for some non-necessary vertex $v$. Here we assume there
are the four vertices $a,b,x,y$, among which $x$ and $y$ are necessary, and we
use the ordering $x\preceq y\preceq a\preceq b$.

We now prove that $\tau^{\text{FN}}$ yields a correct reduction for any
ordering $\preceq$.

######  Lemma 14.

Let $I=(G,k,V_{\square},V_{\triangle})$ be a Defensive AllianceFN instance,
let ${\preceq}$ be an ordering of $\operatorname{V}(G)\setminus V_{\square}$,
let $A$ be the set of solutions of $I$ and let $B$ be the set of solutions of
the Defensive AllianceF instance $\tau^{\text{FN}}(I,{\preceq})$. There is a
bijection $f:A\to B$ such that ${\lvert
f(S)\rvert}=\sigma_{I}^{\text{FN}}({\lvert S\rvert})$ holds for every $S\in
A$.

###### Proof.

We use the same auxiliary notation as in Definition 13 and we define $f$ as

$f(S)=S\cup\bigcup_{v\in S}A_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cup\\{v^{\prime},h_{v}\mid v\in
V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\\}\cup\bigcup_{v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}}A_{v^{\prime}}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\cup\\{g_{v}\mid v\in S\cap
V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\\}.$

For every $S\in A$, we thus obtain ${\lvert f(S)\rvert}={\lvert
S\rvert}+{\lvert S\rvert}(n+1)+2{\lvert V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\rvert}+{\lvert
V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\rvert}\cdot(n+1)+({\lvert S\rvert}-{\lvert
V_{\triangle}\rvert})=\sigma_{I}^{\text{FN}}({\lvert S\rvert})$, and we first
show that indeed $f(S)\in B$.

Let $S\in A$ and let $S^{\prime}$ denote $f(S)$. Obviously $S^{\prime}$
satisfies $V_{\square}^{\prime}\cap S^{\prime}=\emptyset$. To see that
$S^{\prime}$ is a defensive alliance in $G^{\prime}$, let $x$ be an arbitrary
element of $S^{\prime}$. If $x\in S$, then there is a defense
$\mu:N_{G}[x]\setminus S\to N_{G}[x]\cap S$ since $S$ is a defensive alliance
in $G$. We use this to construct a defense
$\mu^{\prime}:N_{G^{\prime}}[x]\setminus S^{\prime}\to N_{G^{\prime}}[x]\cap
S^{\prime}$. For any attacker $a$ of $x$ in $G^{\prime}$, we distinguish the
following cases:

  * •

If $a$ is some $v_{i}^{\square}\in A_{v}^{\square}$ for some $v\in V^{+}$,
then $x$ is either $v_{i}$ or a neighbor of $v_{i}$, all of which are in
$S^{\prime}$, and we set $\mu^{\prime}(a)=v_{i}$.

  * •

Similarly, if $a$ is $g_{v}^{\square}$ for some $v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then we set
$\mu^{\prime}(a)=g_{v}$.

  * •

If $a$ is $h_{v}^{\square}$ for some $v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then $x=g_{v}$
and we set $\mu^{\prime}(a)=h_{v}$.

  * •

If $a$ is $g_{v}$ for some $v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then $x$ is either $v^{\prime}$
or $h_{v}$, which is not used for repelling any other attack because
$h_{v}^{\square}$ cannot attack $x$, so we set $\mu^{\prime}(a)=h_{v}$.

  * •

Otherwise $a$ is in $N_{G}[x]\setminus S$ (by our construction of
$S^{\prime}$). Since the codomain of $\mu$ is a subset of the codomain of
$\mu^{\prime}$, we may set $\mu^{\prime}(a)=\mu(a)$.

Since $\mu^{\prime}$ is injective, each attack on $x$ in $G^{\prime}$ can be
repelled by $S^{\prime}$. Hence $S^{\prime}$ is a defensive alliance in
$G^{\prime}$.

Clearly $f$ is injective. It remains to show that $f$ is surjective. Let
$S^{\prime}$ be a solution of $\tau^{\text{FN}}(I,{\preceq})$. We first show
that $V_{\triangle}\cup\\{v^{\prime},h_{v}\mid v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\\}\subseteq
S^{\prime}$:

  * •

If $S^{\prime}$ contains some $v\in V^{+}$, then $S^{\prime}$ contains an
element of $A_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$ by Observation 3.

  * •

If $S^{\prime}$ contains an element of $A_{v}^{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$ for some $v\in
V^{+}$, then $\\{v\\}\cup A_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\subseteq S^{\prime}$ by Observation
4.

  * •

If $v_{n+1}\in S^{\prime}$ for some $v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then $g_{v}\in
S^{\prime}$ for the same reason.

  * •

Furthermore, if $S^{\prime}$ contains an element of
$A_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$ for some $v\in V_{\triangle}\cup\\{v^{\prime}\mid
v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\\}$, then also $A_{u}^{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\subseteq
S^{\prime}$ for every $u\in V_{\triangle}\cup\\{v^{\prime}\mid v\in
V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size
pt{}}}}\\}$ for the same reason.

  * •

If $g_{v}\in S^{\prime}$ for some $v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then
$\\{h_{v},v^{\prime},v_{n+1}\\}\subseteq S^{\prime}$ by Observation 4.

  * •

If $h_{v}\in S^{\prime}$ for some $v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$, then
$a^{\prime}\in S^{\prime}$ because at least $g_{v}$ or $v^{\prime}$ must be in
$S^{\prime}$ and the former implies $v^{\prime}\in S^{\prime}$ as we have
seen.

  * •

Since $S^{\prime}$ is nonempty, the previous observations show that for every
$v\in V_{\triangle}\cup\\{v^{\prime}\mid v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}\\}$ it holds that
$\\{v\\}\cup A_{v}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\subseteq S^{\prime}$. Finally, we show that
$\\{h_{v}\mid v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\\}\subseteq S^{\prime}$. Suppose, for the sake of
contradiction, that there is some $v\in V_{\mathchoice{{\tf@size
pt{}}}{{\tf@size pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$ such that
$h_{v}\notin S^{\prime}$. We have seen that the latter can only be the case if
$g_{v}\notin S^{\prime}$, and we know that $v^{\prime}\in S^{\prime}$. We
obtain the contradiction that $v^{\prime}$ is attacked by $g_{v}$, $h_{v}$ and
$A_{v^{\prime}}^{\square}$, whereas its only defenders are $v^{\prime}$ itself
and $A_{v^{\prime}}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$.

Let $S=S^{\prime}\cap\operatorname{V}(G)$. By the previous observations, it is
easy to see that $S^{\prime}=f(S)$. It remains to show that $S$ is a defensive
alliance in $G$. Let $x$ be an arbitrary element of $S$. We observe that
$N_{G^{\prime}}[x]\cap S^{\prime}=(N_{G}[x]\cap S)\cup
A_{x}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$ and similarly $N_{G^{\prime}}[x]\setminus
S^{\prime}=(N_{G}[x]\setminus S)\cup A_{v}^{\square}$. Since ${\lvert
A_{x}^{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}\rvert}={\lvert A_{x}^{\square}\rvert}$, this implies
${\lvert N_{G^{\prime}}[x]\cap S^{\prime}\rvert}-{\lvert N_{G}[x]\cap
S\rvert}={\lvert N_{G^{\prime}}[x]\setminus S^{\prime}\rvert}-{\lvert
N_{G}[x]\setminus S\rvert}$. Since $S^{\prime}$ is a defensive alliance in
$G^{\prime}$ and $x\in S^{\prime}$, it holds that ${\lvert
N_{G^{\prime}}[x]\cap S^{\prime}\rvert}\geqslant{\lvert
N_{G^{\prime}}[x]\setminus S^{\prime}\rvert}$. We conclude that ${\lvert
N_{G}[x]\cap S\rvert}\geqslant{\lvert N_{G}[x]\setminus S\rvert}$. Hence $S$
is a defensive alliance in $G$. ∎

Given an ordering ${\preceq}$, clearly $\tau^{\text{FN}}(I,\preceq)$ is
computable in polynomial time. We can thus easily obtain a reduction from
Defensive AllianceFN to Defensive AllianceF by first computing an arbitrary
ordering ${\preceq}$ of the non-forbidden vertices. We next show that by
choosing $\preceq$ appropriately, this amounts to an FPT reduction that
preserves bounded treewidth.

######  Lemma 15.

Defensive AllianceF, parameterized by the treewidth of the graph, is
$\mathsf{W[1]}$-hard.

###### Proof.

Let $I=(G,k,V_{\square},V_{\triangle})$ be a Defensive AllianceFN instance and
let $\mathcal{T}$ be an optimal nice tree decomposition of $G$. We can compute
such a tree decomposition in FPT time [6]. Let ${\preceq}$ be the ordering of
the elements of $V_{\triangle}\cup V_{\mathchoice{{\tf@size pt{}}}{{\tf@size
pt{}}}{{\sf@size pt{}}}{{\ssf@size pt{}}}}$ that is obtained in linear time by
doing a post-order traversal of $\mathcal{T}$ and sequentially recording the
elements that occur for the last time in the current bag. We obtain the
Defensive AllianceF instance $\tau^{\text{FN}}(I,\preceq)$, whose graph we
denote by $G^{\prime}$. This reduction is correct, as shown in Lemma 14, and
computable in FPT time. It remains to show that the treewidth of $G^{\prime}$
is bounded by a function of the treewidth of $G$. To this end, we use
$\mathcal{T}$ to build a tree decomposition $\mathcal{T}^{\prime}$ of
$G^{\prime}$. We initially set $\mathcal{T}^{\prime}:=\mathcal{T}$ and modify
it by the following steps:

  1. 1.

For each $v\in V_{\mathchoice{{\tf@size pt{}}}{{\tf@size pt{}}}{{\sf@size
pt{}}}{{\ssf@size pt{}}}}$, we add $g_{v}$, $g_{v}^{\square}$, $h_{v}$,
$h_{v}^{\square}$ and $v^{\prime}$ to the bag of
$t_{v}^{\mathcal{T}^{\prime}}$. Note that afterwards
$t_{v}^{\mathcal{T}^{\prime}}=t_{v^{\prime}}^{\mathcal{T}^{\prime}}$. After
this step we increased the width of $\mathcal{T}^{\prime}$ by at most five.

  2. 2.

For each $v\in V^{+}$, we use $B_{v}$ to denote the bag of
$t_{v}^{\mathcal{T}^{\prime}}$ and replace $t_{v}^{\mathcal{T}^{\prime}}$ by a
chain of nodes $N_{1},\dots,N_{n}$, where $N_{n}$ is the topmost node and the
bag of $N_{i}$ is
$B_{v}\cup\\{v_{i},v_{i}^{\square},v_{i+1},v_{i+1}^{\square}\\}$. After this
step we increased the width of $\mathcal{T}^{\prime}$ by at most nine. Note
that the bag of the new node $t_{v}^{\mathcal{T}^{\prime}}$ now contains
$v_{i+1}$ and $v_{i+1}^{\square}$. We have so far covered all edges except the
ones connecting elements of two different sets $A_{x}$ and $A_{y}$ for
$(x,y)\in P$.

  3. 3.

For every $(u,v)\in P$, we add $v_{1}$ and $v_{1}^{\square}$ into the bag of
every node between (and including) $t_{u}^{\mathcal{T}^{\prime}}$ and
$t_{v_{1}}^{\mathcal{T}^{\prime}}$. Note that this preserves connectedness and
afterwards the bag of $t_{u}^{\mathcal{T}^{\prime}}$ contains $u_{i+1}$,
$u_{i+1}^{\square}$, $v_{1}$ and $v_{1}^{\square}$, thus covering the
remaining edges. After this step we increased the width of
$\mathcal{T}^{\prime}$ by at most 13. (Since the number of children of each
tree decomposition node is at most two, this step enlarges every bag at most
twice.)

It is easy to verify that $\mathcal{T}^{\prime}$ is a valid tree decomposition
of $G^{\prime}$. Furthermore, the width of $\mathcal{T}^{\prime}$ is at most
the width of $\mathcal{T}$ plus 13. ∎

We again get an analogous result for the exact variant.

######  Corollary 16.

Exact Defensive AllianceF, parameterized by the treewidth of the graph, is
$\mathsf{W[1]}$-hard.

###  3.4 Hardness of Defensive Alliance

We now introduce a transformation $\tau^{\text{F}}$ that eliminates forbidden
vertices. The basic idea is that we ensure that a forbidden vertex $f$ is
never part of a solution by adding so many neighbors to $f$ that we could only
defend $f$ by exceeding the bound on the solution size.

######  Definition 17.

We define a function $\tau^{\text{F}}$, which assigns a Defensive Alliance
instance to each Defensive AllianceF instance $I=(G,k,V_{\square})$. For each
$f\in V_{\square}$, we introduce new vertices $f^{\prime},f_{1},\dots,f_{2k}$.
Now we define $\tau^{\text{F}}(I)=(G^{\prime},k)$, where $G^{\prime}$ is the
graph defined by

$\displaystyle\operatorname{V}(G^{\prime})={}$
$\displaystyle\operatorname{V}(G)\cup\\{f^{\prime},f_{1},\dots,f_{2k}\mid f\in
V_{\square}\\},$ $\displaystyle\operatorname{E}(G^{\prime})={}$
$\displaystyle\operatorname{E}(G)\cup\\{(f,f_{i}),\;(f^{\prime},f_{i})\mid
f\in V_{\square},\;1\leqslant i\leqslant 2k\\}.$

We now prove that $\tau^{\text{F}}$ yields a correct reduction from Defensive
AllianceF to Defensive Alliance.

######  Lemma 18.

Every Defensive AllianceF instance $I$ has the same solutions as the Defensive
Alliance instance $\tau^{\text{F}}(I)$.

###### Proof.

Let $I=(G,k,V_{\square})$ and $\tau^{\text{F}}(I)=(G^{\prime},k)$. Each
solution $S$ of $I$ is also a solution of $\tau^{\text{F}}(I)$ because the
subgraph of $G$ induced by $N_{G}[S]$ is equal to the subgraph of $G^{\prime}$
induced by $N_{G^{\prime}}[S]$. Now let $S^{\prime}$ be a solution of
$\tau^{\text{F}}(I)$. For every $f\in V_{\square}$, neither $f$ nor
$f^{\prime}$ are in $S^{\prime}$ because each of these vertices has at least
$2k$ neighbors, and $S^{\prime}$ cannot contain any $f_{i}$ because
$N_{G^{\prime}}(f_{i})=\\{f,f^{\prime}\\}$. Hence $S^{\prime}$ is also a
solution of $I$ as the subgraphs induced by the respective neighborhoods are
again equal. ∎

We use $\tau^{\text{F}}$ to show $\mathsf{W[1]}$-hardness of Defensive
Alliance by reducing from Defensive AllianceF while preserving bounded
treewidth.

######  Lemma 19.

Defensive Alliance, parameterized by the treewidth of the graph, is
$\mathsf{W[1]}$-hard.

###### Proof.

Let $I=(G,k,V_{\square})$ be a Defensive AllianceF instance, let $G^{\prime}$
denote the graph of $\tau^{\text{F}}(I)$ and let $\mathcal{T}$ be an optimal
nice tree decomposition of $G$. We build a tree decomposition
$\mathcal{T}^{\prime}$ of $G^{\prime}$ by modifying a copy of $\mathcal{T}$ in
the following way: For every $f\in V_{\square}$, we pick an arbitrary node $t$
in $\mathcal{T}$ whose bag $B$ contains $f$, and we add a chain of nodes
$N_{1},\dots,N_{2k}$ between $t$ and its parent such that, for $1\leqslant
i\leqslant 2k$, the bag of $N_{i}$ is $B\cup\\{f^{\prime},f_{i}\\}$. It is
easy to verify that $\mathcal{T}^{\prime}$ is a valid tree decomposition of
$G^{\prime}$. Furthermore, the width of $\mathcal{T}^{\prime}$ is at most the
width of $\mathcal{T}$ plus two. ∎

We again get an analogous result for the exact variant.

######  Corollary 20.

Exact Defensive Alliance, parameterized by the treewidth of the input graph,
is $\mathsf{W[1]}$-hard.

##  4 Conclusion

In this work, we proved that the problem of deciding whether a given graph
possesses a nonempty defensive alliance whose size is at most a given integer
is $\mathsf{W[1]}$-hard when the parameter is the treewidth of the graph. This
means that no fixed-parameter tractable algorithm exists under the common
complexity-theoretic assumption $\mathsf{W[1]}\neq\mathsf{FPT}$. Still, recent
work has shown the problem to be solvable in polynomial time on graphs of
bounded clique-width [24], which implies that there is a polynomial-time
algorithm for graphs of bounded treewidth. Our result proves that, for any
such algorithm, the degree of this polynomial must necessarily depend on the
treewidth unless $\mathsf{W[1]}=\mathsf{FPT}$. For future research it may be
interesting to study related problems corresponding to other alliance notions
such as offensive alliances.

## References

  * [1] Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski.  Complexity of finding embeddings in a k-tree.  SIAM J. Algebraic Discrete Methods, 8(2):277–284, 1987.
  * [2] Yuichi Asahiro, Eiji Miyano, and Hirotaka Ono.  Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree.  Discrete Appl. Math., 159(7):498–508, 2011.
  * [3] Bernhard Bliem and Stefan Woltran.  Complexity of secure sets.  CoRR, abs/1411.6549, 2014.  Updated to version 3 on July 11, 2017.
  * [4] Bernhard Bliem and Stefan Woltran.  Complexity of secure sets.  In Proc. WG, volume 9224 of LNCS, pages 64–77. Springer, 2015.
  * [5] Hans L. Bodlaender.  A tourist guide through treewidth.  Acta Cybernet., 11(1-2):1–22, 1993.
  * [6] Hans L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.
  * [7] Hans L. Bodlaender.  Discovering treewidth.  In Proc. SOFSEM, volume 3381 of LNCS, pages 1–16. Springer, 2005.
  * [8] Hans L. Bodlaender and Arie M. C. A. Koster.  Treewidth computations I. Upper bounds.  Inform. and Comput., 208(3):259–275, 2010.
  * [9] Aurel Cami, Hemant Balakrishnan, Narsingh Deo, and Ronald D. Dutton.  On the complexity of finding optimal global alliances.  J. Combin. Math. Combin. Comput., 58:23–31, 2006.
  * [10] Chan-Wei Chang, Ma-Lian Chia, Cheng-Ju Hsu, David Kuo, Li-Ling Lai, and Fu-Hsing Wang.  Global defensive alliances of trees and cartesian product of paths and cycles.  Discrete Appl. Math., 160(4):479 – 487, 2012.
  * [11] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [12] Artan Dermaku, Tobias Ganzow, Georg Gottlob, Benjamin J. McMahan, Nysret Musliu, and Marko Samer.  Heuristic methods for hypertree decomposition.  In Proc. MICAI, volume 5317 of LNCS, pages 1–11. Springer, 2008.
  * [13] Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger.  Capacitated domination and covering: A parameterized perspective.  In Proc. IWPEC, volume 5018 of LNCS, pages 78–90. Springer, 2008.
  * [14] Rodney G. Downey and Michael R. Fellows.  Parameterized Complexity.  Monographs in Computer Science. Springer, 1999.
  * [15] Rosa I. Enciso.  Alliances in Graphs: Parameterized Algorithms and on Partitioning Series-Parallel Graphs.  PhD thesis, University of Central Florida, Orlando, Florida, USA, 2009\.
  * [16] Henning Fernau and Daniel Raible.  Alliances in graphs: a complexity-theoretic study.  In Proc. SOFSEM, volume 2, pages 61–70. Institute of Computer Science AS CR, Prague, 2007.
  * [17] Henning Fernau and Juan A Rodríguez-Velázquez.  A survey on alliances and related parameters in graphs.  Electron. J. Graph Theory Appl. (EJGTA), 2(1):70–86, 2014.
  * [18] Gary William Flake, Steve Lawrence, C. Lee Giles, and Frans Coetzee.  Self-organization and identification of web communities.  IEEE Computer, 35(3):66–71, 2002.
  * [19] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. Springer, 2006.
  * [20] Teresa W. Haynes, Stephen T. Hedetniemi, and Michael A. Henning.  Global defensive alliances in graphs.  Electr. J. Comb., 10, 2003.
  * [21] Yiu Yu Ho and Ronald D. Dutton.  Rooted secure sets of trees.  AKCE Int. J. Graphs Comb., 6(3):373–392, 2009.
  * [22] L. H. Jamieson.  Algorithms and Complexity for Alliances and Weighted Alliances of Various Types.  PhD thesis, School of Computing, Clemson University, Clemson, South Carolina, USA, 2007.
  * [23] Lindsay H Jamieson, Stephen T Hedetniemi, and Alice A McRae.  The algorithmic complexity of alliances in graphs.  J. Combin. Math. Combin. Comput., 68:137–150, 2009.
  * [24] Masashi Kiyomi and Yota Otachi.  Alliances in graphs of bounded clique-width.  Discrete Appl. Math., 223:91–97, 2017.
  * [25] Ton Kloks.  Treewidth: Computations and Approximations, volume 842 of LNCS.  Springer, 1994.
  * [26] András Kornai and Zsolt Tuza.  Narrowness, pathwidth, and their application in natural language processing.  Discrete Appl. Math., 36(1):87–92, 1992.
  * [27] Petter Kristiansen, Sandra M Hedetniemi, and Stephen T Hedetniemi.  Introduction to alliances in graphs.  In Proc. ISCIS, pages 308–312. CRC Press, 2002.
  * [28] Petter Kristiansen, Sandra M Hedetniemi, and Stephen T Hedetniemi.  Alliances in graphs.  J. Combin. Math. Combin. Comput., 48:157–178, 2004.
  * [29] Rolf Niedermeier.  Invitation to Fixed-Parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications.  Oxford University Press, Oxford, United Kingdom, 2006.
  * [30] Neil Robertson and Paul D. Seymour.  Graph minors. III. Planar tree-width.  J. Combin. Theory Ser. B, 36(1):49–64, 1984.
  * [31] Khurram H. Shafique and Ronald D. Dutton.  Maximum alliance-free and minimum alliance-cover sets.  In Congr. Numer, volume 162, pages 139–146, 2003.
  * [32] Stefan Szeider.  Not so easy problems for tree decomposable graphs.  CoRR, abs/1107.1177, 2011.
  * [33] Mikkel Thorup.  All structured programs have small tree-width and good register allocation.  Inform. and Comput., 142(2):159–181, 1998.
  * [34] Ismael González Yero and Juan A Rodríguez-Velázquez.  Defensive alliances in graphs: a survey.  CoRR, abs/1308.2096, 2013.