The Defensive Alliance problem has been studied extensively during the last
twenty years. A set $S$ of vertices of a graph is a defensive alliance if, for each element of $S$,
the majority of its neighbours is in $S$.

We consider the notion of local minimality in this paper. We are interested in locally
minimal defensive alliance of maximum size.

This problem is known to be NP-hard  but its parameterized complexity remains open
until now.  We enhance our understanding of the problem from the
viewpoint of parameterized complexity.
The main results of the paper are the following:
(1)    when the input graph happens to be a tree, Connected Locally Minimal Strong Defensive Alliance can be solved in polynomial
time, (2) the Locally Minimal Defensive Alliance problem is NP-complete, even when restricted to planar graphs,
(3) a color coding algorithm for Exact Connected Locally Minimal Defensive Alliance, (4) the Locally Minimal Defensive Alliance problem is fixed parameter tractable (FPT) when parametrized by neighbourhood diversity,
(5) the Exact Connected Locally Minimal Defensive Alliance problem parameterized by treewidth is W[1]-hard and thus not FPT (unless
(6)  Locally Minimal Defensive Alliance  can be solved in polynomial time for graphs of bounded treewidth.

§ INTRODUCTION

A defensive alliance in an undirected graph is a set of vertices
with the property that each vertex  has at least as many neighbours  in the alliance
(including itself) as neighbours outside the alliance.  In 2000, Kristiansen, Hedetniemi, and Hedetniemi [14]
introduced defensive, offensive, and powerful alliances, and further studied by Shafique [10]
and other authors [18, 1, 3, 21, 19, 20, 22, 4, 2, 6, 8, 12]. In this paper, we will focus on defensive alliances.
A defensive alliance is strong if each vertex has at least as many neighbours in the alliance (not counting itself) as outside the alliance.
The theory of alliances in graphs have been studied
intensively [9, 3, 7] both from a combinatorial and from a computational perspective.
As mentioned in [1], the
focus has been mostly on finding small alliances, although studying large
alliances do not only make a lot of sense from the original motivation of these notions,
but was actually also delineated in the very first papers on alliances [14].

Note that defensive alliance is not a hereditary property, that is, a subset of
defensive alliance is not necessarily a  defensive alliance.  Shafique [10] called
an alliance a locally minimal alliance if the set obtained by removing any vertex of the
alliance is not an alliance. Bazgan  et al. [1] considered another notion
of alliance that they called a globally minimal alliance which has the property that
no proper subset is an alliance. In this paper we are interested in locally minimal
alliances of maximum size. Clearly, the motivation is that big communities where every member
still matters somehow are of more interest than really small communities. Also, there is a
general mathematical interest in such type of problems, see [17].

§ BASIC NOTATIONS

Throughout this article, $G=(V,E)$ denotes a finite, simple and undirected graph of order $|V|=n$.
The (open) neighbourhood $N_G(v)$ of a vertex
$v\in V(G)$ is the set $\{u~|~(u,v)\in E(G)\}$. The closed neighbourhood $N_G[v]$ of a vertex $v\in V(G)$ is the set
$\{v\} \cup N_G(v)$.  The degree of $v\in V(G)$ is $|N_G(v)|$ and denoted by $d_G(v)$. The subgraph induced by
$S\subseteq V(G)$ is denoted by $G[S]$. We use $d_S(v)$ to denote the degree of vertex $v$ in $G[S]$.
The complement of the vertex set $S$ in $V$ is denoted by $S^c$.
A non-empty set $S\subseteq V$ is a defensive alliance in $G$ if for each $v\in S$,
$|N[v]\cap S|\geq |N(v)\setminus S|$, or equivalently,   $d_S(v)+1\geq d_{S^c}(v)$.

A vertex $v\in S$ is said to be protected if $d_S(v)+1\geq d_{S^c}(v)$. Here $v$ has
$d_S(v)+1$ defenders and $d_{S^c}(v)$ attackers in $G$.
A set $S\subseteq V$ is a defensive alliance if every vertex
in $S$ is protected.
A vertex $v\in S$ is said to be marginally protected
if it becomes unprotected when any of its neighbour in $S$ is moved from $S$ to $V\setminus S$.
A vertex $v\in S$ is said to be overprotected if it remains protected
even when any of its neighbours is moved from $S$ to $V\setminus S$.

[1]
An alliance $S$ is called a locally minimal alliance
if for any $v\in S$, $S\setminus \{v\}$ is not an alliance.
It is important to note  that if $S$ is a locally minimal  defensive alliance,
then for every vertex $v \in S$, at least one of its neighbours in $S$ is marginally protected.

[1]
An alliance $S$ is globally minimal alliance or  shorter minimal alliance if no proper
subset is an alliance.

\[  \begin{tikzpicture}[scale=0.5]
\node[vertex](v1)at(6,0){$1$};
\node[vertex](v2)at(0,-2){2};
\node[vertex](v3)at(3,-2){3};
\node[vertex](v4)at(6,-2){4};
\node[vertex](v5)at(9,-2){5};
\node[vertex](v6)at(12,-2){6};
\node[vertex](v7)at(-1,-4){7};
\node[vertex](v8)at(1,-4){8};
\node[vertex](v9)at(2,-4){9};
\node[vertex](v10)at(4,-4){10};
\node[vertex](v11)at(5,-4){11};
\node[vertex](v12)at(7,-4){12};
\node[vertex](v13)at(8,-4){13};
\node[vertex](v14)at(10,-4){14};
\node[vertex](v15)at(11,-4){15};
\node[vertex](v16)at(13,-4){16};
\node[vertex](v17)at(-1,-6){17};
\node[vertex](v18)at(1,-6){18};
\node[vertex](v19)at(2,-6){19};
\node[vertex](v20)at(4,-6){20};
\node[vertex](v21)at(5,-6){21};
\node[vertex](v22)at(7,-6){22};
\node[vertex](v23)at(8,-6){23};
\node[vertex](v24)at(10,-6){24};
\node[vertex](v25)at(11,-6){25};
\node[vertex](v26)at(13,-6){26};
%layer one edges
\path
(v1) edge (v2)
(v1) edge (v3)
(v1) edge (v4)
(v1) edge (v5)
(v1) edge (v6)
(v2) edge (v7)
(v2) edge (v8)
(v3) edge (v9)
(v3) edge (v10)
(v4) edge (v11)
(v4) edge (v12)
(v5) edge (v13)
(v5) edge (v14)
(v6) edge (v15)
(v6) edge (v16)
(v7) edge (v17)
(v8) edge (v18)
(v9) edge (v19)
(v10) edge (v20)
(v11) edge (v21)
(v12) edge (v22)
(v13) edge (v23)
(v14) edge (v24)
(v15) edge (v25)
(v16) edge (v26);
\end{tikzpicture}\]

The set $S_1=\{7,2,9,3,11,4, 13,5, 15,6\}$  is a locally minimal defensive alliance
of size 10 and  $S_2=\{1,2,3\}$ is a globally minimal defensive alliance of size 3 in $G$.

A  defensive alliance $S$ is connected if the subgraph induced by
$S$ is connected. An alliance $S$ is called a connected locally minimal alliance
if for any $v\in S$, $S\setminus \{v\}$ is not a connected alliance.  Notice that
any globally minimal alliance is also connected.

In this paper, we consider Locally Minimal Defensive Alliance and Exact Connected Locally Minimal Defensive Alliance

under structural parameters. We define the problems as follows:

Locally Minimal Defensive Alliance

Input: An undirected graph $G=(V,E)$ and an  integer $k \leq |V(G)|$.

Question: Is there a locally minimal defensive alliance $S\subseteq V(G)$ such that
$|S|\geq  k $?

Exact Connected Locally Minimal Defensive Alliance

Input: An undirected graph $G=(V,E)$ and an  integer $k \leq |V(G)|$.

Question: Is there a connected locally minimal defensive alliance $S\subseteq V(G)$ such that
$|S|= k $?

Our results are as follows:

* Connected Locally Minimal Strong Defensive Alliance problem is polynomial time solvable
on trees.

* Locally Minimal Defensive Alliance problem is NP-complete, even when restricted to planar graphs.

* We give a randomized FPT algorithm for the Exact Connected
Locally Minimal Defensive Alliance problem using color coding technique.

* Locally Minimal Defensive Alliance problem is FPT when parameterized
by neighbourhood diversity of the input graph.

* Exact Connected Locally Minimal Defensive Alliance parameterized by treewidth is W[1]-hard and thus not FPT (unless

* Locally Minimal Defensive Alliance problem is polynomial time solvable
for graphs with bounded treewith.

Known Results: The decision version for several types of alliances have been shown to be NP-complete.
Carvajal et al. [18] proved that deciding if a graph
contains a strong defensive alliance of size at most $k$ is NP-hard.
The defensive alliance problem is
NP-complete even when restricted to split, chordal and bipartite graph [12].
Bazgan et al. [1] proved that deciding if a graph contains a  locally minimal
strong defensive alliance of size at least $k$ is NP-complete, even when restricted to
bipartite graphs with average degree less than 3.6;  deciding if a graph contains a connected locally minimal
strong defensive alliance or a connected locally minimal
defensive alliance of size at least $k$ is NP-complete, even when restricted to
bipartite graphs with average degree less than $2+\epsilon$, for any $\epsilon >0$.

§ POLYNOMIAL-TIME ALGORITHM FOR CONNECTED LOCALLY MINIMAL STRONG DEFENSIVE ALLIANCE ON TREES

Finding the largest connected locally minimal (strong) defensive alliance is believed to be intractable [1]. However,
when the graph happens to be a tree, we solve the problem in polynomial time, using dynamic programming.
Here we consider strong defensive alliances where the vertex itself is not considered in the inequality.
A defensive alliance is strong if each vertex has at least as many neighbours in the alliance (not counting itself) as outside the alliance.
Also recall that if $S$ is a locally minimal (strong) defensive alliance,
then for every vertex $v \in S$, at least one of its neighbours in $S$ is marginally protected.
A vertex $v\in S$ is said to be
good if it has at least one marginally protected children in $S$, otherwise it is called a
bad vertex. Let $v$ be a non-root node with children $v_1,v_2,\ldots,v_d$, that is, $d(v)=d+1$. We define different possible states of a vertex $v$  based on four factors:

* whether the vertex is part of the solution or not

If the vertex is in the solution,  then we consider the following factors:

* whether the vertex is marginally protected or overprotected

* whether the vertex is good or bad

* whether the parent of $v$ is in the solution or not

The states are  as follows:

* $0$: vertex $v$ is not in the solution.

* $m^{p}_{g}:$ vertex $v$ is in the solution, it is marginally protected by its children and parent,
parent of $v$ is in the solution and it has at least one marginally protected child.

* $m^{p}_{b}:$ vertex $v$ is in the solution, it is marginally protected by its children and parent,
parent of $v$ is in the solution and it has no marginally protected children.

* $m^{\bar{p}}_{g}:$  vertex $v$ is in the solution, it is  marginally protected by its children only,
parent of $v$ is not in the solution and it has at least one marginally protected child.

* $o^{p}_{g}:$ vertex $v$ is in the solution, it is overprotected by its children and parent,
parent of $v$ is in the solution and it has at least one marginally protected child.

* $o^{p}_{b}:$ vertex $v$ is in the solution, it is overprotected by its children and parent,
parent of $v$ is in the solution and it has no marginally protected children.

* $o^{\bar{p}}_{g}:$  vertex $v$ is in the solution, it is  overprotected by its children only,
parent of $v$ is not in the solution and it has at least one marginally protected child.

Note that $m^{\bar{p}}_b$ or $o^{\bar{p}}_b$ are not valid state of a vertex $v$ as the vertex
will not have any marginally protected neighbours.
Here is the algorithm: Start by rooting the tree at any node $v$. Each node defines a subtree, the one hanging from it. This immediately suggests subproblems:
$A_v(s)$= the size of the largest connected locally minimal strong defensive alliance
of the subtree rooted at $v$ and the state of $v$ is $s$;
if no connected locally minimal strong defensive alliance exists,  we put $A_v(s)=-\infty$.
Our final goal is to
compute $\max\Big\{ A_r(0), A_r(m^{\bar{p}}_{g}),A_r(o^{\bar{p}}_{g})\Big\}$ where $r$ is the root of $T$.

Leaf Node: For a leaf node $v$, we have  $A_v(0)=0$. Note that as $v$ does not have any children, we get   $A_v(m^{p}_{g})=-\infty, A_v(o^{p}_{g})=-\infty, A_v(o^{\bar{p}}_{g})=-\infty, A_v(m^{\bar{p}}_{g})=-\infty$.
As $v$ is a one degree vertex, it cannot be overprotected in the solution,
therefore, we get $A_v(o^{p}_{b})=-\infty$. We have $A_v(m^{p}_{b})=1$ as this is a valid state.

Non-leaf Node: Let $v$ be a non-leaf node with the set $\mathcal{C}=\{v_1,v_2,\ldots, v_d\}$ of children.
Suppose we know $A_{v_i}(s)$ for all children $v_i$ of $v$. How can we compute $A_v(s)$?
We now consider the following cases:

Case 1: Let the state of $v$ be $0$, that is, $v$ is not included in the solution.
Therefore, we move on to $v$'s children
and consider the best of their solutions. Then

$$ A_v(0)= \max\limits_{x\in \mathcal{C}}{\Big\{A_{x}(0), A_{x}(m^{\bar{p}}_{g}), A_{x}(o^{\bar{p}}_{g})\Big\} }. $$

Case 2: Let the state of $v$ be $m_g^{p}$ or $m_g^{\bar{p}}$. Here $v$ is a good vertex and
therefore, must have a marginally protected child in $S$. Therefore, at least one  child $v_i$ must have label
$m^p_g$ or $m^{p}_b$.
Next, let $(v_1,v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{ A_{v_i}(m^{p}_{g}), A_{v_i}(m^{p}_{b}), A_{v_i}(o^{p}_{g}), A_{v_i}(o^{p}_{b})\}$, that is,
$$\max\{ A_{v_1}(m^{p}_{g}), A_{v_1}(m^{p}_{b}), A_{v_1}(o^{p}_{g}), A_{v_1}(o^{p}_{b})\}
\geq \ldots \geq \max\{ A_{v_d}(m^{p}_{g}), A_{v_d}(m^{p}_{b}), A_{v_d}(o^{p}_{g}), A_{v_d}(o^{p}_{b})\}.$$

Let $\mathcal{C}_{k,i}$ be the set of first $k$ children from the ordering
$(v_1, v_2,\ldots, v_d)$
except vertex $v_i$. Thus, we have

\begin{equation*}
\begin{split}
A_v(m^{p}_g) & =1+ \max\limits_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(m^{p}_g), A_{v_i}(m^{p}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-2,i}}{\max\{A_{x}(m^{p}_g), A_{x}(m^{p}_b), A_{x}(o^{p}_{g}), A_x (o^{p}_{b})\} }\Bigg\},
\end{split}
\end{equation*}

In the case $d=1$, we take $A_{v}(m^{p}_{g})=-\infty$ as the state is invalid.

Suppose the state of
$v$ is $m^{\bar{p}}_{g}$, that is, $v$ is marginally protected by its children only and it has a
marginally protected children. Since the parent of $v$ is not there in the solution, we have

\begin{equation*}
\begin{split}
A_v(m^{\bar{p}}_{g}) & =1+ \max\limits_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(m^{p}_g), A_{v_i}(m^{p}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}}{\max\{A_{x}(m^{p}_g), A_{x}(m^{p}_b), A_{x}(o^{p}_{g}), A_x (o^{p}_{b})\} }\Bigg\}
\end{split}
\end{equation*}

Case 3: Let the state of $v$ be $o^{p}_g$.
When a vertex is overprotected, all its children in the solution must be good.
If any of them is bad, it remains bad, as its parent is an overprotected node.
Here $v$ is a good vertex and
therefore, must have a marginally protected child in $S$.
As $v \in S$ is overprotected in the presence of its parent, $v$ must have at least
$\lceil\frac{d+1}{2}\rceil$ children in $S$, all  these children need to be good.
Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{A_{v_i}(m^{p}_g), A_{v_i}(o^{p}_{g})\}$.
Let $\mathcal{C}_{k,i}$ be the set of first $k$ children from the ordering
$(v_1, v_2,\ldots, v_d)$
except vertex $v_i$.
We have the following recurrence relation:

\begin{equation*}
\begin{split}
A_v(o^{p}_g) & =1+ \max\limits_{v_i\in \mathcal{C}}\Bigg\{ A_{v_i}(m^p_g)
+ \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}}{\max\{A_{x}(m^{p}_g), A_{x}(o^{p}_{g})\} } \\
& +
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}\cup \{v_i\}\big )} \max\Big(0, A_{x}(m^{p}_{g}), A_{x}(o^{p}_{g})\Big)  \Bigg\}.
\end{split}
\end{equation*}

Let the state of $v$ be $o^{\bar{p}}_g$. Then we have the following recurrence relation:

\begin{equation*}
\begin{split}
A_v(o^{\bar{p}}_g) & =1+ \max\limits_{v_i\in \mathcal{C}}\Bigg\{ A_{v_i}(m^p_g)
+ \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil,i}}{\max\{A_{x}(m^{p}_g), A_{x}(o^{p}_{g})\} } \\
& +
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil,i}\cup \{v_i\}\big )} \max\Big(0, A_{x}(m^{p}_{g}), A_{x}(o^{p}_{g})\Big)  \Bigg\}.
\end{split}
\end{equation*}

Case 4: Let the state of $v$ be $o^{p}_b$.  Here $v$ is a bad vertex, that is,
$v$ has no marginally protected children in $S$. In other words, $v$'s children in $S$ must be
overprotected.  As $v \in S$ is overprotected,
all its  children in $S$ must be good. Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $A_{v_i}(o^{p}_{g})$.
Let $\mathcal{C}_{\lceil \frac{d+1}{2} \rceil} = \{v_{1},\ldots,v_{\lceil \frac{d+1}{2} \rceil} \} $.
We have the following recurrence relation:

\begin{equation*}
\begin{split}
A_v(o^{p}_b) & =1+  \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil}} A_{x}(o^{p}_{g})
\sum\limits_{x\in \mathcal{C}\setminus \mathcal{C}_{\lceil\frac{d+1}{2}\rceil}} \max\Big\{0, A_{x}(o^{p}_{g})\Big\}.
\end{split}
\end{equation*}

Case 5: Let the state of $v$ be $m^{p}_b$.  Here $v$ is a bad vertex
therefore, $v$'s children in $S$ are overprotected.
Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{A_{v_i}(o^{p}_{g}), A_{v_i}(o^{p}_{b})\}$.
We have the following recurrence relation:

\begin{equation*}
A_{v}(m^{p}_{b}) = 1 + \sum\limits_{x\in \mathcal{C}_{\lceil \frac{d+1}{2} \rceil-1}} \max \{ A_{x}(o^{p}_{g}), A_{x}(o^{p}_{b}) \}
\end{equation*}

For computation of $A_r(m^{\bar{p}}_{g})$ and $A_r(o^{\bar{p}}_{g})$, we replace $d$ by $d-1$ in the above recurrence
relations as the root  node $r$ with $d$ children has degree $d$, whereas any other non-leaf node
with $d$ children has degree $d+1$.

The running time of this algorithm is easy to analyze.  At each node $v\in V(T)$,  we compute
$A_v(s)$ where $s$ is a state of $v$. The time required to get descending ordering of the children
of $v_i$ is $O(d_i\log d_i)$, where $d_i$ is the number of children of vertex $v_i$.
The number of subproblems is exactly the number of vertices in $T$. The total running time is
therefore equal to  $ c\sum {d_i \log d_i}\leq c \log n\sum{d_i}=cn\log n = O(n \log n)$, where  $c$ is a constant.

§ LOCALLY MINIMAL DEFENSIVE ALLIANCE IN PLANAR GRAPHS IS NP-COMPLETE

Bazgan, Fernau and Tuza showed in [1] that
the problems of deciding whether a given graph contains a locally minimal strong defensive alliance of size
at least $k$ for bipartite graphs with average degree less than $3.6$; deciding if a graph contains a
locally minimal defensive alliance of size at least $k$ for bipartite graphs with average degree less than 5.6;
deciding if a graph contains a connected locally minimal (strong) defensive alliance of size at least $k$, even for
bipartite graphs with average degree less than $2 + \epsilon$, for any $ \epsilon > 0$,

are NP-complete.
Here we prove that the Locally Minimal Defensive Alliance problem is NP-complete in planar graphs, via
a reduction from Minimum Maximal Matching  in cubic planar graph.
Yannakakis and Gavril showed in [25] that the problem of finding a maximal matching of minimum size,
is NP-hard in  planar graphs of maximum degree 3.
In [11], Horton and Kilakos obtained the NP-hardness of Minimum Maximal Matching
in  planar cubic graphs.

The Locally Minimal Defensive Alliance problem is NP-complete, even when restricted to planar graphs.

Clearly, the decision version of the problem belongs to NP.
In order to obtain the NP-hardness result for the locally minimal defensive alliance  problem, we obtain a polynomial
reduction from the Minimum Maximal Matching problem on cubic planar graphs proved NP-hard in [11].
Given an instance  $I=(G,k)$ of  the Minimum Maximal Matching problem where $G$ is a cubic planar graph,
we construct an instance $I'=(G',k')$ of the Locally Minimal Defensive Alliance problem where $G'$ is planar.
An example is given in Figure <ref>.

\[\begin{tikzpicture}[scale=1]
\tiny[square/.style={draw,regular polygon,regular polygon sides=4,minimum size=1},outer sep=0,inner sep=0]
%\node[square, draw=black] (a1) at (1.5,6.3) [label=above:] {};
\tikzstyle{triangle}=[draw, shape=regular polygon, regular polygon sides=3,draw,inner sep=0pt,minimum
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
%\node[triangle, draw=black, fill=red] (a) at (.5,4.5) [label=above right:${\color{red} a}$] {};
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
%\vertex (a) at (0.5,4.5) [label=above right:${\color{red} a}$] {};
%\node[square, draw=black, fill=blue] (a1) at (0.5,5.5) [label=above:${\color{blue} a^{\square}}$] {};
%\node[square, draw=black] (ha1) at (-0.5,5.2) [label=above:] {};
\vertex (d) at (-1,0) [label=below:$d$] {};
\vertex (a) at (-1,1) [label=above:$a$] {};
\vertex (b) at (0,1) [label=above:$b$] {};
\vertex (c) at (0,0) [label=below:$c$] {};

\vertex (dn) at (4,-1) [label=above:$d$] {};
\vertex (an) at (4,2) [label=above:$a$] {};
\node[] (z1) at (4,2.5) [label=above: $A$ ]{};
\vertex (bn) at (4,1) [label=above:$b$] {};
\vertex (cn) at (4,0) [label=above:$c$] {};
\vertex (dn') at (3,-1) [label=above:$d^{\square}$] {};
\vertex (an') at (3,2) [label=above:$a^{\square}$] {};
%	\filldraw[color=red!60, fill=red!5, very thick] (2,2) circle (.2);
\node[] (z1) at (3,2.5) [label=above: $V^{\square}$ ]{};

\vertex (bn') at (3,1) [label=above:$b^{\square}$] {};
\vertex (cn') at (3,0) [label=above:$c^{\square}$] {};
\vertex (ab) at (5.5,3.6) [label=above:$ab$] {};

\node[] (z1) at (5.5,4.3) [label=above: $B$ ]{};
\vertex (ab_s) at (6.5,3.9) [label=above:$ab^{\square}$] {};
\node[] (z1) at (6.5,4.3) [label=above: $E^{\square}$ ]{};

\vertex (ab'_s) at (6.5,3.3) [label=above:$ab^{'\square}$] {};

\vertex (ac) at (5.5,2.4) [label=above:$ac$] {};
\vertex (ac_s) at (6.5,2.7) [label=above:$ac^{\square}$] {};
\vertex (ac'_s) at (6.5,2.1) [label=above:$ac^{'\square}$] {};

\vertex (ad) at (5.5,1.2) [label=above:$ad$] {};
\vertex (ad_s) at (6.5,1.5) [label=above:$ad^{\square}$] {};
\vertex (ad'_s) at (6.5,0.9) [label=above:$ad^{'\square}$] {};

\vertex (bc) at (5.5,-0.2) [label=above:$bc$] {};
\vertex (bc_s) at (6.5,0.1) [label=above:$bc^{\square}$] {};
\vertex (bc'_s) at (6.5,-0.5) [label=above:$bc^{'\square}$] {};

\vertex (bd) at (5.5,-1.4) [label=above:$bd$] {};
\vertex (bd_s) at (6.5,-1.1) [label=above:$bd^{\square}$] {};
\vertex (bd'_s) at (6.5,-1.7) [label=above:$bd^{'\square}$] {};

\vertex (cd) at (5.5,-2.6) [label=above:$cd$] {};
\vertex (cd_s) at (6.5,-2.3) [label=above:$cd^{\square}$] {};
\vertex (cd'_s) at (6.5,-2.9) [label=above:$cd^{'\square}$] {};

\node[] (z1) at (-0.4,-2.9) [label=below: (a) ]{};
\node[] (z1) at (5,-2.9) [label=below: (b) ]{};

\node[circle, draw, red, thick,  minimum size=0.4cm] (a0) at (2,2) [label=left:$C_{a^{\square}}$]{};
\node[circle, draw, red, thick,  minimum size=0.4cm] (b0) at (2,1) [label=left:$C_{b^{\square}}$]{};
\node[circle, draw, red, thick,  minimum size=0.4cm] (c0) at (2,0) [label=left:$C_{c^{\square}}$]{};
\node[circle, draw, red, thick,  minimum size=0.4cm] (d0) at (2,-1) [label=left:$C_{d^{\square}}$]{};

\node[circle, draw, thick, red, minimum size=0.4cm] (ab0) at (7.5,3.9) [label=right:$C_{ab^{\square}}$]{};
\node[circle, draw, thick, red, minimum size=0.4cm] (ab00) at (7.5,3.3) [label=right:$C_{ab'^{\square}}$]{};
\node[circle, draw, thick, red, minimum size=0.4cm] (ac0) at (7.5,2.7) [label=right:$C_{ac^{\square}}$]{};
\node[circle, draw, thick, red, minimum size=0.4cm] (ac00) at (7.5,2.1) [label=right:$C_{ac'^{\square}}$]{};
\node[circle, draw, thick,  red, minimum size=0.4cm] (ad0) at (7.5,1.5) [label=right:$C_{ad^{\square}}$]{};
\node[circle, draw, thick, red, minimum size=0.4cm] (ad00) at (7.5,0.9) [label=right:$C_{ad'^{\square}}$]{};
\node[circle, draw, thick, red, minimum size=0.4cm] (bc0) at (7.5,0.1) [label=right:$C_{bc^{\square}}$]{};
\node[circle, draw, thick, red, minimum size=0.4cm] (bc00) at (7.5,-0.5) [label=right:$C_{bc'^{\square}}$]{};
\node[circle, draw, red, thick, minimum size=0.4cm] (bd0) at (7.5,-1.1) [label=right:$C_{bd^{\square}}$]{};
\node[circle, draw, red, thick, minimum size=0.4cm] (bd00) at (7.5,-1.7) [label=right:$C_{bd'^{\square}}$]{};

\node[circle, draw, red, thick, minimum size=0.4cm] (cd0) at (7.5,-2.3) [label=right:$C_{cd^{\square}}$]{};
\node[circle, draw, red, thick,  minimum size=0.4cm] (cd00) at (7.5,-2.9) [label=right:$C_{cd'^{\square}}$]{};

\draw[red, thick] (an') -- (a0);
\draw[red,  thick] (bn') -- (b0);
\draw[red, thick] (cn') -- (c0);
\draw[red, thick] (dn') -- (d0);
\draw[red, thick] (ab_s) -- (ab0);
\draw[red, thick] (ab'_s) -- (ab00);
\draw[red, thick] (ac_s) -- (ac0);
\draw[red, thick] (ac'_s) -- (ac00);
\draw[red, thick] (ad_s) -- (ad0);
\draw[red, thick] (ad'_s) -- (ad00);
\draw[red, thick] (bc_s) -- (bc0);
\draw[red, thick] (bc'_s) -- (bc00);
\draw[red, thick] (bd_s) -- (bd0);
\draw[red, thick] (bd'_s) -- (bd00);
\draw[red, thick] (cd_s) -- (cd0);
\draw[red, thick] (cd'_s) -- (cd00);

\path
(a) edge (b)
(b) edge (c)
(d) edge (c)
(a) edge (d)
(a) edge (c)
(b) edge (d)
(an) edge (an')
(bn) edge (bn')
(cn) edge (cn')
(dn) edge (dn')
(an) edge (ab)
(an) edge (ac)
(an) edge (ad)
(bn) edge (ab)
(bn) edge (bc)
(bn) edge (bd)
(cn) edge (ac)
(cn) edge (bc)
(cn) edge (cd)
(dn) edge (ad)
(dn) edge (bd)
(dn) edge (cd)
(ab) edge (ab_s)
(ab) edge (ab'_s)
(ac) edge (ac_s)
(ac) edge (ac'_s)
(ad) edge (ad_s)
(ad) edge (ad'_s)
(bc) edge (bc_s)
(bc) edge (bc'_s)
(bd) edge (bd_s)
(bd) edge (bd'_s)
(cd) edge (cd_s)
(cd) edge (cd'_s);
%(ra) edge (an');
\end{tikzpicture}\]

Reducing Minimum Maximal Matching  on planar cubic graphs to
Locally Minimal Defensive Alliance on planar graphs. (a) An undirected graph
$G=(V,E)$ with minimum maximal matching $M=\{(a,b), (c,d)\}$. (b) The planar graph $G'$ produced by the
reduction algorithm that has locally minimal defensive alliance
$ D = A \cup B \setminus \{ab,cd\} \bigcup\limits_{x\in V^{\square} \cup E^{\square}} \Big\{x_{1},x_{2},x_{4},x_{5},x_{7},x_{8},\ldots,x_{58},x_{59}\Big\} $. A red circle represents a cycle of
length 60 and a red line between $x$ and $C_x$ indicates that $x$ is adjacent to all the vertices of $C_x$.

The graph $G^{\prime}$ that we construct has   vertex sets $A$ and $B$, where
$A=V(G)=\{v_1,v_2,\ldots,v_n\}$ and $B=E(G)=\{e_1,e_2,\ldots,e_m\}$, the edge set of $G$.
We make $v_i$ adjacent to $e_j$ if and only if $v_i$ is an endpoint of $e_j$.
Further we add two sets of vertices $V^{\square} = \{v_1^{\square}, \ldots, v_n^{\square}\}$ and
$E^{\square} = \{e_1^{\square},e_1^{\prime \square}, \ldots,e_m^{\square},e_m^{\prime \square} \}$; and
make $v_i$ adjacent to $v_i^{\square}$ and $e_i$ adjacent to
$e_i^{\square}$ and $e_i^{\prime \square}$.
For each  $x\in V^{\square} \cup E^{\square}$, we add a cycle $C_{x}$ of length $6(n+m)$
with vertices $x_{1},x_{2},\ldots,x_{6(n+m)}$ and make all the vertices of $C_x$ adjacent to $x$.
This completes the construction of $G'$. It is easy to note that $G'$ is a planar graph.
Set $k'= 4(n+m)(n+2m) + (n+m-k)$. To complete the proof, we show that  $G$
has a  maximal matching of size at most $k$ if and only if  $G'$ has a locally minimal
defensive alliance of size at least $k'$.

Suppose $G$ has a maximal matching $M$ of size at most $k$.  We claim that
$ D = A \cup (B \setminus M) \bigcup\limits_{x\in V^{\square} \cup E^{\square}} \Big\{x_{1},x_{2},x_{4},x_{5},x_{7},x_{8},\ldots,x_{6(n+m)-2},x_{6(n+m)-1}\Big\} $ is a locally minimal
defensive alliance of size at least $k'$.
It is easy to verify  that all the vertices in $A$ are protected.
Clearly, all the vertices in
$$(B \backslash M) \cup   \bigcup\limits_{x\in V^{\square} \cup E^{\square}} \Big\{x_{1},x_{2},x_{4},x_{5},x_{7},x_{8},\ldots,x_{6(n+m)-2},x_{6(n+m)-1}\Big\}$$
are marginally protected.
Since $M$ is maximal, it is not
possible to remove a vertex from $D \cap B$ since otherwise some vertex from $A$ will become unprotected.
Also, it is not possible to remove a vertex
from $D\cap A$ since otherwise some vertices from $D \cap B$ will become unprotected.
This shows that $D$ is indeed a locally minimal defensive alliance.

For the reverse direction, suppose  that $G'$  has a locally minimal defensive alliance $D$ of size at least $k'$.
We claim that if $x\in V^{\square} \cup E^{\square}$, then $x$ does not lie in $D$.
For the sake of contradiction assume that  $x\in D$. We consider two cases: Case 1: $x$ is marginally
protected. In this case, the cycle $C_{x}$ contributes at most $3(n+m)$ vertices in $D$, as otherwise
$x$ is not marginally protected. Then $|D| < k'$ and this is a contradiction.
Case 2: $x$ is overprotected. Let $x_i$ be a neighbour of $x$ in $C_x \cap D$.
As $D$ is a locally minimal defensive alliance, $x_i$ must have a  marginally protected neighbour, say
$x_{i+1}$, in $C_x$.
Clearly, $x_i$ and $x_{i+1}$ are not marginally protected.
This implies that $x_{i}$ and $x_{i+1}$ do not have a marginally protected neighbour,
a contradiction to the assumption that $D$ is a locally minimal defensive alliance.
As $x\in V^{\square} \cup E^{\square}$ is not in $D$, then
$C_{x}$ can contribute at most $4(n+m)$ vertices in $D$ by choosing two sets from the following three sets of vertices $X_{0} = \{x_{3i} ~|~ 1\leq 2(n+m) \}, X_{1} = \{x_{3i+1} ~|~ 0\leq 2(n+m)-1 \} $ and $X_{2} = \{x_{3i+2} ~|~ 0\leq 2(n+m)-1\}$.
We define $M=B\cap D^c$ and claim that there exists a set $M'\subseteq M$ such that  $M'$ is a maximal matching.
If no subsets of $M$ forms a maximal matching then clearly there exists an edge $(u,v)\in E$
such that it can still be added in $M$.
It implies that all edges incident to $u$ and $v$ are in $D$ and
hence $u$ and $v$ are overprotected.
Therefore, vertex $e=uv \in B$ does not have a marginally protected neighbour
as both of its neighbors $u$ and $v$ are overprotected.
This shows that there must exist a set $M'\subseteq M$ such that $M'$ is a
maximal matching and $|M'|\leq |M|\leq k$.

§ A COLOR CODING ALGORITHM FOR EXACT CONNECTED LOCALLY MINIMAL DEFENSIVE ALLIANCE

In this section, we give a randomized FPT algorithm for the Exact Connected
Locally Minimal Defensive Alliance problem using color coding technique.
Let $G=(V,E)$ be a graph and let $S\subseteq V$ be a subset of size $k$.
Every vertex in $G$
is colored independently with one colour from the set $\{\mbox{green}, \mbox{red}\}$ with uniform
probability. Denote the obtained coloring by  $\chi~ : ~V(G) \rightarrow \{\text{red, green}\}$.
A connected locally minimal  defensive alliance $S$ in $G$ is called a
green connected locally minimal
defensive alliance in $G$ with coloring $\chi$ if all the vertices in $S$ are colored with green color and all the vertices
in $N(S)$ are colored red.

Let $G$ be a graph and let $\chi : V(G) \rightarrow \{\text{red, green}\}$ be a colouring  of its vertices
with two colours, chosen uniformly at random. Let $S\subseteq V$ be a connected
locally minimal  defensive alliance of size $k$ in $G$.
Then the probability that
the elements of
$S$ are coloured with green colour and elements of
$N(S)$ are coloured with red colour is at least $\frac{1}{2^{k^2+k}}$.

As $S$ is a (connected locally minimal) defensive alliance of size
$k$ in $G$, each element $v$ in $S$ is protected and therefore
$v$ can have at most $k$ neighbours outside $S$. It follows that
$|N(S)|\leq |S|k =k^2$.
There are $2^n$ possible colorings $\chi$; and there are
$2^{n-k^2-k}$ possible colorings where the $k$ vertices of $S$ are
coloured green and at most $k^2$ neighbours of $S$ are colored red.
Hence the lemma follows.
Let $G$ be a graph and let $\chi : V(G) \rightarrow \{\text{red, green}\}$ be a colouring  of its vertices
with two colours.  Then there exists an algorithm that checks in time $O(n+m)$
whether $G$ contains a green connected locally minimal
defensive alliance of size $k$ and, if this is the case, returns one such alliance.

Let $V_g$ and $V_r$ be a partitioning of $V(G)$ such that all vertices in
$V_g$ are coloured green and all vertices in $V_r$ are coloured red. A connected
component $C$ is said to be a green connected component if the vertices of
$C$ are colored green.  Run DFS to identify
all green connected
components $C_1,C_2,\ldots,C_{\ell}$ of $G[V_g]$ in $O(m+n)$ time.  Then verify in linear time
if there exists a green connected component $C_i$ of size
$k$ that forms a locally minimal defensive alliance in $G$.

We now combine Lemma <ref> and Lemma <ref> to obtain
the main result of this section.

There exists a randomized algorithm that, given an Exact Connected Locally Minimal
Defensive Alliance
instance $(G, k)$, in time ${2^{\mathcal{O}{(k^{2}+k)}}(n+m)}$ either reports a failure or
finds a  connected locally  minimal
defensive alliance of size exactly $k$ in $G$. Moreover, if the algorithm is given a yes-instance, it returns a solution with a constant probability.

Given an input instance $(G, k)$, we uniformly at random color the vertices of $V(G)$ with two colors green and red. That is, every vertex is colored independently with either green or red color with uniform probability.
Denote the obtained coloring by $\chi : V(G) \rightarrow \{\text{red, green}\}$.
We run the algorithm of Lemma <ref> on the graph $G$ with coloring $\chi$.
If it returns a green connected locally minimal  defensive alliance  $S$ of size $k$,
then we return
this $S$ as connected locally minimal  defensive alliance of size $k$ in $G$. Otherwise, we report

It remains to bound the probability of finding a connected locally minimal  defensive alliance
of size $k$ in the case $(G,k)$ is a yes-instance. To this end, suppose $G$ has a
connected locally minimal  defensive alliance $S$ of size $k$. By Lemma <ref>,
$S$ becomes a green connected locally minimal defensive alliance of size $k$ in the colouring
$\chi$ with probability at least $\frac{1}{2^{k^2+k}}$. If this is the case, the algorithm of
Lemma <ref> finds a green connected locally minimal  defensive alliance of size $k$
(not necessarily $S$ itself), and the algorithm returns a connected locally minimal
alliance of size $k$ in $G$.

Thus we have an algorithm that runs in time $O(m+n)$ and given a yes-instance, returns
a solution with probability at least $\frac{1}{2^{k^2+k}}$. Clearly, by repeating the algorithm
independently $2^{k^2+k}$ times, we obtain the running time bound and the success probability
at least $1-\frac{1}{e}$.

§ FPT ALGORITHM PARAMETERIZED BY NEIGHBOURHOOD DIVERSITY

In this section, we present an FPT algorithm for Locally Minimal Defensive Alliance  problem parameterized
by neighbourhood diversity.
We say two vertices $u$ and $v$ have the same type if and only if
$N(u)\setminus \{v\}=N(v)\setminus \{u\}$. The relation of having the same type
is an equivalence  relation. The idea of neighbourhood diversity is based on this
type structure.
[15]
The neighbourhood diversity of a graph $G=(V,E)$, denoted by ${\tt nd}(G)$, is the least integer $k$ for which we can partition the set $V$ of vertices  into $k$ classes, such that all vertices in each class have the
same type.

If neighbourhood diversity of a graph is bounded by an integer $k$, then there exists
a partition $\{ C_1, C_2,\ldots, C_k\}$ of $V(G)$ into $k$ type  classes. It is known that
such a minimum partition can be found in linear time using fast modular decomposition algorithms [24].

that each type class  could either be a clique or an independent set by definition.
For algorithmic
purpose it is often useful to consider a type graph $H$ of  graph $G$, where
each vertex of $H$ is a type class in $G$, and two vertices $C_i$ and $C_j$ are adjacent iff
there is complete bipartite clique between these type classes in $G$. It is not difficult to see that
there will be either a complete bipartite clique or no edges between any two type classes.
The key property of graphs of
bounded neighbourhood diversity is that their type graphs have bounded size.
In this section, we prove the following theorem:

The Locally Minimal  Defensive Alliance problem is fixed-parameter tractable when parameterized by  the neighbourhood diversity.

Let $G$ be a connected graph such that ${\tt nd}(G)=k$. Let $C_1,\ldots,C_k$ be the partition
of $V(G)$ into sets of type classes. We assume $k\geq 2$ since otherwise the problem
becomes trivial.  Next we guess the cardinality of $C_i\cap S$ and whether the vertices in $C_i$ are marginally
or overprotected, where $S$ is a locally minimal defensive alliance.
We make the following guesses:

* Option 1: $|C_i\cap S|=0$.

* Option 2: $|C_i\cap S|=1$ and the vertices in $C_i$ are marginally protected.

* Option 3: $|C_i\cap S|=1$ and the vertices in $C_i$ are overprotected.

* Option 4: $|C_i\cap S|>1$ and the vertices in $C_i$ are marginally protected.

* Option 5: $|C_i\cap S| >1$ and the vertices in $C_i$ are overprotected.

There are at most $5^k$ choices for  the tuple $(C_1,C_2,\ldots, C_k)$  as each $C_i$ has
5 options as given above.
Finally we reduce the problem of finding a locally minimal defensive alliance of maximum size
to an integer linear programming  optimization with $k$ variables.
Since integer linear programming is fixed parameter tractable when parameterized by
the number of variables [16], we conclude that our problem is FPT when parameterized by
the neighbourhood diversity.

ILP Formulation: Given a particular choice $P$ of options for $(C_1,C_2,\ldots, C_k)$,  our goal here is
to find a  locally minimal defensive alliance of maximum size.
For each $C_i$, we associate a variable $x_i$ that indicates $|S\cap C_i|=x_i$.
Clearly, $x_i=0$, if $C_i$ is assigned Option 1; $x_i=1$ if $C_i$ is assigned
Option 2 or 3; and $x_i>1$ if  $C_i$ is assigned Option 3 or 4.   Because
the vertices in $C_i$ have the same neighbourhood, the variables $x_i$
determine $S$ uniquely, up to isomorphism. Let $\mathcal{C}_1=\{ C_i ~|~ x_i=1 \}$,
$\mathcal{C}_{>1}=\{ C_i ~|~ x_i>1 \}$ and $\mathcal{C}=\mathcal{C}_1\cup \mathcal{C}_{>1}$.
Let $H[\mathcal{C}]$ be the subgraph of $H$ induced by $\mathcal{C}$.
Now we label the vertices of $H[\mathcal{C}]$ as follows:
vertex $C_i$ is labelled $c_1$ if it is a clique and Option 2 is assigned to $C_i$;
vertex $C_i$ is labelled $c_{>1}$ if it is a clique and Option 4 is assigned to $C_i$;
vertex $C_i$ is labelled ind if it is an independent set and Option 2 or 4 is assigned to $C_i$;
vertex $C_i$ is labelled op if it is a clique or an independent set, and Option 3 or 5 is assigned to $C_i$.
To ensure local minimality of defensive alliance, the induced subgraph must satisfy the following  conditions:

* Every vertex labelled op in the induced graph must have at least one neighbour
labelled $c_1, c_{>1}$ or ind.

* Every vertex labelled $c_1$ in the induced graph must have at least one neighbour labelled $c_1, c_{>1}$ or ind.

* Every vertex labelled ind in the induced graph must have at least one neighbour labelled $c_1$, $ c_{>1}$ or ind.

Above conditions ensure local minimality of the solution because when we remove a vertex from the
solution, we make sure at least one of its neighbours gets unprotected. This happens because every vertex in the solution
has at least one neighbour which is marginally protected.  If  the induced subgraph
$H[\mathcal{C}]$ satisfies all the above conditions then we proceed for the ILP, otherwise not.
Let $\mathcal{L}$ be a subset of $\mathcal{C}$ consisting of all type classes which are cliques;
$\mathcal{I}=\mathcal{C}\setminus \mathcal{L}$ be a subset of $\mathcal{C}$ consisting of all type
classes which are independent sets  and $\mathcal{R}=\{C_1,\ldots,C_k\}\setminus \mathcal{C}$. Let $n_i$ denote the number of vertices in $C_i$. We consider two cases:

Case 1: Suppose $v \in C_j$ where $C_j\in \mathcal{I}$.
Then the degree of $v$ in $S$ satisfies

\begin{align}\label{eq1}
d_S(v) &=\sum\limits_{C_i\in N_H(C_j) \cap \mathcal{C}}{x_i}
\end{align}

Thus, including itself, $v$ has $1+\sum\limits_{C_i\in N_H(C_j) \cap \mathcal{C}}{x_i} $
defenders in
$G$. Note that if $C_i\in \mathcal{C}$, then only $x_i$
vertices of $C_i$ are in $S$ and  the remaining $n_i-x_i$ vertices of
$C_i$ are outside $S$.
The degree of $v$ outside $S$ satisfies

\begin{align}\label{eq2}
d_{S^c}(v) &=\sum\limits_{C_i\in N_H(C_j) \cap \mathcal{C}}{(n_i-x_i)} + \sum\limits_{ C_i\in N_H(C_j)\cap \mathcal{R}}{n_i}
\end{align}

Case 2: Suppose $v\in C_j$ where  $C_j\in \mathcal{L}$.   The degree of $v$ in $S$

\begin{align}\label{eq3}
d_S(v)=\sum\limits_{C_i\in N_H[C_j]\cap \mathcal{C}}{x_i}
\end{align}

The degree of $v$ outside $S$ satisfies

\begin{align}\label{eq4}
d_{S^c}(v)=\sum\limits_{C_i\in N_H[C_j]\cap \mathcal{C}}{(n_i-x_i)} +\sum\limits_{C_i\in N_H[C_j]\cap \mathcal{R}}{n_i}
\end{align}

In the following, we present an ILP formulation of
locally minimal defensive alliance problem, where a choice of options for $(C_1,\ldots,C_k)$ is given:

\begin{equation*}
\begin{split}
&\text{Maximize} \sum\limits_{C_i\in \mathcal{C}}{x_i} \\
&\text{Subject to~~~} \\
&1+ \sum\limits_{C_i\in N_H(C_j) \cap \mathcal{C}}{2x_i} > \sum\limits_{C_i\in N_H(C_j)}{n_i}, ~~\text{for all } C_j\in \mathcal{I}, \text{ labelled {\tt op}}, \\
&\sum\limits_{C_i\in N_H(C_j) \cap \mathcal{C}}{2x_i} - \sum\limits_{C_i\in N_H(C_j)}{n_i}=0 \text{ or } -1, ~~\text{for all } C_j\in \mathcal{I}, \text{ labelled {\tt ind}}, \\
&\sum\limits_{C_i\in N_H[C_j]\cap \mathcal{C}}{2x_i}> \sum\limits_{C_i\in N_H[C_j]}{n_i},~~\text{for all } C_j\in \mathcal{L}, \text{ labelled {\tt op} },  \\
&\sum\limits_{C_i\in N_H[C_j]\cap \mathcal{C}}{2x_i}- \sum\limits_{C_i\in N_H[C_j]}{n_i}=0 \text{ or } 1,~~\text{for all } C_j\in \mathcal{L}, \text{ labelled } c_1 \text{ or } c_{>1},  \\
& x_{i}=1 \text{ for all }i ~:~ C_i\in \mathcal{C}_1;\\
& x_i \in \{ 2, 3, \ldots, |C_i| \} \text{ for all }i ~:~ C_i\in \mathcal{C}_{>1}.
\end{split}
\end{equation*}

Solving the ILP:
Lenstra [16] showed that the feasibility version of $p$-ILP is FPT with
running time doubly exponential in $p$, where $p$ is the number of variables.
Later, Kannan [13] proved an algorithm for $p$-ILP running in time $p^{O(p)}$.
In our algorithm, we need the optimization version of $p$-ILP rather than
the feasibility version. We state the minimization version of $p$-ILP
as presented by Fellows et. al. [5].

$p$-Variable Integer Linear Programming Optimization ($p$-Opt-ILP): Let matrices $A\in \ Z^{m\times p}$, $b\in \ Z^{p\times 1}$ and
$c\in \ Z^{1\times p}$ be given. We want to find a vector $ x\in \ Z ^{p\times 1}$ that minimizes the objective function $c\cdot x$ and satisfies the $m$
inequalities, that is, $A\cdot x\geq b$.  The number of variables $p$ is the parameter.
Then they showed the following:

[5]
$p$-Opt-ILP can be solved using $O(p^{2.5p+o(p)}\cdot L \cdot log(MN))$ arithmetic operations and space polynomial in $L$.
Here $L$ is the number of bits in the input, $N$ is the maximum absolute value any variable can take, and $M$ is an upper bound on
the absolute value of the minimum taken by the objective function.

In the formulation for Locally Minimal Defensive Alliance problem, we have at most $k$ variables. The value of objective function is bounded by $n$ and the value of any variable
in the integer linear programming is also bounded by $n$. The constraints can be represented using
$O(k^2 \log{n})$ bits. Lemma <ref> implies that we can solve the problem with the guess $P$ in FPT time.
There are at most $5^k$ choices for $P$, and the ILP formula for a guess can be solved in FPT time. Thus
Theorem <ref> holds.

§ HARDNESS  OF EXACT CONNECTED LOCALLY MINIMAL DEFENSIVE ALLIANCE PARAMETERIZED BY TREEWIDTH

In this section, we prove the following theorem:

The Exact Connected Locally Minimal Defensive Alliance problem is W[1]-hard when parameterized by the treewidth of the input graph.

We introduce several variants of Locally Minimal Defensive Alliance problem that we require in our proofs. The problem
Locally Minimal Defensive Alliance$^{\mbox{F}}$ generalizes Locally Minimal Defensive Alliance where some vertices are
forced to be outside the solution (these vertices are called forbidden vertices).  This variant can be formalized as

Locally Minimal Defensive Alliance$^{\mbox{F}}$

Input: A graph $G=(V,E)$, an integer $k$ and
a set $V_{\square}\subseteq V(G)$.

Question: Does there exist a locally minimal defensive alliance  $S\subseteq V(G)$
of size at least $k$
such that $S\cap V_{\square}=\emptyset$?

Locally Minimal Defensive Alliance$^{\mbox{FN}}$ is a further generalization  where
some vertices are forced to be in every solution (these vertices are called necessary vertices)
and some other vertices are forced to be outside the solution. This variant can be formalized as

Locally Minimal Defensive Alliance$^{\mbox{FN}}$

Input: A graph $G=(V,E)$, an integer $k$, a set $V_{\triangle}\subseteq V(G)$, and
a set $V_{\square}\subseteq V(G)$.

Question: Does there exist a locally minimal defensive alliance  $S\subseteq V(G)$ of
size at least $k$
such that (i) $V_{\triangle}\subseteq S$,

(ii)  $V_{\square}\subseteq S^c$?

Let $G=(V,E)$ be an undirected and edge weighted graph, where $V$, $E$, and $w$ denote
the set of nodes, the set of edges and a positive integral weight
function $w:~E\rightarrow Z^{+}$, respectively. An orientation  $\Lambda$ of $G$ is an
assignment of a direction to each edge $\{u,v\}\in E(G)$, that is, either $(u,v)$ or $(v,u)$
is contained in $\Lambda$. The weighted outdegree of $u$ on $\Lambda$ is $w_{\mbox{out}}^u=\sum_{(u,v)\in \Lambda}w(\{u,v\})$.
We define Minimum Maximum Outdegree problem as follows:

Minimum Maximum Outdegree

Input: A graph $G$, an edge weighting $w$ of $G$ given in unary, and a positive integer $r$.

Question: Is there an orientation $\Lambda$  of $G$ such that $w_{\mbox{out}}^u\leq r$ for
each $u\in V(G)$?

It is known that Minimum Maximum Outdegree is W[1]-hard when parameterized by the treewidth of the input graph [23].
To prove Theorem <ref>,  we  reduce Minimum Maximum Outdegree to  Locally Minimal Defensive Alliance$^{\mbox{FN}}$ and then we show how we can successively reduce the latter problem
Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$, Connected Locally Minimal Defensive Alliance$^{\mbox{F}}$ and finally
Exact Connected Locally Minimal Defensive Alliance.

The Locally Minimal Defensive Alliance$^{\mbox{FN}}$ is W[1]-hard when parameterized by the treewidth of the
primal graph.

Let  $G=(V,E,w)$ and a positive integer $r$ be an  instance of Minimum Maximum Outdegree.
We construct an instance of Locally Minimal Defensive Alliance$^{\mbox{FN}}$ as follows. An example is given in Figure

\[\begin{tikzpicture}[scale=1]
\tiny[square/.style={draw,regular polygon,regular polygon sides=4,minimum size=1},outer sep=0,inner sep=0]
%\node[square, draw=black] (a1) at (1.5,6.3) [label=above:] {};
\tikzstyle{triangle}=[draw, shape=regular polygon, regular polygon sides=3,draw,inner sep=0pt,minimum
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
\node[triangle, draw=black, fill=red] (a) at (.5,4.5) [label=above right:${\color{red} a}$] {};
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
%\vertex (a) at (0.5,4.5) [label=above right:${\color{red} a}$] {};
\node[square, draw=black, fill=blue] (a1) at (0.5,5.5) [label=above:${\color{blue} a^{\square}}$] {};
%\node[square, draw=black] (ha1) at (-0.5,5.2) [label=above:] {};
\vertex (ha1) at (-0.5,5.2) [label=above:${\color{red} h^{a}_1}$] {};
\vertex (ha2) at (-0.5, 4.4) [label=above:${\color{red} h^{a}_2}$] {};
\vertex (ha3) at (-0.5,3.6) [label=above:${\color{red} h^{a}_3}$] {};
\vertex (ha4) at (-0.5,2.8) [label=above:${\color{red} h^{a}_4}$] {};
\node[square, draw=black, fill=blue] (ha11) at (-1.5,5.2) [label=above:${\color{blue} h^{a\square}_1}$] {};
\node[square, draw=black, fill=blue] (ha21) at (-1.5,4.4) [label=above:${\color{blue} h^{a\square}_2}$] {};
\node[square, draw=black, fill=blue] (ha31) at (-1.5,3.6) [label=above:${\color{blue} h^{a\square}_3}$] {};
\node[square, draw=black, fill=blue] (ha41) at (-1.5,2.8) [label=above:${\color{blue} h^{a\square}_4}$] {};
%\vertex (ha11) at (-1.5,5.2) [label=above:${ h^{a\square}_1}$] {};
%\vertex (ha21) at (-1.5, 4.4) [label=above:${ h^{a\square}_2}$] {};
%\vertex (ha31) at (-1.5,3.6) [label=above:${ h^{a\square}_3}$] {};
%\vertex (ha41) at (-1.5,2.8) [label=above:${ h^{a\square}_4}$] {};
\vertex (ad11) at (2,5.6) [label=below:${ \color{blue}a^d_1}$] {};
\node[triangle, draw=black, fill=red] (tad1) at (3,5.6) [label=below:$\triangle_{a_1d_1}$] {};
\node[triangle, draw=black, fill=red] (t'ad1) at (3.25,6) [label=right:$\triangle^{\prime}_{a_1d_1}$] {};
\node[square, draw=black, fill=blue] (s'ad1) at (2.75,6) [label=left:$\square_{a_1d_1}$] {};

\node[square, draw=black, fill=blue] (ad12) at (2,4.9) [label=below:${\color{blue} a^{d\square}_1}$] {};
%\vertex (ad12) at (2, 4.9) [label=below:${ a^{d\square}_1}$] {};
\vertex (da11) at (4.1,5.6) [label=below:${\color{red} d^a_1}$] {};
\node[square, draw=black, fill=blue] (da21) at (4.1,4.9) [label=below:${\color{blue} d^{a \square}_1}$] {};
\node[triangle, draw=black, fill=red] (b) at (.5,0) [label=above right:${\color{red} b}$] {};
%	\vertex (b) at (.5,0) [label=below right:${\color{red} b}$] {};
\node[square, draw=black, fill=blue] (b1) at (.5,-1) [label=below:${\color{blue} b^{\square}}$] {};
\vertex (hb1) at (-0.5,0.6) [label=above:${\color{red} h^{b}_1}$] {};
\vertex (hb2) at (-0.5, -0.2) [label=above:${\color{red} h^{b}_2}$] {};
\vertex (hb3) at (-0.5,-1) [label=above:${\color{red} h^{b}_3}$] {};
\vertex (hb4) at (-0.5,-1.8) [label=above:${\color{red} h^{b}_4}$] {};
\node[square, draw=black, fill=blue] (hb11) at (-1.5,0.6) [label=above:${\color{blue} h^{b\square}_1}$] {};
\node[square, draw=black, fill=blue] (hb21) at (-1.5,-0.2) [label=above:${\color{blue} h^{b\square}_2}$] {};
\node[square, draw=black, fill=blue] (hb31) at (-1.5,-1) [label=above:${\color{blue} h^{b\square}_3}$] {};
\node[square, draw=black, fill=blue] (hb41) at (-1.5,-1.8) [label=above:${\color{blue} h^{b\square}_4}$] {};
%\vertex (hb11) at (-1.5,0.6) [label=below:${\ h^{b\square}_1}$] {};
%\vertex (hb21) at (-1.5,-0.2) [label=below:${ h^{b\square}_2}$] {};
%\vertex (hb31) at (-1.5,-1) [label=below:${ h^{b\square}_3}$] {};
%\vertex (hb41) at (-1.5,-1.8) [label=below:${ h^{b\square}_4}$] {};
\vertex (bc11) at (2,0.6) [label=above:${\color{blue} b^c_1}$] {};

\vertex (bc12) at (2, -0.4) [label=above:${\color{blue} b^c_2}$] {};

\node[square, draw=black, fill=blue] (bc13) at (2,-0.9) [label=right:${\color{blue} b^{c \square}_1}$] {};
\node[square, draw=black, fill=blue] (bc14) at (2,-1.5) [label=right:${\color{blue} b^{c \square}_2}$] {};
\vertex (ba11) at (0.4,1.5) [label=left:${\color{red}  b^a_1}$] {};
\node[square, draw=black, fill=blue] (ba13) at (1,1.5) [label=right:${\color{blue} b^{a \square}_1}$] {};
\node[triangle, draw=black, fill=red] (c) at (5.5,0) [label=above right:${\color{red} c}$] {};
%\vertex (c) at (5.5,0) [label=below right:$\color{red} c$] {};
\node[square, draw=black, fill=blue] (c1) at (5.5,-1) [label=below:${ \color{blue} c^{\square}}$] {};
\vertex (hc1) at (6.5,0.6) [label=above:${\color{red} h^{c}_1}$] {};
\vertex (hc2) at (6.5, -0.2) [label=above:${\color{red} h^{c}_2}$] {};
\vertex (hc3) at (6.5,-1) [label=above:${\color{red} h^{c}_3}$] {};
\vertex (hc4) at (6.5,-1.8) [label=above:${\color{red} h^{c}_4}$] {};
\node[square, draw=black, fill=blue] (hc11) at (7.5,0.6) [label=above:${\color{blue} h^{c\square}_1}$] {};
\node[square, draw=black, fill=blue] (hc21) at (7.5,-0.2) [label=above:${\color{blue} h^{c\square}_2}$] {};
\node[square, draw=black, fill=blue] (hc31) at (7.5,-1) [label=above:${\color{blue} h^{c\square}_3}$] {};
\node[square, draw=black, fill=blue] (hc41) at (7.5,-1.8) [label=above:${\color{blue} h^{c\square}_4}$] {};
%\vertex (hc11) at (7.5,0.6) [label=above:${ h^{c\square}_1}$] {};
%\vertex (hc21) at (7.5,-0.2) [label=above:${ h^{c\square}_2}$] {};
%\vertex (hc31) at (7.5,-1) [label=above:${ h^{c\square}_3}$] {};
%\vertex (hc41) at (7.5,-1.8) [label=above:${ h^{c\square}_4}$] {};
\vertex (cb11) at (4,0.6) [label=above:${ \color{red} c^b_1}$] {};

\node[triangle, draw=black, fill=red] (tb1c1) at (3,0.6) [] {};
\node[triangle, draw=black, fill=red] (t'b1c1) at (2.7,1) [] {};
\node[square, draw=black, fill=blue] (sb1c1) at (3.3,1) [] {};

\node[triangle, draw=black, fill=red] (tb1c2) at (3,0.1) [] {};
\node[triangle, draw=black, fill=red] (t'b1c2) at (2.7,.4) [] {};
\node[square, draw=black, fill=blue] (sb1c2) at (3.3,.4) [] {};

\node[triangle, draw=black, fill=red] (tb2c2) at (3,-0.4) [] {};
\node[triangle, draw=black, fill=red] (t'b2c2) at (2.7,-.7) [] {};
\node[square, draw=black, fill=blue] (sb2c2) at (3.3,-.7) [] {};

\vertex (cb12) at (4, -0.4) [label=above:${\color{red} c^b_2}$] {};

\node[square, draw=black, fill=blue] (cb13) at (4,-0.9) [label=left:${\color{blue} c^{b \square}_1}$] {};
\node[square, draw=black, fill=blue] (cb14) at (4,-1.5) [label=left:${\color{blue} c^{b \square}_2}$] {};
\vertex (cd11) at (3.8,1.5) [label=left:${\color{blue} c^d_1}$] {};

\node[triangle, draw=black, fill=red] (tc1d2) at (4.3,2.5) [] {};
\node[triangle, draw=black, fill=red] (t'c1d2) at (4,2.8) [] {};
\node[square, draw=black, fill=blue] (sc1d2) at (4,2.2) [] {};

\vertex (cd12) at (4.8,1.5) [label=left:${\color{blue} c^d_2}$] {};
\node[square, draw=black, fill=blue] (cd13) at (5.2,1.5) [label=above:${\color{blue} c^{d \square}_1}$] {};
\node[square, draw=black, fill=blue] (cd14) at (5.8,1.5) [label=above:${\color{blue} c^{d \square}_2}$] {};
\node[triangle, draw=black, fill=red] (d) at (5.5,4.5) [label=above right:${\color{red} d}$] {};
%\vertex (d) at (5.5,4.5) [label=above right:$\color{red} d$] {};
\node[square, draw=black, fill=blue] (d1) at (5.5,5.5) [label=above:${\color{blue}  d^{\square}}$] {};
\vertex (dc11) at (3.8,3.5) [label=left:${\color{red} d^c_1}$] {};
\node[triangle, draw=black, fill=red] (tcd1) at (3.8,2.5) [] {};
\node[triangle, draw=black, fill=red] (t'cd1) at (3.4,2.8) [label=left:$\triangle^{\prime}_{c_1d_1}$] {};
\node[square, draw=black, fill=blue] (scd1) at (3.4,2.2) [label=left:$\square_{ c_1d_1}$] {};

\node[triangle, draw=black, fill=red] (tc2d2) at (4.8,2.5) [] {};
\node[triangle, draw=black, fill=red] (t'c2d2) at (5.2,2.8) [] {};
\node[square, draw=black, fill=blue] (sc2d2) at (5.2,2.2) [] {};

\vertex (dc12) at (4.8,3.5) [label=left:${\color{red} d^c_2}$] {};
\node[square, draw=black, fill=blue] (dc13) at (5.2,3.5) [label=below:${\color{blue} d^{c \square}_1}$] {};
\node[square, draw=black, fill=blue] (dc14) at (5.8,3.5) [label=below:${\color{blue} d^{c \square}_2}$] {};
\vertex (ab11) at (0.4,3.5) [label=left:${\color{blue} a^b_1}$] {};
\node[triangle, draw=black, fill=red] (tab1) at (0.4,2.5) [label=left:$\triangle_{a_1b_1}$] {};
\node[triangle, draw=black, fill=red] (t'ab1) at (.8,2.8) [label=right:$\triangle^{\prime}_{a_1b_1}$] {};
\node[square, draw=black, fill=blue] (s'ab1) at (.8,2.2) [label=right:$\square_{a_1b_1}$] {};

\node[square, draw=black, fill=blue] (ab13) at (1,3.5) [label=right:$a^{b \square}_1$] {};
\vertex (hd1) at (6.5,5.2) [label=above:$ \color{red} h^{d}_1$] {};
\vertex (hd2) at (6.5,4.4) [label=above:$\color{red} h^{d}_2$] {};
\vertex (hd3) at (6.5,3.6) [label=above:${\color{blue} h^{d}_3}$] {};
\vertex (hd4) at (6.5,2.8) [label=above:${\color{blue} h^{d}_4}$] {};
\node[square, draw=black, fill=blue] (hd11) at (7.5,5.2) [label=above:${\color{blue} h^{d\square}_1}$] {};
\node[square, draw=black, fill=blue] (hd21) at (7.5,4.4) [label=above:${\color{blue} h^{d\square}_2}$] {};
\node[square, draw=black, fill=blue] (hd31) at (7.5,3.6) [label=above:${\color{blue} h^{d\square}_3}$] {};
\node[square, draw=black, fill=blue] (hd41) at (7.5,2.8) [label=above:${\color{blue} h^{d\square}_4}$] {};
%\vertex (hd11) at (7.5,5.2) [label=above:$ h^{d\square}_1$] {};
%\vertex (hd21) at (7.5,4.4) [label=above:$ h^{d\square}_2$] {};
%\vertex (hd31) at (7.5,3.6) [label=above:$ h^{d\square}_3$] {};
%\vertex (hd41) at (7.5,2.8) [label=above:$ h^{d\square}_4$] {};

%	\vertex (y) at (1,0.5) [label=below:$\square^{ab}$] {};
\path
% Note that the word "path" here isn't used in the graph-theory sense; the \path command
% is always used prior to the list of edges; here, coincidentally, they do form an actual path.
(a1) edge (a)
(a) edge (ha1)
(a) edge (ha2)
(a) edge (ha3)
(a) edge (ha4)
(ab13) edge (a)
(a) edge (ad11)
(a) edge (ad12)
(d) edge (d1)
(d) edge (hd1)
(d) edge (hd2)
(d) edge (hd3)
(d) edge (hd4)
(hd11) edge (hd1)
(hd21) edge (hd2)
(hd31) edge (hd3)
(hd41) edge (hd4)
(hc11) edge (hc1)
(hc21) edge (hc2)
(hc31) edge (hc3)
(hc41) edge (hc4)
(hb11) edge (hb1)
(hb21) edge (hb2)
(hb31) edge (hb3)
(hb41) edge (hb4)
(ha11) edge (ha1)
(ha21) edge (ha2)
(ha31) edge (ha3)
(ha41) edge (ha4)
(d) edge (dc11)
(d) edge (dc12)
(d) edge (dc13)
(d) edge (dc14)
(d) edge (da11)
(d) edge (da21)
(a) edge (ab11)
(b) edge (b1)
(b) edge (hb1)
(b) edge (hb2)
(b) edge (hb3)
(b) edge (hb4)
(b) edge (bc11)
(b) edge (bc12)
(b) edge (bc13)
(b) edge (bc14)
(b) edge (ba11)
(b) edge (ba13)
(c) edge (c1)
(c) edge (hc1)
(c) edge (hc2)
(c) edge (hc3)
(c) edge (hc4)
(c) edge (cb11)
(c) edge (cb12)
(c) edge (cb13)
(c) edge (cb14)
(c) edge (cd11)
(c) edge (cd12)
(c) edge (cd13)
(c) edge (cd14)
(ad11) edge (tad1)
(tad1) edge (da11)
(t'ad1) edge (tad1)
(s'ad1) edge (tad1)
(t'ad1) edge (s'ad1)
(tab1) edge (ab11)
(tab1) edge (ba11)
(tab1) edge (t'ab1)
(tab1) edge (s'ab1)
(t'ab1) edge (s'ab1)
(dc11) edge (tcd1)
(cd11) edge (tcd1)
(tcd1) edge (t'cd1)
(tcd1) edge (scd1)
(t'cd1) edge (scd1)
(tc1d2) edge (sc1d2)
(tc1d2) edge (t'c1d2)
(sc1d2) edge (t'c1d2)
(cd11) edge (tc1d2)
(dc12) edge (tc1d2)
(dc12) edge (tc2d2)
(cd12) edge (tc2d2)
(tc2d2) edge (t'c2d2)
(tc2d2) edge (sc2d2)
(t'c2d2) edge (sc2d2)
(bc11) edge (tb1c1)
(cb11) edge (tb1c1)
(tb1c1) edge (t'b1c1)
(tb1c1) edge (sb1c1)
(t'b1c1) edge (sb1c1)
(bc11) edge (tb1c2)
(cb12) edge (tb1c2)
(tb1c2) edge (t'b1c2)
(tb1c2) edge (sb1c2)
(t'b1c2) edge (sb1c2)
(bc12) edge (tb2c2)
(cb12) edge (tb2c2)
(tb2c2) edge (t'b2c2)
(tb2c2) edge (sb2c2)
(t'b2c2) edge (sb2c2)

%\draw (-2,2) .. controls (-1,0) and (1,0) .. (2,2);
%\path[draw, dashed] (cb21) -- controls (3,0.5) -- (bc21);
% \draw[dashed, thick] (2,5.6) --  (4.1,5.6);
%\draw[dashed, thick] (2,0.3) --  (4,0.3);
%\draw[dashed, thick] (2,0.3) --  (4,-0.3);
% \draw[dashed, thick] (2, -0.3) --  (4,-0.3);
% \draw[dashed, thick] (0.4,1.5) --  (0.4,3.5);
%\draw[dashed, thick] (4,1.5) --  (4,3.5);
%\draw[dashed, thick] (4,1.5) --  (4.6,3.5);
%\draw[dashed, thick] (4.6,1.5) --  (4.6,3.5);

\vertex (a) at (-3, 2) [label=above:$a$]{};
\vertex (d) at (-2,2)  [label=above:$d$]{};
\vertex (b) at (-3, 1) [label=below:$b$]{};
\vertex (c) at (-2, 1) [label=below:$c$]{};
\path[->]
(c) edge node[right]{$2$}  (d)
(b) edge node[below]{$2$} (c)
(a) edge node[left]{$1$} (b)
(a) edge node[above]{$1$} (d);

\end{tikzpicture}\]

Result of our reduction on a Minimum Maximum Outdegree instance $G$ with $r=2$. The graph $G$ long with its
orientation is shown at the left; and $G^{\prime}$ is shown at the right.
The necessary vertices in $V_{\triangle}$  are filled with red colour; the forbidden vertices in $V_{\square}$ are filled with blue colour. The vertices in locally minimal defensive alliance $S$
are shown in red label for the given orientation of $G$.

For each vertex $v\in V(G)$, we introduce one new vertex $v^{\square}$ and two sets of new vertices $H_v=\{h_1^{v}, \dots, h_{2r}^{v}\}$ and
$H_v^{\square}=\{h_1^{v\square}, \dots, h_{2r}^{v \square}\}$.
For each edge
$(u,v)\in E(G)$, we introduce the sets of new vertices
$V_{uv}=\{u^v_1, \ldots, u^v_{w(u,v)}\}$,
$V_{vu}=\{v^u_1, \ldots, v^u_{w(u,v)}\}$,
$V^{\square}_{uv}=\{u^{v\square}_1, \ldots, u^{v\square}_{w(u,v)}\}$,
$V^{\square}_{vu}=\{v^{ u\square}_1, \ldots, v^{u\square}_{w(u,v)}\}$.
Let $\omega =\sum\limits_{(u,v)\in E(G)}{w(u,v)}$.
We define a set of complementary vertex pairs

\begin{align*}
C &=\Big\{(u_i^{v}, v_i^{u}),~|~ (u,v)\in E(G), 1\leq i\leq w(u,v)\Big\}\\
& \bigcup \Big\{(u_{i+1}^{v},v_i^{u}) ~|~ (u,v)\in E(G), 1\leq i\leq w(u,v)-1\Big\}.
\end{align*}

For every complementary pair $c=(u^{v},v^{u})\in C$, we introduce three vertices $V(c)=\{\triangle_{u^{v}v^{u}}, \square_{u^{v}v^{u}}, \triangle^{\prime}_{u^{v}v^{u}}\}$. We add the following set of edges to the complementary pair gadget

$$E(c) = \{(\triangle_{u^{v}v^{u}}, \square_{u^{v}v^{u}}),(\triangle_{u^{v}v^{u}},\triangle^{\prime}_{u^{v}v^{u}}),(\triangle^{\prime}_{u^{v}v^{u}}, \square_{u^{v}v^{u}}),(u^{v},\triangle_{u^{v}v^{u}}), (\triangle_{u^{v}v^{u}},v^{u})\}.$$

We now define the graph
$G^{\prime}$ with

\begin{align*}
V(G^{\prime})&=V(G) \bigcup\Big\{v^{\square}~|~v \in V(G)\Big\} \bigcup\limits_{v\in V(G)} \big(H_v \cup H_v^{\square}\big) \\ &\bigcup\limits_{(u,v)\in E(G)}\big(V_{uv}\cup
V_{uv}^{\square} \cup V_{vu}\cup V_{vu}^{\square}\big) \bigcup\limits_{c\in C} V(c)
\end{align*}

\begin{align*}
E(G^{\prime})&= \big\{(v,h)~|~v\in V(G), h\in H_v\big\} \bigcup \big\{(h_i^v,h_i^{v\square})~|~1\leq i\leq 2r, v\in V(G)\big\}\\
&\bigcup \Big\{ (u,x) ~|~ (u,v)\in E(G), x\in V_{uv}\cup V_{uv}^{\square}\Big\}\\
& \bigcup \Big\{(x,v)~|~ (u,v)\in E(G), x \in V_{vu}\cup V_{vu}^{\square}\Big\} \bigcup \Big\{(v,v^{\square})~|~ v\in V(G)\Big\} \\
& \bigcup\limits_{c\in C} E(c) .
\end{align*}

The number of vertices in $G^{\prime}$ is $n(4r+2)+4\omega+3|C|$, where $n$ is the number of vertices in $G$.  Finally we define $V_{\triangle}=V(G) \bigcup\limits_{(u^{v},v^{u})\in C} \{\triangle_{u^{v}v^{u}},\triangle^{\prime}_{u^{v}v^{u}} \}  $,

\[V_{\square}=\bigcup_{(u,v)\in E(G)}(V_{uv}^{\square}\cup V_{vu}^{\square})\bigcup_{v\in V(G)}H_v^{\square}\bigcup\Big\{v^{\square}~|~v \in V(G)\Big\} \bigcup\limits_{(u^{v},v^{u})\in C} \{\square_{u^{v}v^{u}}\}\]

and $k=n(r+1)+\omega + 2|C| $. Note that the end points of each
complementary pair are adjacent to a vertex in $V_{\triangle}$.
We use $I$ to denote $(G^{\prime},k, V_{\triangle}, V_{\square})$ which is an instance
of Locally Minimal Defensive Alliance$^{\mbox{FN}}$.

Clearly, it takes polynomial time to compute $I$. We now prove that  the treewidth of the
graph $G^{\prime}$ of $I$ is bounded by a function of  the treewidth of $G$. We do so by modifying an optimal tree decomposition $\tau$ of $G$ as follows:

* For every edge $(u,v)$ of $G$, there is a node in $\tau$ whose  bag $B$  contains
both $u$ and $v$; add to this node a chain of nodes $1,2,\ldots,w(u,v)-1$ where the bag of node $i$
is $B\cup \{u_i^v, v_{i}^{u}, u_{i+1}^{ v},
v_{i+1}^{ u}, \triangle_{u_{i}^{v}v_{i}^{u}}, \square_{u_{i}^{v}v_{i}^{u}}, \triangle^{\prime}_{u_{i}^{v}v_{i}^{u}},\triangle_{u_{i}^{v}v_{i+1}^{u}}, \square_{u_{i}^{v}v_{i+1}^{u}}, \triangle^{\prime}_{u_{i}^{v}v_{i+1}^{u}} \}$.

* For every edge $(u,v)$ of $G$, there is a node in $\tau$ whose  bag $B$  contains
$u$; add to this node a chain of nodes $1,2,\ldots,w(u,v)$ where the bag of node $i$
is $B\cup \{u_i^{v \square}, u^{\square}\}$.

* For every edge $(u,v)$ of $G$, there is a node in $\tau$ whose bag
$B$ contains
$v$ and add to this node a chain of nodes $1,2,\ldots,w(u,v)$ where the bag of node $i$
is $B\cup \{v_i^{u \square}, v^{\square}\}$.

* For every vertex  $v$ of $G$, there is a node in $\tau$ whose bag $B$ contains
$v$ and add to this node a chain of nodes $1,2,\ldots,2r$ where the bag of node $i$
is $B\cup \{h_i^v, h_i^{v\square}\}$.

Clearly, the modified tree decomposition is a valid tree decomposition of the graph of $I$ and
its width is at most the treewidth of $G$ plus ten.

Let $D$ be the directed graph obtained by  an orientation of the edges of $G$ such that for
each vertex the sum of the weights of outgoing edges is at most $r$.
Let $w_{\mbox{out}}^x$ and $w_{\mbox{in}}^x$ denote the sum of the weights
of outgoing and incoming edges of vertex $x$, respectively. Then the set

$$S=V_{\triangle} \bigcup_{(u,v)\in E(D)} V_{vu} \bigcup \big\{h_i^v~|~1\leq i\leq r+w_{\mbox{out}}^v; v\in V(G) \big\}$$
is a
locally minimal defensive alliance of size $k$.
To prove that $S$ is a locally minimal defensive alliance, we show that
$d_{S}(x)\geq d_{S^c}(x)$ for all $x\in S$ and each vertex in $S$ has a marginally protected
neighbour.  Let $x$ be a vertex in $S$. If  $x\in H_v$, then including itself,  it has two
neighbour in $S$ and
one neighbour in $S^c$; so $x$ is marginally protected. If  $x\in V_{uv}$, then including itself,
it has three neighbour in $S$ and
no neighbours in $S^c$; so $x$ is protected. If $x\in V(G) \subseteq V_{\triangle}$, then including
itself, it has $r+w_{\mbox{out}}^x+w_{\mbox{in}}^x+1$ neighbours in $S$, and
it has $r+w_{\mbox{out}}^x+w_{\mbox{in}}^x+1$ neighbours in $S^c$; so $x$ is marginally protected.
If $x\in V_{\triangle}\setminus V(G)=\bigcup\limits_{(u^{v},v^{u})\in C} \{\triangle_{u^{v}v^{u}},\triangle^{\prime}_{u^{v}v^{u}}\}$, then it is easy to see that $x$ is marginally protected.
Thus every vertex $x$ in $S$ is protected and has at least one marginally protected neighbour.
Conversely, suppose $S$ is a solution of the instance $I$. We first show that exactly one vertex from each complementary pair belong to $S$.  The following holds for every solution $S$ of $I$: As $S$ contains
$\triangle_{u^{v}v^{u}}, \triangle^{\prime}_{u^{v}v^{u}}$ for every complementary pair
$(u^{v},v^{u})\in C$, it  must include at least one vertex
from $\{u^{v},v^{u}\}$ to protect $\triangle_{u^{v}v^{u}}$ in the solution. We claim $S$ cannot include
both $u^{v}$ and $v^{u}$. We know every vertex in a locally minimal defensive alliance must have a marginally
protected neighbour. As $\triangle_{u^{v}v^{u}}$ is the only neighbour of $\triangle^{\prime}_{u^{v}v^{u}}$ in $S$,
$\triangle_{u^{v}v^{u}}$ must be marginally protected. Suppose both $u^{v}$ and $v^{u}$ are in
$S$, then including itself, $\triangle_{u^{v}v^{u}}$ has four neighbours in $S$, and
one neighbour outside $S$. Then $\triangle_{u^{v}v^{u}}$ is not marginally protected.
Therefore $S$ contains exactly one endpoint  for
each $(u^{v},v^{u})\in C$.
For every $(u,v)\in E(G)$, either
$V_{uv}\in S$ or $V_{vu}\in S$
due to the complementary
vertex pairs.
We define a directed graph $D$ by $V(D)=V(G)$ and

\[E(D)=\Big\{ (u,v) ~|~V_{vu}\subseteq S\Big\}\bigcup \Big\{ (v,u) ~|~V_{uv}\subseteq S\Big\}. \]

Suppose there is a vertex $x$ in $D$ for which $w_{\mbox{out}}^x>r$.
Clearly $x\in V(G)$. We know, including itself, $x$ has at most $2r+w_{\mbox{in}}^x +1$
neighbours in $S$ and $x$ has at least  $2w_{\mbox{out}}^x + w_{\mbox{in}}^x+1$
neighbours in $S^c$.
Then $d_{S^c}(x)> d_S(x)$,
as by assumption
$w_{\mbox{out}}^x >r$, a contradiction to the fact that $S$ is
a (locally minimal) defensive alliance of $G^{\prime}$.
Hence $w_{\mbox{out}}^x\leq r$ for all
$x\in V(D)$.

The Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$ is W[1]-hard when parameterized by the treewidth of the graph.

Let $I = (G,k,V_{\triangle},V_{\square})$ be a Locally Minimal Defensive Alliance$^{\mbox{FN}}$
instance; let $n$ denote
the number of vertices in $G$. We  construct an instance $I'$ of Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$
the following way.  We illustrate our
construction in Figure <ref>.

\[\begin{tikzpicture}[scale=0.8]
\tiny[square/.style={draw,regular polygon,regular polygon sides=4,minimum size=1},outer sep=0,inner sep=0]
%\node[square, draw=black] (a1) at (1.5,6.3) [label=above:] {};
\tikzstyle{triangle}=[draw, shape=regular polygon, regular polygon sides=3,draw,inner sep=0pt,minimum
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
\vertex (v1) at (0,3) [label= above: $v_1$] {};
\vertex (v2) at (0,2) [label= above: $v_2$] {};
\vertex (v3) at (0,0) [label= below: $v_n$] {};

\node[triangle, draw=black, fill=red] (h) at (-2.2,1.5) [label= above: $h$] {};
\node[square, draw=black, fill=blue] (t) at (2,1.5) [label= above: $t$] {};

\node[triangle, draw=black, fill=red] (h1) at (-4,3) [label= above right: $h_{1}$] {};
\node[square, draw=black, fill=blue] (h11) at (-5,3.6) [label= left: $h_{1}^{1\square}$] {};
\node[square, draw=black, fill=blue] (h12) at (-5,3.2) [label= left: $h_{1}^{2\square}$] {};
\node[square, draw=black, fill=blue] (h13) at (-5,2.8) [label= left: $h_{1}^{3\square}$] {};
\node[square, draw=black, fill=blue] (h14) at (-5,2.4) [label= left: $h_{1}^{4\square}$] {};

\node[triangle, draw=black, fill=red] (h2) at (-4,1) [label= above right: $h_{2}$] {};
\node[square, draw=black, fill=blue] (h21) at (-5,1.6) [label= left: $h_{2}^{1\square}$] {};
\node[square, draw=black, fill=blue] (h22) at (-5,1.2) [label= left: $h_{2}^{2\square}$] {};
\node[square, draw=black, fill=blue] (h23) at (-5,0.8) [label= left: $h_{2}^{3\square}$] {};
\node[square, draw=black, fill=blue] (h24) at (-5,0.4) [label= left: $h_{2}^{4\square}$] {};

\node[triangle, draw=black, fill=red] (h3) at (-4,-1.5) [label= right: $h_{4n}$] {};
\node[square, draw=black, fill=blue] (h31) at (-5,-0.9) [label= left: $h_{4n}^{1\square}$] {};
\node[square, draw=black, fill=blue] (h32) at (-5,-1.3) [label= left: $h_{4n}^{2\square}$] {};
\node[square, draw=black, fill=blue] (h33) at (-5,-1.7) [label= left: $h_{4n}^{3\square}$] {};
\node[square, draw=black, fill=blue] (h34) at (-5,-2.1) [label= left: $h_{4n}^{4\square}$] {};

\draw (0,1.3) ellipse (0.8cm and 2.2cm);

\path

(h1) edge (h2)
(t) edge (v1)
(t) edge (v2)
(t) edge (v3)
(h) edge (v1)
(h) edge (v2)
(h) edge (v3)
(h1) edge (h)
(h2) edge (h)
(h3) edge (h)
(h1) edge (h11)
(h1) edge (h12)
(h1) edge (h13)
(h1) edge (h14)
(h2) edge (h21)
(h2) edge (h22)
(h2) edge (h23)
(h2) edge (h24)
(h3) edge (h31)
(h3) edge (h32)
(h3) edge (h33)
(h3) edge (h34);

\draw[dotted, thick] (0,1.7) --  (0,0.3);
\draw[dotted, thick] (-4,0.7) --  (-4,-1.2);
\draw (-4,3) .. controls (-3.3,0.75) .. (-4,-1.5);

\node[] (z1) at (0,3.5) [label= above: $G$]{};

\end{tikzpicture}\]

The graph $G'$ in our reduction from Locally Minimal Defensive Alliance$^{\mbox{FN}}$
to Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$ for the proof of  Lemma

We introduce one necessary vertex $h$ and one forbidden vertex $t$ which are adjacent to all vertices in $G$.
We introduce a set of  necessary vertices $H = \{ h_{1},h_{2},\dots,h_{4n}\}$.
For every vertex $h_{i}$ in $H$, we introduce four forbidden vertices $H_{i}^{\square} = \{h_{i}^{1\square},h_{i}^{2\square},h_{i}^{3\square},h_{i}^{4\square}\}$.
We now define the Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$ instance $I^{\prime}= (G^{\prime} , k^{\prime},  V^{\prime}_{\triangle}, V^{\prime}_{\square})$ where
$V_{\triangle}^{\prime} = V_{\triangle}\bigcup\{ h\} \bigcup\limits_{i=1}^{4n}\{ h_{i}\} $ and $ V^{\prime}_{\square} = V_{\square}\bigcup \{ t \}\bigcup\limits_{i=1}^{4n}\bigcup\limits_{j=1}^{4}\{ h_{i}^{j\square}\}$ and $G^{\prime}$ is the graph defined by

$$ V(G^{\prime}) = V(G)\bigcup \{h,t\}  \bigcup\limits_{i=1}^{4n}\bigcup\limits_{j=1}^{4}\{h_{i},h_{i}^{j\square}\} $$

\begin{align*}
E(G^{\prime}) = &E(G) \bigcup\limits_{u \in V(G)} \{(u,h),(u,t)\} \bigcup\limits_{i=1}^{4n}\bigcup\limits_{j=1}^{4}\{(h_{i},h_{i}^{j\square}),(h,h_{i})\} \bigcup\limits_{i=1}^{4n-1} \{(h_{i},h_{i+1}),(h_{4n},h_{1})\}
\end{align*}

We set $k^{\prime}=k+4n+1$. The treewidth of $G^{\prime}$ is equal to the treewidth of $G$ plus 5.
We now claim that $I$ is a yes-instance if and only if $I^{\prime}$ is a yes-instance.
Suppose there exists a locally minimal defensive alliance  $S\subseteq V(G)$ with $|S|\geq k$ of $G$
such that $V_{\triangle} \subseteq S$ and $V_{\square} \subseteq S^c$.
We claim that the set $S^{\prime} = S \  \bigcup H  \bigcup \{h\}$
is a connected locally
minimal defensive alliance in $G'$.
As  $h$ is adjacent to all vertices in $S'$, the subgraph induced by $S'$ is connected.
Each vertex in $S$  remains protected and has a marginally protected
neighbour. Each vertex in $H$ is marginally protected and has a marginally protected neighbour in $H$.
Similarly, $h$ is strongly protected and adjacent to marginally protected vertices in  $H$.
Since we are adding the set $H$ of $4n$ vertices and a vertex $h$ to $S$, it implies that $|S'|\geq k'$.
This shows that $I'$ is a yes-instance.

Conversely, suppose that there exists a connected locally minimal defensive alliance $S^{\prime}$ of $G^{\prime}$ with $|S^{\prime}|\geq k'$ such that $V_{\triangle}^{\prime} \subseteq S'$ and $V^{\prime}_{\square} \cap S^{\prime}=\emptyset$. We claim that $S = S^{\prime} \cap V(G)$ forms a locally minimal defensive alliance in $G$.
Clearly, each vertex in $S=S^{\prime} \cap V(G)$  is protected as it loses one neighbour
each from inside and outside the solution. This also implies that marginally protected
vertices in $S^{\prime}$ will remain marginally protected in $S$. As every vertex in
$ S^{\prime}$ had a marginally protected neighbour in $S^{\prime}$
and $h$ is strongly protected in $S'$, it shows that every vertex in $S$ will also have a marginally
protected neighbour in $S$. As we are removing exactly $4n+1$ vertices from the solution,
we get $|S|\geq k$.  This shows that $I$ is a yes-instance.

As a consequence of this lemma, we have the following result:
The Exact Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$ problem is W[1]-hard when parameterized by the treewidth of the graph.

The Connected Locally Minimal Defensive Alliance$^{\mbox{F}}$ is W[1]-hard when parameterized by the treewidth of the graph.

Let $I = (G,k,V_{\triangle},V_{\square})$ be a
Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$ instance.
We construct an instance $I^{\prime}= (G^{\prime},k',V^{\prime}_{\square})$ of
Connected Locally Minimal Defensive Alliance$^{\mbox{F}}$ the following way.
For each  $u\in V_{\triangle}$, we introduce two new vertices $u^1$ and $u^2$.
For each $u^1$, we introduce a set $V_{u^1} = \{ u_{i}^1 \  | \  1\leq i \leq 4n\}$
of $4n$ vertices. For each $u_{i}^{1} \in V_{u^1}$, we add a set $V_{u_i^1}^{\square}$ of four
one-degree forbidden vertices adjacent to $u_{i}^{1}$.
We now define the graph $G'$ with

$$ V(G') = V(G) \bigcup\limits_{u\in V_{\triangle}}{\{u^{1},u^{2}\}}
\bigcup\limits_{u\in V_{\triangle}}\bigcup\limits_{i=1}^{4n} {\{u_i^{1}\}}
\bigcup\limits_{u\in V_{\triangle}}\bigcup\limits_{i=1}^{4n} {V_{u_i^1}^{\square}}

\begin{align*}
E(G^{\prime}) &= E(G)  \bigcup\limits_{u\in V_{\triangle}} \bigcup\limits_{i=1}^{4n} \Big\{(u^{1},u),(u^{2},u),(u^{1},u^{1}_{i}),(u^{1}_{i},\alpha) \  | \ \alpha \in V_{u_i^1}^{\square} \Big\}.
\end{align*}

We set $V^{\prime}_{\square} = V_{\square}
\bigcup\limits_{u\in V_{\triangle}}{\{u^{2}\}}
\bigcup\limits_{u\in V_{\triangle}}\bigcup\limits_{i=1}^{4n} {V_{u_i^1}^{\square}}$ and $k^{\prime} = k + (4n+1)|V_{\triangle}|$.

\[\begin{tikzpicture}[scale=0.5]

\tiny[square/.style={draw,regular polygon,regular polygon sides=4,minimum size=1},outer sep=0,inner sep=0]
\tikzstyle{triangle}=[draw, shape=regular polygon, regular polygon sides=3,draw,inner sep=0pt,minimum
\vertex(u) at (0,1) [label=above right :$ {u^{1}}$]{};
\vertex (u') at (0,3.5) [label=above right :$u$]{};
\node[square, draw=black, fill=blue](u'1) at (-3.5,3.5) [label=above right :${u^{2}}$]{};
\vertex (x1) at (-5,0)[label=above right :${u_1^{1}}$]{};
\node[square, draw=black, fill=blue]  (x11) at (-8.5,5)[label=left :]{};
\node[square, draw=black, fill=blue]  (x12) at (-8.5,4)[label=left :]{};
\node[square, draw=black, fill=blue]  (x13) at (-8.5,3)[label=left :]{};
\node[square, draw=black, fill=blue]  (x14) at (-8.5,2)[label=left :]{};
\vertex (x3) at (-4,-2)[label=right :${u_{2}^{1}}$]{};
\node[square, draw=black, fill=blue] (x31) at (-8.5,-1)[label=right :]{};
\node[square, draw=black, fill=blue] (x32) at (-8.5,-2)[label=right :]{};
\node[square, draw=black, fill=blue] (x33) at (-8.5,-3)[label=right :]{};
\node[square, draw=black, fill=blue] (x34) at (-8.5,-4)[label=right :]{};
\vertex (x4) at (-2,-4)[label=above right :${u_{2n}^{1}}$]{};
\node[square, draw=black, fill=blue] (x41) at (-5,-6)[label=above right :]{};
\node[square, draw=black, fill=blue] (x42) at (-4,-6)[label=above right :]{};
\node[square, draw=black, fill=blue] (x43) at (-3,-6)[label=above right :]{};
\node[square, draw=black, fill=blue] (x44) at (-2,-6)[label=above right :]{};
\vertex (x5) at (2,-4)[label=above left :${u_{2n+1}^{1}}$]{};
\node[square, draw=black, fill=blue] (x51) at (2,-6)[label=above left :]{};
\node[square, draw=black, fill=blue] (x52) at (3,-6)[label=above left :]{};
\node[square, draw=black, fill=blue] (x53) at (4,-6)[label=above left :]{};
\node[square, draw=black, fill=blue] (x54) at (5,-6)[label=above left :]{};
\vertex (x6) at (4,-2)[label= left :${u_{4n-1}^{1}}$]{};
\node[square, draw=black, fill=blue] (x61) at (8.5,-1)[label=right :]{};
\node[square, draw=black, fill=blue] (x62) at (8.5,-2)[label=right :]{};
\node[square, draw=black, fill=blue] (x63) at (8.5,-3)[label=right :]{};
\node[square, draw=black, fill=blue] (x64) at (8.5,-4)[label=right :]{};
\vertex (x8) at (5,0)[label=above left :${u_{4n}^{1}}$]{};
\node[square, draw=black, fill=blue]  (x81) at (8.5,5)[label=left :]{};
\node[square, draw=black, fill=blue]  (x82) at (8.5,4)[label=left :]{};
\node[square, draw=black, fill=blue]  (x83) at (8.5,3)[label=left :]{};
\node[square, draw=black, fill=blue]  (x84) at (8.5,2)[label=left :]{};

\node[] (z1) at (-3.5,-7.2) [label= below: ${V_{u_{2n}^1}^{\square}}$]{};
\node[] (z2) at (3.5,-7.2) [label= below: ${V_{u_{2n+1}^1}^{\square}}$]{};
\node[] (z3) at (10.5,2.5) [label= above: ${V_{u_{4n}^1}^{\square}}$]{};
\node[] (z4) at (10.5,-3.5) [label= above: ${V_{u_{4n-1}^1}^{\square}}$]{};
\path

(u) edge (u')
(u') edge (u'1)
(u) edge (x1)
(u) edge (x3)
(u) edge (x4)
(u) edge (x5)
(u) edge (x6)
(x1) edge (x11)
(x1) edge (x12)
(x1) edge (x13)
(x1) edge (x14)
(x3) edge (x31)
(x3) edge (x32)
(x3) edge (x33)
(x3) edge (x34)
(x4) edge (x41)
(x4) edge (x42)
(x4) edge (x43)
(x4) edge (x44)
(x5) edge (x51)
(x5) edge (x52)
(x5) edge (x53)
(x5) edge (x54)
(x6) edge (x61)
(x6) edge (x62)
(x6) edge (x63)
(x6) edge (x64)
(x8) edge (x81)
(x8) edge (x82)
(x8) edge (x83)
(x8) edge (x84)
(u) edge (x8)
(x1) edge (x3)
(x4) edge (x5)
(x6) edge (x8);

\draw[dotted, thick] (-3.8,-2.4) .. controls (-3.3,-3.3) .. (-2.5,-3.8);
\draw[dotted, thick] (3.8,-2.4) .. controls (3.3,-3.3) .. (2.5,-3.8);
\draw (-5,0) .. controls (0,-1) .. (5,0);

\draw [decorate,decoration={brace,amplitude=10pt,mirror},xshift=-4pt,yshift=0pt]
(-8.8,5) -- (-8.8,2) node [black,midway,xshift=-0.8cm]
{\footnotesize ${V_{u_1^1}^{\square}}$};

\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
(9,5) -- (9,2) node [black,midway,xshift=-0.8cm]
\draw [decorate,decoration={brace,amplitude=10pt,mirror},xshift=-4pt,yshift=0pt]
(-8.8,-1) -- (-8.8,-4) node [black,midway,xshift=-0.8cm]
{\footnotesize ${V_{u_2^1}^{\square}}$ };
\draw [decorate,decoration={brace,amplitude=10pt},xshift=-4pt,yshift=0pt]
(9,-1) -- (9,-4) node [black,midway,xshift=-0.8cm]
\draw [decorate,decoration={brace,amplitude=10pt,mirror},xshift=0pt,yshift=0pt]
(-5,-6.5) -- (-2,-6.5) node [black,midway,xshift=-0.8cm]
\draw [decorate,decoration={brace,amplitude=10pt},xshift=0pt,yshift=0pt]
(5,-6.5) -- (2,-6.5) node [black,midway,xshift=-0.8cm]
\end{tikzpicture}
\]

An illustration of the reduction of necessary vertices in Connected Locally Minimal Defensive Alliance$^{\mbox{FN}}$ to
Connected Locally Minimal Defensive Alliance$^{\mbox{F}}.$ The vertex $u$ may have additional neighbours in $G$.

We claim that $I$ is a yes-instance if and only if $I'$ is a yes-instance.
Suppose there is a connected locally minimal defensive alliance $S$ in  $G$ such that $V_{\triangle} \subseteq S$ and $V_{\square} \cap S = \emptyset$. We claim the set
$ S^{\prime} = S \cup \bigcup\limits_{u\in V_{\triangle}}\bigcup\limits_{i=1}^{4n} \{u^{1}, u_{i}^{1}\} $
is a connected locally minimal defensive alliance  in  $G'$ such that $S'\cap V'_{\square}=\emptyset$.
Clearly, each vertex in $S$  remains protected and has a marginally protected neighbour because we are
adding equal number of neighbours inside and outside the solution for each vertex in $S$.
We observe that the vertices in
$V_{u^{1}} = \{ u_{i}^{1} \  | \  1\leq i \leq 4n\}$  are marginally protected and have a marginally protected
neighbour in the same set. Also, $u^{1}$ is overprotected and has marginally protected neighbours in the set $V_{u^{1}}$.
As for every vertex in the set $V_{\triangle}$, we are adding exactly $4n+1$ vertices to the solution, it implies that $|S'| \geq k'=k+(4n+1)|V_{\triangle}|$. This proves that if $I$ is a yes-instance then $I'$ is a yes-instance.

To prove the reverse direction of the equivalence, suppose there is a connected locally minimal defensive
alliance $S'$ of $G'$ such
that $V_{\square}^{\prime} \cap S'= \emptyset$.
We  first prove that
all the vertices $\{u,u^{1} \ | u\in V_{\triangle}\}$ are in the solution.
If there is a vertex $u^{1}$ such that it is not part of the $S'$ then no
vertices from the set $V_{u^{1}}$ are part of $S'$ as they will not be protected.
This implies that  $|S'| \leq n + (4n+1)(|V_{\triangle}|-1) < (4n+1)|V_{\triangle}|  < k'$,
a contradiction to the fact that $|S'| \geq k'$.
If there is a vertex $u$ such that it is not part of the $S'$ then no vertices from
the set $V_{u^{1}}$  are part of  $S'$ as the solution will be disconnected;
if $V_{u^{1}}$ itself forms a solution then clearly $|V_{u^{1}}| < k'$.
We claim that $S = S' \cap V(G)$ is a
locally minimal defensive alliance in graph $G$ of size at least $k$ such that $V_{\triangle} \subseteq S$.
We proved  that $V_{\triangle} \subseteq S$.
Since every vertex in $S$  loses equal number of neighbours from inside and outside the solution, the vertices of $S$
remain protected. This also implies that every vertex in $S$ has a marginally protected neighbour.
This is true since $u$ has only one new neighbour $u^{1}$ in $S'$ and since $u^{1}$ is
overprotected in $S'$, $u$ must have a marginally protected neighbour in $S=S' \cap V(G)$.
As we are removing exactly $(4n+1)|V_{\triangle}|$ vertices from $S'$, we get $|S|\geq k$.

As a consequence of this lemma, we have the following result:
The Exact Connected Locally Minimal Defensive Alliance$^{\mbox{F}}$ is W[1]-hard when parameterized by the treewidth of the graph.

The Exact Connected Locally Minimal Defensive Alliance is W[1]-hard when parameterized by the treewidth of the graph.

Let $I = (G,k,V_{\square})$ be an instance of the Exact Connected Locally Minimal Defensive
Alliance$^{\mbox{F}}$ problem. We construct an instance $I'=(G',k')$ of Exact Connected Locally Minimal Defensive Alliance
as follows. For every $u \in V_{\square}$, we introduce a set $V_u$ of $2n$ one-degree vertices adjacent to $u$.
The graph $G'$ is defined as follows:

$$ V(G') = V(G) \cup \bigcup\limits_{u\in V_{\square}} V_u $$

$$ E(G') = E(G) \cup  \bigcup\limits_{u\in V_{\square}} \Big\{(u,\beta) \ | \ \beta\in V_u \Big\}$$

We set $k'=k~(\leq n)$.

We claim that $I$ is a yes-instance if and only if $I'$ is a yes-instance.
Suppose $S$ is a connected locally minimal defensive alliance of size $k$ in $G$. Then $S$ is also a connected locally
minimal defensive alliance of size $k$ in  $G'$.
Conversely, suppose that $S'$ is a connected locally minimal defensive alliance of size $k$ in $G'$.
We observe that no vertex from the set $V_{\square}$ lie in $S'$ as the protection of a vertex from
$V_{\square}$  requires at least $n$ vertices
in $S'$. This  implies that $|S'|>n$, a contradiction to the fact that $|S'|=k~(\leq n)$. Therefore,
is an exact connected locally minimal defensive alliance of size $k$ in $G$ such that
$V_{\square}\cap S'=\emptyset$.
This shows that  $I$ is a yes-instance.

This proves Theorem <ref>.

§ GRAPHS OF BOUNDED TREEWIDTH

In this section we prove that Locally Minimal Defensive Alliance  problem can be solved in polynomial
time for graphs of bounded treewidth. In other words, this section presents an  XP-algorithm
for Locally Minimal Defensive Alliance  problem parameterized by

We now prove the following theorem:
Given an $n$-vertex graph $G$ and its nice tree decomposition $T$ of width at most $k$, the
size of a maximum locally minimal defensive alliance of $G$ can be computed in $8^k n^{O(2^{k+1})}$ time.

Let $(T, \{X_{t}\}_{t \in V(T)})$ be a nice tree decomposition rooted at node $r$
of the input graph $G$.  For a node $t$ of $T$, let $V_t$ be the union of all
bags present in the subtree of $T$ rooted at $t$, including $X_t$. We denote by $G_t$ the subgraph of $
G$ induced by $V_t$. For each node $t$ of $T$, we construct a table
$dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)\in \{ \mbox{true, false}\}$ where
$A\subseteq X_t$; ${\bf x}$ and ${\bf y}$ are  vectors of length $n$;

$a$, $\alpha$ and $\beta$ are integers
between $0$ and $n$. We set
$dp_t(A, {\bf x}, a,\alpha, \bf{y},\bf{z}, \beta)= \mbox{true}$ if and only if there exists  a set $A_t\subseteq V_t$ such that:

* $A_t \cap X_t=A$

* $a=|A_t|$

* the $i$th coordinate of vector ${\bf x}$ is

\[ x(i) =
\begin{cases}
\text{$d_{A_t}(v_i$)} &\quad\text{for $v_i\in A$}\\
\text{$0$} &\quad\text{otherwise}\\
\end{cases}
\]

* $\alpha$ is the number of vertices $v \in A_t$ that are protected, that is,
$d_{A_t}(v)\geq \frac{d_G(v)-1}{2}$.

* A vertex $v\in A$ is said to be “good" if it has at least one marginally protected neighbour
in $A_t\setminus A$. A vertex $v \in A$ is said to be “bad" if it has no marginally protected neighbours
in $A_t\setminus A$. Here ${\bf y}$ is a vector of length $n$,  and
the $i$th coordinate of vector ${\bf y}$ is

\[ y(i) =
\begin{cases}
\text{$g$} &\quad\text{if $v_i\in A$ and $v_i$ is a good vertex}\\
\text{$b$} &\quad\text{if $v_i\in A$ and $v_i$ is a bad vertex}\\
\text{$0$} &\quad\text{otherwise}\\
\end{cases} \]

* ${\bf z}$ is a $2^k$ length vector, where the entry $z(S)$ associated with subset $S\subseteq A$ denotes
the number of common bad neighbours of $S$ in $A_t\setminus A$. The $z$ vector considers
the   power set of $A$ in lexicographic order. For example, let $A=\{a,b,c\}$, then ${\bf z}=\Big(z(\{a\}),
z(\{a,b\}), z(\{a,b,c\}), z(\{a,c\}), z(\{b\}), z(\{b,c\}), z(\{c\})\Big) $.

* $\beta$ is the number of good vertices in $A_t$.

We compute all entries $dp_t(A, {\bf x}, a,\alpha, \bf{y},\bf{z}, \beta)$ in a bottom-up manner.
Since $tw(T)\leq k$, at most $2^k n^k (n+1)^3 2^k n^{2^k}= 4^kn^{O(2^k)}$
records are maintained at each node $t$. Thus, to prove Theorem <ref>, it suffices to show
that each entry $dp_t(A, {\bf x}, a,\alpha, \bf{y},\bf{z}, \beta)$ can be computed in
$2^kn^{O(2^k)}$ time, assuming that the entries for the children of $t$ are already

Leaf node:  For a leaf node $t$ we have that $X_t=\emptyset$. Thus
$dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$ is true if and only if $A=\emptyset$,
${\bf x=0}$, $a=0$, $\alpha=0$, $\bf{y=0}$, $\bf{z=0}$, $\beta=0$ . These conditions can be checked in
$O(1)$ time.

Introduce node:  Suppose $t$ is an introduction node with child $t^{\prime}$ such
that $X_t=X_{t^{\prime}} \cup \{v_i\}$ for some $v_i\notin X_{t^{\prime}}$.
Let $A$ be any subset of $X_t$. We consider two cases:

Case (i): Let $v_i\notin A$.
In this case $dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$ is true if and only if
$dp_{t^{\prime}}(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$ is true.

Case (ii): Let $v_i \in A$.
Here $dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$ is true if and only if there exist
$A^{\prime}, {\bf x^{\prime}}, a^{\prime}$, $ \alpha^{\prime}$, ${\bf y^{\prime}}$,
${\bf z^{\prime}}$, and  $\beta^{\prime}$ such that
$dp_{t^{\prime}}(A^{\prime}, {\bf x^{\prime}}, a^{\prime},  \alpha^{\prime}, {\bf y^{\prime}},
{\bf z^{\prime}}, \beta^{\prime} )$=true, where

* $A=A^{\prime} \cup \{v_i\}$;

* $x(j)=x^{\prime}(j)+1$, if $v_j\in N_A(v_i)$, $x(i)=d_A(v_i)$, and $x(j)=x^{\prime}(j)$ if $v_j \in A \setminus N_A[v_i]$;

* $a=a^{\prime}+1$;

* $\alpha=\alpha^{\prime} +\delta$; here $\delta$ is the cardinality of the set
$$\Big\{ v_j\in A~|~ x^{\prime}(j) < \frac{d_G(v_j)-1}{2} ; x(j) \geq  \frac{d_G(v_j)-1}{2}  \Big\}.$$

That is, to compute $\alpha$ from $\alpha^{\prime}$ we need to add the number $\delta$ of those vertices
not satisfied in  $(A^{\prime}, {\bf x^{\prime}}, a^{\prime}, \alpha^{\prime}, {\bf y^{\prime}},
{\bf z^{\prime}}, \beta^{\prime})$ but satisfied in $(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$.

* $y(i)=b$ and $y(j)=y^{\prime}(j)$ for all $j\neq i$.

* $z(S)=z^{\prime}(S)$ if $v_i\notin S$;
$z(S)=0$ if $v_i\in S$.

* $\beta=\beta^{\prime}$.

For an introduce node $t$, $dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$ can be computed in $O(1)$ time.
This follows from the fact that there is only one candidate of such tuple $(A^{\prime}, {\bf x^{\prime}}, a^{\prime}, \alpha^{\prime}, {\bf y^{\prime}},
{\bf z^{\prime}}, \beta^{\prime})$.

Forget node: Suppose $t$ is a forget node with child $t^{\prime}$ such that $X_t=X_{t^{\prime}}\setminus \{v_i\}$ for some
$v_i\in X_{t^{\prime}}$.  Let $A$ be any subset of $X_t$. Here $dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$
is true if and only if either
$dp_{t^{\prime}}(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$  is true (this corresponds to the case that $A_t$ does not contain
$v_i$) or
$dp_{t^{\prime}}(A^{\prime}, {\bf x^{\prime}}, a^{\prime},  \alpha^{\prime}, {\bf y^{\prime}},
{\bf z^{\prime}}, \beta^{\prime})$=true for some $A^{\prime}, {\bf x^{\prime}}$, $a^{\prime}$,  $\alpha^{\prime}$,  ${\bf y^{\prime}}$,
${\bf z^{\prime}}$, $\beta^{\prime}$ with the
following conditions (this corresponds to the case that $A_t$ contains $v_i$):

* $A^{\prime}=A \cup \{ v_i\}$;

* $x(j)=x^{\prime}(j) $ for all $j \neq i$ and $x(i)=0$;

* $a=a^{\prime}$;

* $\alpha=\alpha^{\prime}$;

We now consider four cases:

Case 1: $v_i$ is not marginally protected and $v_i$ is a good vertex.

5. $y(j)=y^{\prime}(j)$ for all $j\neq i$ and $y(i)=0$;

6. $z(S)=z^{\prime}(S)$ for all $S\subseteq A$;

7.  $\beta=\beta^{\prime}$.

Case 2: $v_i$ is not marginally protected and $v_i$ is a bad vertex.

5. $y(j)=y^{\prime}(j)$ for all $j\neq i$ and $y(i)=0$;

\[ z(S) =
\begin{cases}
\text{$z^{\prime}(S)+1$} &\quad\text{if $S \subseteq N_A(v_i)$}\\
\text{$z^{\prime}(S)$} &\quad\text{otherwise}\\
\end{cases}
\]

7.  $\beta=\beta^{\prime}$.

Case 3: $v_i$ is marginally protected and $v_i$ is a good vertex.

\[ y(j) =
\begin{cases}
\text{$g$} &\quad\text{if $v_j \in N_A(v_i)$}\\
\text{$y^{\prime}(j)$} &\quad\text{if $v_j\in A \setminus N_A(v_i) $}\\
%\text{$0$} &\quad\text{otherwise}\\
\end{cases}
\]

6. $z(S)=z^{\prime}(S)-z^{\prime}(S\cup \{v_i\})$ for all $S\subseteq A$;

7.  $\beta=\beta^{\prime}+z^{\prime}(\{v_i\})+ |\Big\{j~:~y^{\prime}(j)=b; y(j)=g\Big\}|$.

Case 4: $v_i$ is  marginally protected and $v_i$ is a bad vertex.

\[ y(j) =
\begin{cases}
\text{$g$} &\quad\text{if $v_j \in N_A(v_i)$}\\
\text{$y^{\prime}(j)$} &\quad\text{if $v_j\in A \setminus N_A(v_i) $}\\
%\text{$0$} &\quad\text{otherwise}\\
\end{cases}
\]

\[ z(S)=\begin{cases}
\text{$z^{\prime}(S)-z^{\prime}(S\cup \{v_i\})+1$} &\quad\text{if $S \subseteq  N_A(v_i)$}\\
\text{$z^{\prime}(S)-z^{\prime}(S\cup \{v_i\})$} &\quad\text{for all other subsets $S \subseteq A$}\\
\end{cases}
\]

7.  $\beta=\beta^{\prime}+z^{\prime}(\{v_i\})+ |\Big\{j~:~y^{\prime}(j)=b; y(j)=g\Big\}|$.

For a forget node $t$, $dp_t(A, {\bf x}, a,\alpha, \bf{y}, \bf{z}, \beta)$ can be
computed in $n^{O(2^k)}$ time. This follows from the
fact that there are $n^{O(2^k)}$ candidates of such tuple $(A^{\prime}, {\bf x^{\prime}}, a^{\prime}, \alpha^{\prime}, {\bf z^{\prime}}$, $\beta^{\prime} )$, and each of them can be checked in $O(1)$ time.

Join node: Suppose $t$ is a join node with children $t_1$ and $t_2$ such that $X_t=X_{t_1}=X_{t_2}$. Let
$A$ be any subset of $X_t$. Then $dp_{t}(A, {\bf x}, a,\alpha, {\bf y}, {\bf z}, \beta)$ is true
if and only if there exist $(A_1, {\bf x_1},a_1,\alpha_1, {\bf y_1}, {\bf z_1}, \beta_1)$ and
$(A_2, {\bf x_2},a_2,\alpha_2, {\bf y_2}, {\bf z_2}, \beta_2)$ such that
$dp_{t_1}(A_1, {\bf x_1},a_1,\alpha_1, {\bf y_1}, {\bf z_1}, \beta_1)=$ true and
$dp_{t_2}(A_2, {\bf x_2},a_2,\alpha_2, {\bf y_2}, {\bf z_2}, \beta_2)=$ true, where

* $A=A_1=A_2$;

* $x(i)=x_1(i)+x_2(i)-d_A(v_i)$ for all $i\in A$, and $x(i)=0$ if $i\notin A$;

* $a=a_1+a_2-|A|$;

* $\alpha=\alpha_1+\alpha_2-\gamma+\delta $; $\gamma $ is the cardinality of the set

$$ \Big\{ v_j\in A~|~ x_1(j) \geq \frac{d_G(v_i)-1}{2}; ~x_2(j) \geq \frac{d_G(v_i)-1}{2} \Big\} $$
and $\delta$ is
the cardinality of the set
$$ \Big\{ v_j\in A~|~ x_1(j) < \frac{d_G(v_i)-1}{2}; ~x_2(j) < \frac{d_G(v_i)-1}{2}; ~x(j) \geq \frac{d_G(v_i)-1}{2}  \Big\}. $$

To compute $\alpha$ from $\alpha_1+\alpha_2$, we need to subtract the number of those $v_j$ which
are satisfied in both the
branches and add the number of vertices $v_j$ not satisfied in either of the branches $t_1$ and $t_1$
but satisfied in $t$.

\[ y(j) =
\begin{cases}
\text{$g$} &\quad\text{if $y_1(j)=g$ or $y_2(j)=g$}\\
\text{$b$} &\quad\text{otherwise}\\
%\text{$0$} &\quad\text{otherwise}\\
\end{cases}
\]

* $z(S)=z_1(S)+z_2(S)$ for all $S\subseteq A$;

* $\beta=\beta_1+\beta_2-|\Big\{j~:~y_1(j)=g, y_2(j)=g\Big\}|$.

For a join node $t$, there are  $n^k$ possible pairs for $(\bf {x_1,x_2})$ as ${\bf x_2}$ is uniquely determined by ${\bf x_1}$;
$n+1$ possible pairs for $(a_1,a_2)$; $n+1$ possible pairs for $(\alpha_1,\alpha_2)$; there are
$2^k$ possible pairs for $(\bf {y_1,y_2})$ as ${\bf y_2}$ is uniquely determined by ${\bf y_1}$; there are
$n^{2^k}$ possible pairs for $(\bf {z_1,z_2})$ as ${\bf z_2}$ is uniquely determined by ${\bf z_1}$; and
$n+1$ possible pairs for $(\beta_1,\beta_2)$. In total, there are
$2^kn^{O(2^k)}$ candidates, and each of them can be checked in $O(1)$ time. Thus, for a join node $t$,
$dp_t(A, {\bf x}, a,\alpha, {\bf y}, {\bf z}, \beta)$ can be computed in $2^kn^{O(2^k)}$ time.

At the root node $r$, we look at all records such that $dp_r(\emptyset, {\bf x}, a,\alpha, {\bf y}, {\bf z}, \beta)$= true, and  $a=\alpha=\beta$. The size of a maximum locally minimal defensive alliance is the maximum $a$ satisfying
$dp_r(\emptyset, {\bf x}, a,a, {\bf y}, {\bf z}, a)$= true.

§ CONCLUSION
The main contributions in this paper are that the
Locally Minimal Defensive Alliance problem is NP-complete on planar graphs, FPT
when parameterized by neighborhood diversity, and XP in treewidth. We proved that
connected locally minimal strong defensive alliance is polynomial time solvable on trees; we gave a
color coding algorithm for the exact connected locally minimal defensive alliance problem.
We also proved that exact connected locally minimal defensive alliance is W[1]-hard when
parameterized by the treewidth of the input graph. We list some nice problems emerge from the results here: is the problem FPT in treewidth, and does it admit a polynomial kernel in neighborhood diversity? Also, noting that the result for neighborhood diversity implies that the problem is FPT in vertex cover, it would be interesting to consider the parameterized complexity with respect to twin cover. The modular width parameter also appears to be a natural parameter to consider here, and since there are graphs with bounded modular-width and unbounded neighborhood diversity; we believe this is also an
interesting open problem.  The parameterized complexity of the Locally Minimal Defensive Alliance  problem
remains unsettle  when parameterized by other important
structural graph parameters like clique-width.

[1]
C. Bazgan, H. Fernau, and Z. Tuza.
Aspects of upper defensive alliances.
Discrete Applied Mathematics, 266:111 – 120, 2019.

[2]
B. Bliem and S. Woltran.
Defensive alliances in graphs of bounded treewidth.
Discrete Applied Mathematics, 251:334 – 339, 2018.

[3]
A. Cami, H. Balakrishnan, N. Deo, and R. Dutton.
On the complexity of finding optimal global alliances.
J. Combin. Math. Combin. Comput., 58:23–31, 2006.

[4]
R. Enciso.
PhD thesis, USA, 2009.

[5]
M. R. Fellows, D. Lokshtanov, N. Misra, F. A. Rosamond, and S. Saurabh.
Graph layout problems parameterized by vertex cover.
In S.-H. Hong, H. Nagamochi, and T. Fukunaga, editors, Algorithms and Computation, pages 294–305, Berlin, Heidelberg, 2008.
Springer Berlin Heidelberg.

[6]
H. Fernau and D. Raible.
Alliances in graphs: a complexity-theoretic study.
In Proceeding Volume II of the 33rd International Conference on
Current Trends in Theory and Practice of Computer Science, 2007.

[7]
H. Fernau and J. A. Rodriguez-Velazquez.
A survey on alliances and related parameters in graphs.
Electronic Journal of Graph Theory and Applications, 2(1),

[8]
H. Fernau, J. A. Rodríguez, and J. M. Sigarreta.
Offensive r-alliances in graphs.
Discrete Applied Mathematics, 157(1):177 – 182, 2009.

[9]
G. Fricke, L. Lawson, T. Haynes, M. Hedetniemi, and S. Hedetniemi.
A note on defensive alliances in graphs.
Bulletin of the Institute of Combinatorics and its
Applications, 38:37–41, 2003.

[10]
K. Hassan-Shafique.
Partitioning a graph in alliances and its application to data

[11]
J. D. Horton and K. Kilakos.
Minimum edge dominating sets.
SIAM Journal on Discrete Mathematics, 6(3):375–387, 1993.

[12]
L. H. Jamieson, S. T. Hedetniemi, and A. A. McRae.
The algorithmic complexity of alliances in graphs.
Journal of Combinatorial Mathematics and Combinatorial
Computing, 68:137–150, 2009.

[13]
R. Kannan.
Minkowski's convex body theorem and integer programming.
Mathematics of Operations Research, 12(3):415–440, 1987.

[14]
P. Kristiansen, M. Hedetniemi, and S. Hedetniemi.
Alliances in graphs.
Journal of Combinatorial Mathematics and Combinatorial
Computing, 48:157–177, 2004.

[15]
M. Lampis.
Algorithmic meta-theorems for restrictions of treewidth.
Algorithmica, 64(1):19–37, 2012.

[16]
H. W. Lenstra.
Integer programming with a fixed number of variables.
Mathematics of Operations Research, 8(4):538–548, 1983.

[17]
D. Manlove.
In Minimaximal and maximinimal optimisation problems: a partial
order-based approach, 1998.

[18]
C. R., M. M., R. I., and S. N.
Small alliances in graphs.
In Kučera L., Kučera A. (eds) Mathematical Foundations of
Computer Science, MFCS 2007, Lecture Notes in Computer Science, volume 4708,
Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

[19]
J. Rodríguez-Velázquez and J. Sigarreta.
Global offensive alliances in graphs.
Electronic Notes in Discrete Mathematics, 25:157 – 164, 2006.

[20]
J. Sigarreta, S. Bermudo, and H. Fernau.
On the complement graph and defensive k-alliances.
Discrete Applied Mathematics, 157(8):1687 – 1695, 2009.

[21]
J. Sigarreta and J. Rodríguez.
On defensive alliances and line graphs.
Applied Mathematics Letters, 19(12):1345 – 1350, 2006.

[22]
J. Sigarreta and J. Rodríguez.
On the global offensive alliance number of a graph.
Discrete Applied Mathematics, 157(2):219 – 226, 2009.

[23]
S. Szeider.
Not so easy problems for tree decomposable graphs.
CoRR, abs/1107.1177, 2011.

[24]
M. Tedder, D. Corneil, M. Habib, and C. Paul.
Simpler linear-time modular decomposition via recursive factorizing
In Automata, Languages and Programming, pages 634–645, Berlin,
Heidelberg, 2008. Springer Berlin Heidelberg.

[25]
M. Yannakakis and F. Gavril.
Edge dominating sets in graphs.
SIAM Journal on Applied Mathematics, 38(3):364–372, 1980.

§ AN ILLUSTRATION OF THE ALGORITHM IN SECTION <REF>

Consider the tree shown in Figure <ref>.

\[\begin{tikzpicture}[scale=0.6]
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
\vertex (x1) at (0,0) [label=above:$x_1$] {};
\vertex (x2) at (-1,-1) [label=left:$x_2$] {};
\vertex (x3) at (1,-1) [label=right:$x_3$] {};
\vertex (x4) at (0,-2) [label=below:$x_4$] {};
\vertex (x5) at (2,-2) [label=right:$x_5$] {};
\vertex (x6) at (3, -3) [label=right:$x_6$] {};
\path
% Note that the word "path" here isn't used in the graph-theory sense; the \path command
% is always used prior to the list of edges; here, coincidentally, they do form an actual path.
(x1) edge (x2)
(x1) edge (x3)
(x3) edge (x4)
(x3) edge (x5)
(x5) edge (x6)
;   % This semicolon ends the \path command.
\end{tikzpicture}\]

The largest locally minimal strong defensive alliances of $T$ are $\{x_{1},x_{3},x_{4}\}$ and $\{x_{1},x_{3},x_{5}\}$

For a leaf node $x\in \{x_2,x_4,x_6\}$, we have  $A_x(0)=0$, $A_x(m_{g}^{p})=A_x(o_{g}^{p})=A_x(o_{g}^{\bar{p}})=A_x(m_{g}^{\bar{p}})=A_x(o_{b}^{p})=-\infty$ and
For non-leaf node
$x_5$, we have $ A_{x_5}(0)= \max\Big\{A_{x_6}(0), A_{x_6}(m_{g}^{\bar{p}}), A_{x_6} (o_{g}^{\bar{p}})\Big\}=\max\{0, -\infty, -\infty\}=0$. Since $d=1$, we have $A_{x_{5}}(m^{p}_{g})= -\infty$ and $\lceil\frac{d+1}{2}\rceil-1=0$. Therefore

\begin{equation*}
A_{x_{5}}(m_{g}^{\bar{p}}) = 1 + \max\{A_{x_{6}}(m^{p}_{g}),A_{x_{6}}(m^{p}_{b})\}=1 + \max\{-\infty,1\} =2
\end{equation*}

\begin{equation*}
A_{x_{5}}(o_{g}^{p})  = A_{x_{5}}(o_{g}^{\bar{p}})  = 1 + A_{x_{5}}(m^{p}_{g}) = 1+ (-\infty) = -\infty.
\end{equation*}

Next, we consider the states $o^{p}_{b}$ and $m^{p}_{b}$. We have
$A_{x_{5}}(o_{b}^{p}) = 1 + A_{x_{5}}(o^{p}_{g}) = 1 + (-\infty) = -\infty$
and $A_{x_{5}}(m_{b}^{p}) = 1 $.
For non-leaf node $x_3$, we have $d=2$;

\begin{equation*}
\begin{split}
A_{x_3}(0) &= \max\Big\{A_{x_4}(0), A_{x_4}(m^{\bar{p}}_{g}), A_{x_4} (o^{\bar{p}}_{g}), A_{x_5}(0), A_{x_5}(m^{\bar{p}}_{g}), A_{x_5} (o^{\bar{p}}_{g})\Big\} \\
&= \max\{0,-\infty,-\infty,0,2,-\infty \}=2
\end{split}
\end{equation*}

and the associated locally minimal defensive
alliance is $\{x_5,x_6\}$. For the state  $m^p_g$, we have

\begin{equation*}
\begin{split}
A_{x_3}(m^{p}_{g})& =1+\max\limits_{x\in \mathcal{C}_1}\{\max\Big\{ A_x(1_{og}), A_x (1_{ob})\Big\} \}\\
&= 1+\max\Big\{ A_{x_4}(m^{p}_{g}), A_{x_4}(m^{p}_{b}),A_{x_5}(m^{p}_{g}), A_{x_5}(m^{p}_{b})\Big\}\\
&=1+ \max\{-\infty,1,-\infty, 1\}=2.
\end{split}
\end{equation*}

For the state $m^{\bar{p}}_g$, we have

\begin{equation*}
\begin{split}
A_{x_3}(m^{\bar{p}}_{g})& =1+\max \Big\{ \max \Big\{ A_{x_{4}}(m^{p}_{g}), A_{x_{4}} (m^{p}_{b})\Big\} + \max\Big\{ A_{x_{5}}(m^{p}_{g}), A_{x_{5}}(m^{p}_{b}), A_{x_{5}}(o^{p}_{g}), A_{x_{5}}(o^{p}_{b}) \Big\}, \\
&\max \Big\{ A_{x_{5}}(m^{p}_{g}), A_{x_{5}} (m^{p}_{b})\Big\} + \max\Big\{ A_{x_{4}}(m^{p}_{g}), A_{x_{4}}(m^{p}_{b}), A_{x_{4}}(o^{p}_{g}), A_{x_{4}}(o^{p}_{b}) \Big\} \Big\}\\
&=1+ \max\{2,2\}=3,
\end{split}
\end{equation*}

and the associated locally minimal defensive
alliances are $\{x_3,x_4,x_5\}$ and $\{x_3,x_5,x_6\}$. Next, we get

\begin{equation*}
\begin{split}
A_{x_{3}}(o^{p}_{g}) &= 1 + \max \Big\{ A_{x_{4}}(m^{p}_{g}) + \max \Big\{ A_{x_{5}}(m^{p}_{g}),A_{x_{5}}(o^{p}_{g}), \\
& A_{x_{5}}(m^{p}_{g}) + \max \Big\{ A_{x_{4}}(m^{p}_{g}),A_{x_{4}}(o^{p}_{g})\Big\} \Big\}\\
&= 1 + \max\{-\infty,-\infty\}=-\infty
\end{split}
\end{equation*}

Similarly, since $A_{x_{4}}(m^{p}_{g}) = A_{x_{5}}(m^{p}_{g}) = -\infty $, we get $A_{x_{3}}(o^{\bar{p}}_{g}) = -\infty$. As $A_{x_{4}}(o^{p}_{g}) = A_{x_{5}}(o^{p}_{g}) = -\infty $,  we get $A_{x_{3}}(o^{p}_{b})=1+(-\infty)=-\infty$. As
$A_{x_{4}}(o^{p}_{g})= A_{x_{4}}(o^{p}_{b})= A_{x_{5}}(o^{p}_{g})= A_{x_{5}}(o^{p}_{b})= -\infty$, we get $A_{x_{3}}(m^{p}_{b})= 1 + (-\infty) = -\infty$.
Finally, for the root
node $x_1$, we have $d=2$ and

\begin{equation*}
\begin{split}
A_{x_1}(0) &= \max\Big\{A_{x_2}(0), A_{x_2}(m_{g}^{\bar{p}}), A_{x_2} (o_{g}^{\bar{p}}), A_{x_3}(0), A_{x_3}(m_{g}^{\bar{p}}), A_{x_3} (o_{g}^{\bar{p}})\Big\}\\
&= \max\{0,-\infty,-\infty,2,3,-\infty\}=3.
\end{split}
\end{equation*}

As $A_{x_{2}}(m^{p}_{g}) = A_{x_{3}}(m^{p}_{g}) = -\infty $,
we get $A_{x_{1}}(o^{\bar{p}}_{g})=-\infty$. Next

\begin{equation*}
\begin{split}
A_{x_{1}}(m^{\bar{p}}_{g}) &= 1 + \max \Big \{ \max\{ A_{x_{2}}(m^{p}_{g}),A_{x_{2}}(m^{p}_{b})\}, \max\{A_{x_{3}}(m^{p}_{g}),A_{x_{3}}(m^{p}_{b})\}  \Big\}\\
&= 1+2=3.
\end{split}
\end{equation*}

The associated connected locally minimal strong defensive alliances are $\{x_{1},x_{3},x_{4}\}$ and $\{x_{1},x_{3},x_{5}\}$.
Therefore, the size of the largest locally minimal strong defensive alliance is

§ POLYNOMIAL-TIME ALGORITHM FOR CONNECTED LOCALLY MINIMAL STRONG DEFENSIVE ALLIANCE ON TREES (NEW)

Finding the largest connected locally minimal (strong) defensive alliance is believed to be intractable [1]. However,
when the graph happens to be a tree, we solve the problem in polynomial time, using dynamic programming.
Here we consider strong defensive alliances where the vertex itself is not considered in the inequality.
A defensive alliance is strong if each vertex has at least as many neighbours in the alliance (not counting itself) as outside the alliance.
Also recall that if $S$ is a locally minimal (strong) defensive alliance,
then for every vertex $v \in S$, at least one of its neighbours in $S$ is marginally protected.
A vertex $v\in S$ is said to be
good if it has at least one marginally protected children in $S$, otherwise it is called a
bad vertex. Let $v$ be a non-root node with children $v_1,v_2,\ldots,v_d$, that is, $d(v)=d+1$. We define different possible states of a vertex $v$  based on three criterion's

* whether the vertex is part of the solution or not

* whether one of the children is marginally protected or not(good or bad)

* whether the parent of the vertex is in the solution or not

as follows:

* $0$: vertex $v$ is not in the solution.

* $\hat{1}^{1}_{g}:$ vertex $v$ is marginally protected, parent of $v$ is in the solution and one of the children is marginally protected.

* $\hat{1}^{1}_{b}$ vertex $v$ is marginally protected, parent of $v$ is in the solution and none of the children are marginally protected.

* $1^{1}_{b}:$ vertex $v$ is over protected, parent of $v$ is in the solution and none of the children are marginally protected.

* $1^{1}_{g}:$ vertex $v$ is over protected, parent of $v$ is in the solution and one of the children is marginally protected.

* $\hat{1}^{0}_{g}:$  vertex $v$ is marginally protected, parent of $v$ is not in the solution and one of the children is marginally protected.

* $1^{0}_{g}:$  vertex $v$ is over protected, parent of $v$ is not in the solution and one of the children is marginally protected.

Here is the algorithm: Start by rooting the tree at any node $v$. Each node defines a subtree, the one hanging from it. This immediately suggests subproblems:
$A_v(s)$= the size of the largest connected locally minimal strong defensive alliance
of the subtree rooted at $v$ and the state of $v$ is $s$;
if no connected locally minimal strong defensive alliance exists,  we put $A_v(s)=-\infty$.
Our final goal is to
compute $\max\Big\{ A_r(0), A_r(\hat{1}^{0}_{g}),A_r(1^{0}_{g})\Big\}$ where $r$ is the root of $T$.

Leaf Node: For a leaf node $v$, we have  $A_v(0)=0$. Note that as the leaf do not have any children, we have   $A_v(\hat{1}^{1}_{g})=-\infty, A_v(1^{1}_{g})=-\infty, A_v(1^{0}_{g})=-\infty, A_v(\hat{1}^{0}_{g})=-\infty$. As $v$ is a one degree vertex, it cannot be overprotected in the solution. Therefore, we get $A_v(1^{1}_{b})=-\infty$. We have $A_v(\hat{1}^{1}_{b})=1$ as it is a valid state.

Non-leaf Node: Let $v$ be a non-leaf node with the set $\mathcal{C}=\{v_1,v_2,\ldots, v_d\}$ of children.
Suppose we know $A_{v_i}(s)$ for all children $v_i$ of $v$. How can we compute $A_v(s)$?
We now consider the following cases:

Case 1: Let the state of $v$ be $0$, that is, $v$ is not included in the solution.
Therefore, we move on to $v$'s children
and consider the best of their solutions. Then

$$ A_v(0)= \max\limits_{x\in \mathcal{C}}{\Big\{A_{x}(0), A_{x}(\hat{1}^{0}_{g}), A_{x}(1^{0}_{g})\Big\} }. $$

Case 2: Let the state of $v$ be $\hat{1}_g^{1}$ or $\hat{1}_g^{0}$ . Here $v$ is a good vertex and
therefore, must have a marginally protected child in $S$. Therefore, one of the child $v_i$ has a label
$\hat{1}^{1}_g$ or $\hat{1}^{1}_b$, then while  $v$ is included in $S$, $v_i$ becomes marginally protected.
Next, we take $(v_1,v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{ A_{v_i}(\hat{1}^{1}_{g}), A_{v_i}(\hat{1}^{1}_{b}), A_{v_i}(1^{1}_{g}), A_{v_i}(1^{1}_{b})\}$, that is,
$$\max\{ A_{v_1}(\hat{1}^{1}_{g}), A_{v_1}(\hat{1}^{1}_{b}), A_{v_1}(1^{1}_{g}), A_{v_1}(1^{1}_{b})\}
\geq \ldots \geq \max\{ A_{v_d}(\hat{1}^{1}_{g}), A_{v_d}(\hat{1}^{1}_{b}), A_{v_d}(1^{1}_{g}), A_{v_d}(1^{1}_{b})\}.$$

Let $\mathcal{C}_{k,i}$ be the set of first $k$ children from the ordering
$(v_1, v_2,\ldots, v_d)$
except vertex $v_i$. Thus, we have

\begin{equation*}
\begin{split}
A_v(\hat{1}^{1}_g) & =1+ \max\limit_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(\hat{1}^{1}_g), A_{v_i}(\hat{1}^{1}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-2,i}}{\max\{A_{x}(\hat{1}^{1}_g), A_{x}(\hat{1}^{1}_b), A_{x}(1^{1}_{g}), A_x (1^{1}_{b})\} }\Bigg\},
\end{split}
\end{equation*}

In the case $d=1$, we take $A_{v}(\hat{1}^{1}_{g})=-\infty$ as the state is invalid.

Suppose the state of $v$ is $\hat{1}^{0}_{g}$, that is, $v$ is marginally protected by its children and
one of them is marginally protected. Since the parent of $v$ is not there in the solution, we have

\begin{equation*}
\begin{split}
A_v(\hat{1}^{0}_{g}) & =1+ \max\limit_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(\hat{1}^{1}_g), A_{v_i}(\hat{1}^{1}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}}{\max\{A_{x}(\hat{1}^{1}_g), A_{x}(\hat{1}^{1}_b), A_{x}(1^{1}_{g}), A_x (1^{1}_{b})\} }\Bigg\}
\end{split}
\end{equation*}

Case 3: Let the state of $v$ be $1^{1}_g$.  Here $v$ is a good vertex and
therefore, must have a marginally protected child in $S$.
Here $v \in S$ is overprotected, therefore, all the children must be good.
Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{A_{v_i}(\hat{1}^{1}_g), A_{v_i}(1^{1}_{g})\}$.
Let $\mathcal{C}_{k,i}$ be the set of first $k$ children from the ordering
$(v_1, v_2,\ldots, v_d)$
except vertex $v_i$.
We have the following recurrence relation:

\begin{equation*}
\begin{split}
A_v(1^{1}_g) & =1+ \max\limit_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(\hat{1}_g)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}}{\max\{A_{x}(\hat{1}^{1}_g), A_{x}(1^{1}_{g})\} } \\
& +
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}\cup \{v_i\}\big )} \max\Big(0, A_{x}(\hat{1}^{1}_{g}), A_{x}(1^{1}_{g})\Big)  \Bigg\},
\end{split}
\end{equation*}

Case 4: Let the state of $v$ be $1^{1}_b$.  Here $v$ is a bad vertex and
therefore, none of the children are marginally protected in $S$. Here $v \in S$ is overprotected, therefore, all the children must be good. Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\{A_{v_i}(1^{1}_{g})\}$. Let $\mathcal{C}_{\lceil \frac{d+1}{2} \rceil} = \{v_{1},\ldots,v_{\lceil \frac{d+1}{2} \rceil} \} $.
We have the following recurrence relation:

\begin{equation*}
\begin{split}
A_v(1^{1}_b) & =1+  \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil}} A_{x}(1^{1}_{g})  \\
& +
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil}\big )} \max\Big(0, A_{x}(1^{1}_{g})\Big)  \Bigg\},
\end{split}
\end{equation*}

Case 5: Let the state of $v$ be $\hat{1}^{1}_b$.  Here $v$ is a bad vertex and
therefore, none of the children are marginally protected in $S$. Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{A_{v_i}(1^{1}_{g}), A_{v_i}(1^{1}_{b})\}$.
We have the following recurrence relation:

\begin{equation*}
A_{v}(\hat{1}^{1}_{b}) = 1 + \sum\limits_{x\in \mathcal{C}_{\lceil \frac{d+1}{2} \rceil-1}} \max \{ A_{x}(1^{1}_{g}), A_{x}(1^{1}_{b}) \}
\end{equation*}

Case 6: Let the state of $v$ be $1^{0}_g$.  Here $v$ is a good vertex and
therefore, must have a marginally protected child in $S$.
Here $v \in S$ is overprotected, therefore, all the children must be good.
Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{A_{v_i}(\hat{1}^{1}_g), A_{v_i}(1^{1}_{g})\}$.
Let $\mathcal{C}_{k,i}$ be the set of first $k$ children from the ordering
$(v_1, v_2,\ldots, v_d)$
except vertex $v_i$.
We have the following recurrence relation:

\begin{equation*}
\begin{split}
A_v(1^{0}_g) & =1+ \max\limit_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(\hat{1}^{1}_g)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}}{\max\{A_{x}(\hat{1}^{1}_g), A_{x}(1^{1}_{g})\} } \\
& +
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}\cup \{v_i\}\big )} \max\Big(0, A_{x}(\hat{1}^{1}_{g}), A_{x}(1^{1}_{g})\Big)  \Bigg\},
\end{split}
\end{equation*}

For computation of $A_r(\hat{1}^{0}_{g})$ and $A_r(1^{0}_{g})$, we replace $d$ by $d-1$ in the above recurrence
relations as the root  node $r$ with $d$ children has degree $d$, whereas any other non-leaf node
with $d$ children has degree $d+1$.

The running time of this algorithm is easy to analyze.  At each node $v\in V(T)$,  we compute
$A_v(s)$ where $s$ is a state of $v$. The time required to get descending ordering of the children
of $v_i$ is $O(d_i\log d_i)$, where $d_i$ is the number of children of vertex $v_i$.
The number of subproblems is exactly the number of vertices in $T$. The total running time is
therefore equal to  $ c\sum {d_i \log d_i}\leq c \log n\sum{d_i}=cn\log n = O(n \log n)$, where  $c$ is a constant.

§.§ An Illustration of the Algorithm
Consider the tree shown in Figure <ref>.

\[\begin{tikzpicture}[scale=0.6]
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
\vertex (x1) at (0,0) [label=above:$x_1$] {};
\vertex (x2) at (-1,-1) [label=left:$x_2$] {};
\vertex (x3) at (1,-1) [label=right:$x_3$] {};
\vertex (x4) at (0,-2) [label=below:$x_4$] {};
\vertex (x5) at (2,-2) [label=right:$x_5$] {};
\vertex (x6) at (3, -3) [label=right:$x_6$] {};
\path
% Note that the word "path" here isn't used in the graph-theory sense; the \path command
% is always used prior to the list of edges; here, coincidentally, they do form an actual path.
(x1) edge (x2)
(x1) edge (x3)
(x3) edge (x4)
(x3) edge (x5)
(x5) edge (x6)
;   % This semicolon ends the \path command.
\end{tikzpicture}\]

The largest locally minimal strong defensive alliance of $T$ is $\{x_1,x_2,x_5,x_6\}$.

For a leaf node $x=x_2,x_4,x_6$, we have  $A_x(0)=0$, $A_x(\hat{1}_b)=1$;
$A_x(\hat{1}_g)=A_x(1_{mg})=A_x(1_{ob})=A_x(1_{og})=-\infty.$ For non-leaf node
$x_5$, we have $d=1$, and hence $C_{\lceil\frac{d}{2}\rceil-1}=C_0=\emptyset$.
$$A_{x_5}(\hat{1}_b) =1+\sum\limits_{x\in \emptyset}{\max\Big\{ A_x(1_{og}), A_x (1_{ob})\Big\} } +
{A_{x_6}(0)}=1+0+0=1; $$

$A_{x_5}(1_{ob})=-\infty$ as   $x_5$ does not have at least $\lceil\frac{d+1}{2}\rceil+1=2$ overprotected (non-leaf) children and $A_{x_5}(\hat{1}_g)=1$ as $x_5$ has only one child ($d=1$);

\begin{equation*}
\begin{split}
A_{x_5}(1_{mg}) & = 1+ \max\{A_{x_6}(\hat{1}_g), A_{x_6}(\hat{1}_b)\}\\
& + \sum\limits_{x\in \emptyset}{\max\{A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_x (1_{ob})\} }
\sum\limits_{x\in \emptyset} {A_x(0)}\\
\end{split}
\end{equation*}

$ A_{x_5}(0)= \max\Big\{A_{x_6}(0), A_{x_6}(1_{og}), A_{x_6} (1_{mg})\Big\}=\max\{0, -\infty, -\infty\}=0$
and  $A_{x_5}(1_{og})=-\infty$ as $x_5$ does not have at least $\lceil\frac{d+1}{2}\rceil+1=2$ non-leaf children.
For non-leaf node $x_3$, we have $d=2$;
$A_{x_3}(0)= \max\Big\{A_{x_4}(0), A_{x_4}(1_{og}), A_{x_4} (1_{mg})\Big\}
+\max\Big\{A_{x_5}(0), A_{x_5}(1_{og}), A_{x_5} (1_{mg})\Big\}=0+2=2$ and the associated locally minimal defensive
alliance is $\{x_5,x_6\}$;

\begin{equation*}
\begin{split}
A_{x_3}(\hat{1}_b)& =1+\sum\limits_{x\in \mathcal{C}_1}{\max\Big\{ A_x(1_{og}), A_x (1_{ob})\Big\} } +
\sum\limits_{x\in \mathcal{C}\setminus \mathcal{C}_{1}} {A_x(0)}\\
&= 1+\max\Big\{ A_{x_4}(1_{og}), A_{x_4}(1_{ob})\Big\}+ A_{x_5}(0)\\
\end{split}
\end{equation*}

\begin{equation*}
\begin{split}
A_v(\hat{1}_g) & =1+ \max\{A_{x_5}(\hat{1}_g), A_{x_5}(\hat{1}_b)\}\\
& + \sum\limits_{x\in \emptyset}{\max\{A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_x (1_{ob})\} }
+  {A_{x_4}(0)}\\
\end{split}
\end{equation*}

and the associated locally minimal defensive alliance is $\{x_3,x_5\}$;

\begin{equation*}
\begin{split}
A_{x_3}(1_{mg}) & = 1+ \max\{A_{x_5}(\hat{1}_g), A_{x_5}(\hat{1}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{1}}{\max\{A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_x (1_{ob})\} }
\sum\limits_{x\in \emptyset} {A_x(0)}\\
&=1+\max\{A_{x_5}(\hat{1}_g), A_{x_5}(\hat{1}_b)\}+ \max\{A_{x_4}(\hat{1}_g), A_{x_4}(\hat{1}_b), A_{x_4}(1_{og}), A_{x_4} (1_{ob})\}+0\\
\end{split}
\end{equation*}

and the associated locally minimal defensive alliance is $\{x_3,x_4,x_5\}$;
and $A_{x_3}(1_{og})=-\infty$.
Finally, for the root
node $x_1$, we have $d=2$ and  $A_{x_1}(0)=3$ and the associated locally minimal defensive alliance is $\{x_3,x_4,x_5\}$;

\begin{equation*}
\begin{split}
A_{x_1}(1_{mg}) & = 1+ \max\{A_{x_2}(\hat{1}_g), A_{x_2}(\hat{1}_b)\}+
\end{split}
\end{equation*}

and the associated locally minimal defensive alliance is $\{x_1,x_2,x_5,x_6\}$; and $A_{x_1}(1_{sg})=-\infty$ as $x_1$ does not have
at least $\lceil\frac{d}{2}\rceil+1=2$ non-leaf children.
Therefore, the size of the largest locally minimal strong defensive alliance is
$\max\{A_{x_1}(0),A_{x_1}(1_{mg}),A_{x_1}(1_{og}) \}=4$; and the
largest locally minimal strong defensive alliance is $\{x_1,x_2,x_5,x_6\}$.

§ POLYNOMIAL-TIME ALGORITHM FOR LOCALLY MINIMAL STRONG DEFENSIVE ALLIANCE ON TREES

Finding the largest locally minimal (strong) defensive alliance is believed to be intractable [1]. However,
when the graph happens to be a tree, we solve the problem in polynomial time, using dynamic programming.
Here we consider strong defensive alliances where the vertex itself is not considered in the inequality.
A defensive alliance is strong if each vertex has at least as many neighbours in the alliance (not counting itself) as outside the alliance.
Also recall that if $S$ is a locally minimal (strong) defensive alliance,
then for every vertex $v \in S$, at least one of its neighbours in $S$ is marginally protected.
A vertex $v\in S$ is said to be
good if it has at least one marginally protected neighbour in $S$, otherwise it is called a
bad vertex. Let $v$ be a non-root node with children $v_1,v_2,\ldots,v_d$, that is, $d(v)=d+1$.
Then a vertex $v \in S$ is  marginally unprotected by its children if
$\lceil\frac{d+1}{2}\rceil-1$  of its children are in $S$; thus the parent of $v$ must be in
$S$ for protection of $v$; whereas $v\in S$ is overprotected
by its children if at least
$\lceil\frac{d+1}{2}\rceil+1$  of its children are in $S$.
We define different possible states of a vertex $v$ as follows:

* $0$: vertex $v$ is not in the solution.

* $\hat{1}_b:$ vertex $v$ is marginally unprotected by its children and none of its children is marginally protected.

* $\hat{1}_g:$ vertex $v$ is marginally unprotected by its children and  at least one of its children is marginally protected.

* $1_{mg}:$ vertex $v$ is marginally protected by its children and  at least one of its children
is marginally protected.

* $1_{ob}:$ vertex $v$ is overprotected by its children and none of the children is marginally protected.

* $1_{og}:$ vertex $v$ is overprotected by its children and at least one of its children is marginally protected.

Here is the algorithm: Start by rooting the tree at any node $v$. Each node defines a
subtree, the one hanging from it. This immediately suggests subproblems:
$A_v(s)$= the size of the largest locally minimal defensive alliance
of the subtree rooted at $v$ and the state of $v$ is $s$;
if no locally minimal defensive alliance exists,  we put $A_v(s)=-\infty$.
Our final goal is to
compute $\max\Big\{ A_r(0), A_r(1_{og}), A_r(1_{mg})\Big\}$ where $r$ is the root of $T$.

Leaf Node: For a leaf node $v$, we have  $A_v(0)=0$, $A_v(\hat{1}_b)=1$. As $v$ has
no children, it cannot have a marginally protected children; therefore, we have
$A_v(\hat{1}_g)=A_v(1_{mg})=A_v(1_{og})=-\infty$. Similarly, as $v$ has no children, it cannot be
overprotected by its children; therefore, we have $A_v(1_{ob})=-\infty$.

Non-leaf Node: Let $v$ be a non-leaf node with the set $\mathcal{C}=\{v_1,v_2,\ldots, v_d\}$ of children.
Suppose we know $A_{v_i}(s)$ for all children $v_i$ of $v$. How can we compute $A_v(s)$?
We now consider the following cases:

Case 1: Let the state of $v$ be $0$, that is, $v$ is not included in the solution.
We know that locally minimal defensive alliance can be disconnected. Therefore, we move on to $v$'s children
and consider sum of their solutions. Then

$$ A_v(0)= \sum\limits_{x\in \mathcal{C}}{\max\Big\{A_{x}(0), A_{x}(1_{og}), A_x (1_{mg})\Big\} }. $$

Case 2: Let the state of $v$ be $\hat{1}_b$ or $1_{ob}$.
Let $(v_1,v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{ A_{v_i}(1_{og}), A_{v_i}(1_{ob})\}$, that is,
$$\max\{ A_{v_1}(1_{og}), A_{v_1}(1_{ob})\}
\geq \ldots \geq \max\{ A_{v_d}(1_{og}), A_{v_d}(1_{ob})\}.$$

Let $\mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1}=\{v_1,v_2, \ldots, v_{\lceil\frac{d+1}{2}\rceil-1}\}$ and
$\mathcal{C}_{\lceil\frac{d+1}{2}\rceil+1}=\{v_1,v_2, \ldots, v_{\lceil\frac{d+1}{2}\rceil+1}\}$.
Suppose the state of $v$ is $\hat{1}_b$. That is,  $v$ is marginally unprotected by its overprotected children.
As the solution includes $v$,
we get one point for it, and we are allowed to include exactly
of its overprotected children  in $S$.
Thus, we have

$$A_v(\hat{1}_b) =1+\sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1}}{\max\Big\{ A_x(1_{og}), A_x (1_{ob})\Big\} } +
\sum\limits_{x\in \mathcal{C}\setminus \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1}} {A_x(0)}. $$

Suppose the state of $v$ is $1_{ob}$, that is, $v$ is overprotected by its children and
none of them is marginally protected.
As the solution includes $v$,
we get one point for it, and we are allowed to include  at least ${\lceil\frac{d+1}{2}\rceil+1}$
of its overprotected children  in $S$.
Thus, we have

\begin{equation*}
\begin{split}
A_v(1_{ob}) & =1+\sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil+1}}{\max\Big\{ A_x(1_{og}), A_x (1_{ob})\Big\} }\\
\sum\limits_{x\in \mathcal{C}\setminus \mathcal{C}_{\lceil\frac{d+1}{2}\rceil+1}} \max{\Big\{A_x(0), A_x(1_{og}), A_x (1_{ob})\Big\}}
\end{split}
\end{equation*}

In this case,
$v$ must have at least $\lceil\frac{d+1}{2}\rceil+1$ overprotected (non-leaf) children, otherwise, $A_v(1_{ob})=-\infty$.

Case 3: Let the state of $v$ be $\hat{1}_g$, $1_{mg}$ or $1_{og}$.  Here $v$ is a good vertex and
therefore, must have to a marginally protected child in $S$.
Note that if $v$ has a marginally unprotected
child $v_i$ in $S$ with label
$\hat{1}_g$ or $\hat{1}_b$, then while  $v$ is included in $S$, $v_i$ becomes marginally protected.
First, suppose the state of $v$ is $\hat{1}_g$. Here $v \in S$ is good and  marginally unprotected by its children, that is,
exactly  $\lceil\frac{d+1}{2}\rceil-1$  of its children are in $S$ and at least one of them is labelled
$\hat{1}_g$ or $\hat{1}_b$.
Let $(v_1, v_2,\ldots, v_d)$ be a descending ordering of $\mathcal{C}$ according
to values $\max\{A_{v_i}(\hat{1}_g), A_{v_i}(\hat{1}_b), A_{v_i}(1_{sg}), A_{v_i}(1_{sb})\}$.

Let $\mathcal{C}_{k,i}$ be the set of first $k$ children from the ordering
$(v_1, v_2,\ldots, v_d)$
except vertex $v_i$. As the solution includes $v$,
we get one point for it, and we need to include  one marginally unprotected child $v_i$ and
overprotected or marginally unprotected children  in $S$.
We have the following recurrence relations:

\begin{equation*}
\begin{split}
A_v(\hat{1}_g) & =1+ \max\limit_{v_i\in \mathcal{C}}\Bigg\{\max\{A_{v_i}(\hat{1}_g), A_{v_i}(\hat{1}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-2,i}}{\max\{A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_x (1_{ob})\} } \\
& +
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil-2,i}\cup \{v_i\}\big )} {A_x(0)}\Bigg\},
\end{split}
\end{equation*}

for $d\geq 2$, and $A_v(\hat{1}_g)=1$ for $d=1$.
Next, suppose the state of $v$ is  $1_{mg}$.  Here $v \in S$ is good and  marginally protected by its children, that is,
exactly  $\lceil\frac{d+1}{2}\rceil$  of its children are in $S$ and at least one of them is labelled
$\hat{1}_g$ or $\hat{1}_b$. We have the following
recurrence relation:

\begin{equation*}
\begin{split}
A_v(1_{mg}) & =1+ \max\limit_{v_i\in \mathcal{C}}\Big\{ \max\{A_{v_i}(\hat{1}_g), A_{v_i}(\hat{1}_b)\}\\
& + \sum\limits_{x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}}{\max\{A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_x (1_{ob})\} } \\
\sum\limits_{x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil-1,i}\cup \{v_i\}\big )} {A_x(0)}\Big\}
\end{split}
\end{equation*}

Finally, suppose the state of $v$ is $1_{og}$. Here $v \in S$ is  good and strongly protected by its children, that is,
at least  $\lceil\frac{d+1}{2}\rceil+1$  of its children are in $S$ and
at least one of these $\lceil\frac{d+1}{2}\rceil+1$ children is labelled
$\hat{1}_g$ or $\hat{1}_b$. We have the following
recurrence relation:

\begin{equation*}
\begin{split}
A_v(1_{og}) & = 1+\max\limit_{\mbox{non-leaf }v_i\in \mathcal{C}}\Bigg\{  \max\{A_{v_i}(\hat{1}_g), A_{v_i}(\hat{1}_b)\}\\
& + \sum\limits_{\mbox{non-leaf } x\in \mathcal{C}_{\lceil\frac{d+1}{2}\rceil,i}}{\max\{A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_x (1_{ob})\} } \\
\sum\limits_{\mbox{non-leaf } x\in \mathcal{C}\setminus \big(\mathcal{C}_{\lceil\frac{d+1}{2}\rceil,i}\cup \{v_i\}\big )}{ \max\{A_x(0),A_{x}(\hat{1}_g), A_{x}(\hat{1}_b), A_{x}(1_{og}), A_{x}(1_{ob}) \}}\Bigg\}.
\end{split}
\end{equation*}

We claim that if $v_i$ is a leaf node and its parent is overprotected then $v_i$ cannot be in $S$.
The reason is this. The only neighbour of $v_i$ is its parent $v$, which is overprotected,
therefore $v_i$ will never have a marginally protected neighbour, but every vertex in $S$ needs to have
a marginally protected neighbour.  Thus, in this case,
$v$ must have at least $\lceil\frac{d+1}{2}\rceil+1$ non-leaf children, otherwise, $A_v(1_{og})=-\infty$.
For computation of $A_r(1_{mg})$ and $A_r(1_{og})$, we replace $d$ by $d-1$ in the above recurrence
relations as the root  node $r$ with $d$ children has degree $d$, whereas any other non-leaf node
with $d$ children has degree $d+1$.

The running time of this algorithm is easy to analyze.  At each node $v\in V(T)$,  we compute
$A_v(s)$ where $s$ is a state of $v$. The time required to get descending ordering of the children
of $v_i$ is $O(d_i\log d_i)$, where $d_i$ is the number of children of vertex $v_i$.
The number of subproblems is exactly the number of vertices in $T$. The total running time is
therefore equal to  $ c\sum {d_i \log d_i}\leq c \log n\sum{d_i}=cn\log n = O(n \log n)$, where  $c$ is a constant.

§.§ An Illustration of the Algorithm
Consider the tree shown in Figure <ref>.

\[\begin{tikzpicture}[scale=0.6]
%% Notice in the first vertex is named (v) for the sake of a later edge,
%% and it also has a label to its left that is the math-mode $v$.
\vertex (x1) at (0,0) [label=above:$x_1$] {};
\vertex (x2) at (-1,-1) [label=left:$x_2$] {};
\vertex (x3) at (1,-1) [label=right:$x_3$] {};
\vertex (x4) at (0,-2) [label=below:$x_4$] {};
\vertex (x5) at (2,-2) [label=right:$x_5$] {};
\vertex (x6) at (3, -3) [label=right:$x_6$] {};
\path
% Note that the word "path" here isn't used in the graph-theory sense; the \path command
% is always used prior to the list of edges; here, coincidentally, they do form an actual path.