11institutetext: School of Computer and Information Sciences, University of
Hyderabad,
Hyderabad, India.
11email<EMAIL_ADDRESS>
# On the Tractability of Defensive Alliance Problem††thanks: Preliminary
version of this paper has appeared in 9th Annual International Conference on
Algorithms and Discrete Applied Mathematics, CALDAM 2023

Sangam Balchandar Reddy  Anjeneya Swami Kare

###### Abstract

Given a graph $G=(V,E)$, a non-empty set $S\subseteq V$ is a Defensive
Alliance, if for every vertex $v\in S$, the majority of its closed neighbours
are in $S$, that is, $|N_{G}[v]\cap S|\geq|N_{G}[v]\setminus S|$. The decision
version of the problem is known to be NP-Complete even when restricted to
split and bipartite graphs. The problem is fixed-parameter tractable for the
parameters solution size, vertex cover number and neighbourhood diversity. For
the parameters treewidth and feedback vertex set number, the problem is
W[1]-hard.
In this paper, we study the Defensive Alliance problem for graphs with bounded
degree. We show that the problem is polynomial-time solvable on graphs with
maximum degree at most 5 and NP-Complete on graphs with maximum degree 6. This
rules out the fixed-parameter tractability of the problem for the parameter
maximum degree of the graph. We also consider the problem from the standpoint
of parameterized complexity. We provide an FPT algorithm using the Integer
Linear Programming approach for the parameter distance to clique. We also
answer an open question posed in [9] by providing an FPT algorithm for the
parameter twin cover.

###### Keywords:

Defensive Alliance Bounded Degree Graphs Twin cover Distance to clique NP-
Complete FPT

##  1 Introduction

We, humans, form alliances for the sake of mutual benefit. This can often be
seen in politics, businesses, trades, etc. The main agenda behind the alliance
is to achieve a common goal between the parties. Based on this idea, the
alliances are classified as follows. An alliance is formed between the parties
of a group to defend against an attack from other parties (defensive alliance)
or to be able to attack other parties (offensive alliance). The concept of
alliances in graphs was first introduced by Kristiansen, Hedetniemi and
Hedetniemi [17]. The initial algorithmic results of the problem were given by
Jamieson [13]. Alliances in graphs have been well studied [2] and various
generalizations are also studied [7, 21].
A defensive alliance is a non-empty set $S\subseteq V$, such that for every
vertex $v\in S:|N_{G}[v]\cap S|\geq|N_{G}[v]\setminus S|$. We say that a
vertex $v$ is protected if it has at least as many closed neighbours inside
$S$ as it has outside $S$. The boundary of a set $S\subseteq V$ is denoted by
$\partial S$ and represents the vertices in the neighbourhood of $S$,
excluding $S$, i.e., $\partial S$ = $N[S]\setminus S$. An offensive alliance
is a non-empty set $S\subseteq V$, such that for every vertex $v\in\partial
S:|N_{G}[v]\cap S|\geq|N_{G}[v]\setminus S|$. A powerful alliance is both
defensive and offensive simultaneously. An alliance is global if it is also a
dominating set. In this paper, we confine our study to the DEFENSIVE ALLIANCE
problem. We define the decision version of the problem as follows:
DEFENSIVE ALLIANCE:
Input: A simple, undirected graph $G=(V,E)$, and a positive integer $k$.
Question: Is there a defensive alliance $S\subseteq V$ such that $|S|\leq k$?
The optimization version of the problem asks to compute the defensive alliance
with minimum cardinality.
Known results. There are polynomial time algorithms for finding minimum
alliances111By alliances, we mean defensive, offensive, and powerful alliance
problems in trees [1, 13]. Kiyomi and Otachi [16] have provided an XP
algorithm on graphs with bounded treewidth. There is a polynomial time
algorithm for finding a minimum defensive alliance in series-parallel graphs
[4]. Jamieson et al. [12] showed that the defensive alliance is NP-Complete
even when restricted to split and bipartite graphs. Gaikwad and Maity [9]
proved that the defensive alliance is NP-Complete on circle graphs. Fernau and
Raible [6] proved that the alliance problems, including their global versions,
are fixed-parameter tractable when parameterized by the solution size. Enciso
[4] proved that defensive and global defensive alliances are fixed-parameter
tractable parameterized by domino treewidth. Alliances are fixed-parameter
tractable when parameterized by vertex cover number of the input graph [16].
Recently, both the defensive and offensive alliances were also shown to be
fixed-parameter tractable parameterized by the neighborhood diversity of the
input graph [8]. Defensive alliance is W[1]-hard parameterized by a wide range
of parameters such as the feedback vertex set, treewidth, cliquewidth,
treedepth and pathwidth [9].
Our results. We investigate the complexity of the DEFENSIVE ALLIANCE problem
on graphs with bounded degree. We also study the fixed-parameter tractability
of the problem for the parameters distance to clique and twin cover. Our main
findings are as follows:

  1. 1.

We show that the DEFENSIVE ALLIANCE problem is polynomial-time solvable on
graphs with maximum degree at most 5.

  2. 2.

We prove that the DEFENSIVE ALLIANCE problem is NP-Complete on graphs with
maximum degree 6. We give a reduction from the well-known NP-Complete problem,
DOMINATING SET on cubic graphs.

  3. 3.

We also show that the DEFENSIVE ALLIANCE problem is FPT parameterized by
distance to clique.

  4. 4.

We provide an FPT algorithm for the DEFENSIVE ALLIANCE problem parameterized
by twin cover, which answers an open question posed in [9].

##  2 Preliminaries

Notation and terminology. We consider only simple, finite, connected and
undirected graphs. Let $G=(V,E)$ be a graph with $V$ as the vertex set and $E$
as the edge set such that $n=|V|$ and $m=|E|$. $\Delta(G)$ represents the
maximum degree of $G$. We denote the open neighbourhood of a vertex $v$ by
$N_{G}(v)$ and the closed neighbourhood by $N_{G}[v]$. The set of vertices
that belong to $N_{G}(v)$ and $N_{G}[v]$, respectively, are referred to as the
neighbours and closed neighbours of a vertex $v$. The open neighbourhood of a
set $S$ is denoted by $N_{G}(S)$ and the closed neighbourhood by $N_{G}[S]$.
$N_{G}(S)$ = $\bigcup\limits_{v\in S}N_{G}(v)$ and $N_{G}[S]$ =
$\bigcup\limits_{v\in S}N_{G}[v]$. The degree of a vertex $v$ is represented
by $d(v)$ and $d(v)=|N(v)|$. $dist(a,b)$ represents the shortest-path distance
between the vertices $a$ and $b$. $SP(a,b)$ represents the set of vertices in
the shortest path between $a$, $b$ including $a$, $b$. The girth of a graph
$G$, is the length of the shortest cycle in $G$ and is denoted by $g$. A graph
is $r$-regular if each vertex in the graph has a degree exactly $r$. A cubic
graph is a 3-regular graph.
Parameterized Complexity. A problem is considered to be fixed-parameter
tractable w.r.t. a parameter $k$, if there exists an algorithm with running
time $\mathcal{O}(f(k)\cdot n^{\mathcal{O}(1)})$, where $f$ is a computable
function. We use $\mathcal{O}^{*}(f(k))$ to denote the time complexity of the
form $\mathcal{O}(f(k)\cdot n^{\mathcal{O}(1)})$. Similarly, the term
W[1]-hard is used to express the hardness of a problem w.r.t. a parameter. In
parameterized complexity, the hierarchy of complexity classes is defined as
follows: FPT $\subseteq$ W[1] $\subseteq$ W[2] $\subseteq$ … $\subseteq$ XP.
In general, FPT $\neq$ W[1] under the Exponential Time Hypothesis [11]. Class
W[1] is the analog of NP in parameterized complexity. For more information on
graph theory and parameterized complexity, we refer the reader to [22] and
[3], respectively.

##  3 DEFENSIVE ALLIANCE on graphs with maximum degree at most 5

In this section, we show that the DEFENSIVE ALLIANCE problem is polynomial-
time solvable on graphs with maximum degree at most 5. For the rest of the
section, we assume that $\Delta(G)\leq 5$.
Theorem 1. The DEFENSIVE ALLIANCE problem on graphs with $\Delta(G)\leq 5$ is
polynomial-time solvable.
Lemma 1. A set containing only the vertices of a cycle in $G$, forms a
defensive alliance.
Proof. Let $S$ be a set containing only the vertices of a cycle. All the
vertices in $S$ will have three closed neighbours in $S$ and at most three
neighbours outside $S$. Therefore, all the vertices in $S$ are protected,
making it a defensive alliance. ∎

$v_{1}$$v_{2}$$v_{4}$$v_{3}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{1}$$v_{2}$$v_{4}$$v_{3}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$
Figure 1: Illustration of Observation 1, with an instance of the subproblem
$P_{4}$ on the left and an instance of the subproblem $P_{5}$ on the right.

Consider a graph $G=(V,E)$, where $|V|=n$ and $V=\\{v_{1},v_{2},...,v_{n}\\}$.
We solve $n$ independent subproblems: $P_{1},P_{2},...,P_{n}$, where $P_{i}$
denotes the problem of computing the smallest defensive alliance of $G$
containing the vertex $v_{i}$.
Observation 1: Consider the graph shown in Figure 1. The union of the vertices
of the path $v_{4}$, $v_{5}$ and the cycle $v_{5},v_{6}$ and $v_{7}$ forms a
defensive alliance for the subproblem $P_{4}$ which includes the vertex
$v_{4}$. However, the cycle $v_{5},v_{6}$ and $v_{7}$ forms a defensive
alliance of smaller cardinality in subproblem $P_{5}$.
From observation 1, it is clear that in order to compute the optimal solution
to the original problem, we can ignore a case where we consider the vertices
of a cycle and the path joining the cycle to obtain the defensive alliance for
subproblems. For the rest of this section, we compute the solutions to the
subproblems by avoiding such a scenario.
Observation 2: If $d(v_{i})\leq 1$, then $v_{i}$ itself forms a defensive
alliance. So, we consider only the subproblems in which $d(v_{i})\geq 2$.
Lemma 2. Let $d(v_{i})=3$ [or $2$], the size of the optimal solution for
$P_{i}$, will be minimum among the following:

  1. 1.

$\min_{x\in W}dist(v_{i},x)$+1, where $W=\\{u\in V(G)\setminus v_{i}|d(u)\leq
3\\}$.

  2. 2.

length of the shortest cycle containing $v_{i}$.

Proof. Let $u_{1},u_{2}$ and $u_{3}$ [or $u_{1}$ and $u_{2}$] are the
neighbours of $v_{i}$.
Case 1: Let us assume that exactly one neighbour of $v_{i}$ (say $u_{1}$) is
picked into the solution. As neither $u_{2}$ nor $u_{3}$ [or $u_{2}$] can be a
part of the solution, it is clear that the defensive alliance cannot be a set
of vertices from a cycle containing $v_{i}$. We cannot add any more vertices
that would form a cycle outside $v_{i}$, as explained earlier in Observation
1. Then the only way we could form a defensive alliance containing $v_{i}$ and
$u_{1}$ is to find the closest vertex (say $x$) from $v_{i}$, with $d(x)\leq
3$ and add all the vertices in the shortest path joining $u_{1}$ and $x$ to
the set. Except $x$ and $v_{i}$ all the other vertices of the path has at
least three closed neighbours in the set and both $x_{i}$ and $v_{i}$ with the
degree of at most three has at least two closed neighbours in the set. Hence,
the vertices of the path joining $x$ and $v_{i}$ forms a defensive alliance.
If no such $x$ exists, then $P_{i}$ cannot lead to an optimal solution.
Case 2: Let us assume that exactly two neighbours of $v_{i}$ (say $u_{1}$ and
$u_{2}$) are picked into the solution. The only way to form a defensive
alliance set containing the vertices $v_{i},u_{1}$ and $u_{2}$ is to find the
shortest cycle containing $v_{i},u_{1}$ and $u_{2}$ and add all the vertices
in the cycle to the set. If no such cycle exists, then $P_{i}$ cannot lead to
an optimal solution.
Case 3: Let us assume that all three neighbours of $v_{i}$ are picked into the
solution. If the defensive alliance forms a cycle containing the three
neighbours of $v_{i}$ then we can infer that there is a smaller cycle that
contains just the two neighbours of $v_{i}$. Hence, this case would lead to a
larger set than either case 1 or case 2.
We will have three [or two] combinations in case 1 and three [or one]
combinations in case 2. The minimum among them will return the optimal
solution for the subproblem $P_{i}$. ∎ Lemma 3. Let $d(v_{i})=5$ [or $4$], the
size of the optimal solution for $P_{i}$ will be the minimum among the
following:

  1. 1.

$\min_{x\neq y\in W}(dist(v_{i},x)+dist(v_{i},y)+1$), $W=\\{u\in V(G)\setminus
v_{i}|d(u)\leq 3\\},\\{SP(v_{i},x)\cap SP(v_{i},y)\\}\setminus
v_{i}=\emptyset$.

  2. 2.

length of the shortest cycle containing $v_{i}$.

Proof. Let $u_{1},u_{2},u_{3},u_{4}$ and $u_{5}$ [or $u_{1},u_{2},u_{3}$ and
$u_{4}$] are the neighbours of $v_{i}$.
Case 1: Let us assume that exactly one neighbour of $v_{i}$ (say $u_{1}$) is
picked into the solution. Then, it is easy to see that $v_{i}$ is not
protected. Therefore, no defensive alliance is possible by picking only one
neighbour of $v_{i}$ as part of the solution.
Case 2: Let us assume that exactly two neighbours of $v_{i}$ (say $u_{1}$ and
$u_{2}$) are picked into the solution. The defensive alliance containing the
vertices $v_{i},u_{1}$ and $u_{2}$ can be formed either with the vertices of
the shortest cycle containing $v_{i},u_{1}$ and $u_{2}$ or with the vertices
along the two vertex disjoint shortest paths from $u_{1}$ and $u_{2}$ to
vertices with degrees at most three. The minimum among the two sets forms a
defensive alliance.
Case 3: Let us assume that more than two neighbours of $v_{i}$ are picked into
the solution, then as explained in case 3 of Lemma 2, this forms a defensive
alliance with a larger cardinality than case 2.
We will have a total of twenty [or twelve] combinations in case 2. The minimum
among them will give the optimal solution for the subproblem $P_{i}$. ∎ Given
a vertex $v$,

  1. 1.

Computing the closest vertex to $v$ with degree at most three can be done in
$O(m+n)$ time.

  2. 2.

Using BFS, we can compute the shortest cycle containing $v$ in $O(m+n)$ time.

  3. 3.

Finding two vertex disjoint shortest paths to vertices with degree at most
three from $v$, is also solvable in $O(m+n)$ time.

Therefore, we can compute the optimal solution (if it exists) of the
subproblem $P_{i}$ in linear time. Hence, the DEFENSIVE ALLIANCE problem on
graphs with $\Delta(G)\leq 5$ is polynomial-time solvable. This concludes the
proof of Theorem 1.

##  4 DEFENSIVE ALLIANCE on graphs with maximum degree 6

In this section, we prove that the DEFENSIVE ALLIANCE problem is NP-Complete
on graphs with maximum degree 6.
Theorem 2. DEFENSIVE ALLIANCE on graphs with $\Delta(G)=6$ is NP-Complete.
It is easy to see that the problem is in NP. To prove the NP-Hardness, we
reduce from the following problem:
DOMINATING SET ON CUBIC GRAPHS:  Given a cubic graph $G=(V,E)$, a set
$S\subseteq V$ is a dominating set if every vertex $v\in V\setminus S$ has a
neighbour in $S$. Input: A simple, undirected cubic graph $G=(V,E)$, and a
positive integer $k$.
Question: Is there a dominating set $S\subseteq V$ such that $|S|\leq k$?
In 1980, Kikuno et al. [15] proved that the DOMINATING SET problem on cubic
graphs is NP-Complete.
Given an instance $I=(G,k)$ of the DOMINATING SET problem with $G$ being a
cubic graph, we construct an instance of $I^{\prime}=(G^{\prime},k^{\prime})$
of the DEFENSIVE ALLIANCE problem. We need a special type of vertices in
$G^{\prime}$ that cannot be a part of any defensive alliance of size at most
$k^{\prime}$, we call them the forbidden vertices. The forbidden vertices are
indicated using square-shaped nodes. We make use of the following gadget to
generate the forbidden vertices.
Gadget to generate the forbidden vertices:
Consider a 6-regular graph. Note that all the vertices have a closed
neighbourhood of seven. To protect a vertex of the defensive alliance from a
6-regular graph, it should have at least four closed neighbours in the set.
Therefore, the optimal defensive alliance can be obtained by finding the
minimum induced subgraph of minimum degree $\geq$ 3(from here on referred to
as MSMD(3)). As we do not want any vertex from the gadget to be a part of the
defensive alliance, we construct a 6-regular graph with no MSMD(3) of size at
most $k^{\prime}$. We make use of Ramanujan graphs to construct the gadget.
Definition 1. A Ramanujan graph is a $r$-regular graph whose non-trivial
eigenvalues lie in the interval $[-2\sqrt{r-1},2\sqrt{r-1}]$. For more
information on Ramanujan graphs, we refer the reader to [20, 19].
From [19], we have that $r$-regular Ramanujan graphs have girth,
$g\geq\frac{4}{3}\log_{r-1}|V|$.
Given the minimum degree $r$ and girth $g$, we have the following lower bound
on the graph size $|V(r,g)|$.
$|V(r,g)|\geq\frac{r(r-1)^{\frac{g-1}{2}}-2}{r-2}$ for odd $g$
$|V(r,g)|\geq\frac{2(r-1)^{\frac{g}{2}}-2}{r-2}$ for even $g$
Lemma 4. The size of the 6-regular Ramanujan graph that has an MSMD(3) of size
$k^{\prime}+1$ is polynomial in $k^{\prime}$.
Proof. Consider a 6-regular Ramanujan graph $R$. $R$ has girth at least
$\frac{4}{3}\log_{5}n$. Let $M$ be an MSMD(3) of $R$. As $M$ is an induced
subgraph of $R$, it also has a girth of at least $\frac{4}{3}\log_{5}n$. From
the lower bound on the size of the graph $|V(r,g)|$, we have that the size of
$M$ with girth at least $\frac{4}{3}\log_{5}n$ is
$\Omega(2^{\frac{\frac{4}{3}\log_{5}n}{2}})$ which is
$\Omega(n^{\frac{2}{3}\log_{5}2})$. The bound can be represented as
$\Omega(n^{c})$ where $c=0.2871$.

$k^{\prime}+1\geq c_{1}\cdot 2^{\frac{\frac{4}{3}\log_{5}n}{2}}$ $\implies$
$k^{\prime}+1\geq c_{1}\cdot n^{\frac{2}{3}\log_{5}2}$ $\implies$
$k^{\prime}+1\geq c_{1}\cdot n^{0.2871}$

$\implies$ $n\leq(\frac{k^{\prime}+1}{c})^{3.484}$.

The size of $R$ with $M$ of size $k^{\prime}+1$ is
$\mathcal{O}((k^{\prime}+1)^{3.484})$. This proves that the order of the
6-regular Ramanujan graph with MSMD(3) of size at least $k^{\prime}+1$ is a
polynomial function of $k^{\prime}$. ∎Lemma 5. There is no defensive alliance
of size at most $k^{\prime}$ from the 6-regular Ramanujan graph of size
polynomial in $k^{\prime}$.
Proof. Let $R$ be the 6-regular Ramanujan graph. Each vertex of $R$ has a
degree of six with a closed neighbourhood of seven. To obtain the optimal
defensive alliance from $R$, we compute an induced subgraph with each vertex
having a closed neighbourhood of four, hence the MSMD(3). We know that the
size of MSMD(3) is at least $k^{\prime}+1$. This concludes that there is no
defensive alliance of size at most $k^{\prime}$ from $R$. ∎Note: The
construction of Ramanujan graphs by Lubotzky et al. can be done in polynomial
time[19]. One can construct $r+1$-regular Ramanujan graph using this method
when $r$ is a prime and $r\equiv 1\pmod{4}$. Therefore, the 6-regular
Ramanujan graph can be constructed in polynomial time.
Let us consider a 6-regular Ramanujan graph with one missing edge with the
same girth as that of a 6-regular Ramanujan graph. We can obtain the graph by
removing an edge which is not part of a shortest cycle. In a 6-regular
Ramanujan graph with one missing edge, the vertices of MSMD(3) with at most
one missing edge can also form a defensive alliance. So, we look to find an
MSMD(3) with at most one missing edge. The size of MSMD(3) with at most one
missing edge of girth $g$, is at least the size of MSMD(3) of girth $g$.
Therefore, Lemma 4 and Lemma 5 also hold for 6-regular Ramanujan graph with
one missing edge. Hence, we obtain the following lemma.
Lemma 6. There is no defensive alliance of size at most $k^{\prime}$ from the
6-regular Ramanujan graph with one missing edge of size polynomial in
$k^{\prime}$.
We use the 6-regular Ramanujan graph with one missing edge as the gadget. The
vertices corresponding to the missing edge will be used in place of the
forbidden vertices. From Lemma 6, we conclude that there is no defensive
alliance of size at most $k^{\prime}$ from the gadget.
Reduction from the DOMINATING SET ON CUBIC GRAPHS:
We construct an instance $I^{\prime}=(G^{\prime},k^{\prime})$ of the DEFENSIVE
ALLIANCE problem in the following way. See Figure 2 for an illustration.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$G$

$G^{\prime}$$v_{1}^{0}$$v_{1}^{1}$$u_{1}^{1}$$w_{1}^{1}$$u_{1}^{2}$$w_{1}^{2}$$u_{1}^{3}$$w_{1}^{3}$$v_{1}^{2}$$v_{1}^{3}$$v_{2}^{0}$$v_{2}^{1}$$u_{2}^{1}$$w_{2}^{1}$$u_{2}^{2}$$w_{2}^{2}$$u_{2}^{3}$$w_{2}^{3}$$v_{2}^{2}$$v_{2}^{3}$$v_{3}^{0}$$v_{3}^{1}$$u_{3}^{1}$$w_{3}^{1}$$u_{3}^{2}$$w_{3}^{2}$$u_{3}^{3}$$w_{3}^{3}$$v_{3}^{2}$$v_{3}^{3}$$v_{4}^{0}$$v_{4}^{1}$$u_{4}^{1}$$w_{4}^{1}$$u_{4}^{2}$$w_{4}^{2}$$u_{4}^{3}$$w_{4}^{3}$$v_{4}^{2}$$v_{4}^{3}$$v_{5}^{0}$$v_{5}^{1}$$u_{5}^{1}$$w_{5}^{1}$$u_{5}^{2}$$w_{5}^{2}$$u_{5}^{3}$$w_{5}^{3}$$v_{5}^{2}$$v_{5}^{3}$$v_{6}^{0}$$v_{6}^{1}$$u_{6}^{1}$$w_{6}^{1}$$u_{6}^{2}$$w_{6}^{2}$$u_{6}^{3}$$w_{6}^{3}$$v_{6}^{2}$$v_{6}^{3}$$u_{1}^{0}$$w_{1}^{0}$$u_{2}^{0}$$w_{2}^{0}$$u_{3}^{0}$$w_{3}^{0}$$u_{4}^{0}$$w_{4}^{0}$$u_{5}^{0}$$w_{5}^{0}$$u_{6}^{0}$$w_{6}^{0}$$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{5}$$s_{6}$

Figure 2: A 6-vertex cubic graph $G$ and its corresponding $G^{\prime}$

  1. 1.

For every vertex $v_{i}\in V$ in $G$, we introduce four copies in
$G^{\prime}$, which are represented by
$v_{i}^{0},v_{i}^{1},v_{i}^{2},v_{i}^{3}$.

  2. 2.

For every vertex $v_{i}^{j}\in G^{\prime},1\leq i\leq n,0\leq j\leq 3$, we
introduce two vertices $u_{i}^{j},w_{i}^{j}$. We make all the three vertices
$v_{i}^{j},u_{i}^{j}$ and $w_{i}^{j}$ adjacent to each other.

  3. 3.

We make each $v_{i}^{0}$ adjacent to $u_{i}^{1}$, each $w_{i}^{1}$ adjacent to
$u_{i}^{2}$ and each $w_{i}^{2}$ adjacent to $u_{i}^{3}$. Additionally, we
also make $w_{i}^{0}$ adjacent to $u_{i+1}^{0}$ for each
$i\in\\{1,...,n-1\\}$.

  4. 4.

For every vertex $v_{i}^{0}$, we introduce a vertex $s_{i}$, and make it
adjacent to $v_{i}^{0}$. We make $s_{i}$ also adjacent to $v_{k}^{j}$ for all
$k\in N_{G}(v_{i})$, with the smallest possible value of $j\in\\{1,2,3\\}$
such that $v_{k}^{j}$ has no other $s_{k}$ adjacent to it. For example,
$v_{1}$ is adjacent to $v_{2},v_{3}$ and $v_{6}$ in $G$, so we make $s_{1}$
adjacent to $v_{2}^{1}$, $v_{3}^{1}$ and $v_{6}^{1}$ in $G^{\prime}$ as all
three of them do not have any other $s_{k}$ adjacent to them at this point.
Similarly, $v_{2}$ is adjacent to $v_{1},v_{3}$ and $v_{4}$ in $G$, we make
$s_{2}$ adjacent to $v_{1}^{1},v_{3}^{2}$ and $v_{4}^{1}$. Here $v_{3}^{1}$ is
adjacent to $s_{1}$, hence we go for $v_{3}^{2}$. We add these edges
lexicographically, starting from $s_{1}$.

From hereon, we add the forbidden vertices that are constructed using the
gadget.

  1. 5.

We make every vertex of $v_{i}^{j},1\leq i\leq n,0\leq j\leq 3$, adjacent to
two forbidden vertices.

  2. 6.

We make every vertex of $\\{u_{i}^{j}\cup w_{i}^{j}\\},1\leq i\leq n,0\leq
j\leq 3$, adjacent to three forbidden vertices.

The vertices corresponding to the missing edge in a 6-regular Ramanujan graph
can be used as the forbidden vertices. We use multiple gadgets to represent
all the forbidden vertices in the reduction.
Lemma 7. If $G$ has a dominating set of size at most $k$ then $G^{\prime}$ has
a defensive alliance of size at most $k^{\prime}$, where $k^{\prime}=4n+8k$.
Proof. Let the set $S$ be a dominating set of size at most $k$ then we claim
that the set $S^{\prime}=X\cup Y\cup Z$ is a defensive alliance of
$G^{\prime}$ of size at most $k^{\prime}$, where
$X=\bigcup\limits_{i=1}^{n}$ $\\{u_{i}^{0}\cup v_{i}^{0}\cup w_{i}^{0}\\}$
$Y=\bigcup\limits_{i|v_{i}\in S}\bigcup\limits_{j\in\\{1,2,3\\}}$
$\\{u_{i}^{j}\cup v_{i}^{j}\cup w_{i}^{j}\\}$
$Z=\bigcup\limits_{i|v_{i}\notin S}s_{i}$
For $S^{\prime}$ to be a defensive alliance, every vertex from the sets $X,Y$
and $Z$ should be protected.
Set $X$:

  * •

Consider a vertex $v\in\\{v_{i}^{0},1\leq i\leq n\\}$. $v$ has seven vertices
in its closed neighbourhood including the two forbidden vertices. $v$ has
three of its neighbours, $u_{i}^{0},w_{i}^{0}$ and one among $u_{i}^{1}$ or
$s_{i}$ in $S^{\prime}$. Including itself, $v$ has four closed neighbours in
$S^{\prime}$, which makes $v$ protected.

  * •

Similarly, it can be seen that a vertex $v\in\\{u_{i}^{0}\cup w_{i}^{0},1\leq
i\leq n\\}$ has the majority of its neighbours in $S^{\prime}$. Hence, $v$ is
protected.

Set $Y$:

  * •

Consider a vertex $v\in\\{u_{i}^{j}\cup w_{i}^{j},i|v_{i}\in S,1\leq j\leq
3\\}$. $v$ is adjacent to three forbidden vertices. As all the other
neighbours of $v$ are in $S^{\prime}$, it is easy to verify that $v$ is
protected.

  * •

A vertex $v\in\\{v_{i}^{j},i|v_{i}\in S,1\leq j\leq 3\\}$ has six vertices in
its closed neighbourhood which includes two forbidden vertices. As the two
neighbours of $v$, $u_{i}^{j}$ and $w_{i}^{j}$ are in $S^{\prime}$, $v$ is
protected.

Set $Z$:
Consider a vertex $v\in\\{s_{i},i|v_{i}\notin S\\}$. $v$ has a total of five
vertices in its closed neighbourhood. $v$ has two of its neighbours,
$v_{i}^{0}$ and one of its other three neighbours in $S^{\prime}$. Including
itself, $v$ has three closed neighbours in $S^{\prime}$ . Hence, $v$ is
protected.
As all the vertices of the sets $X,Y$ and $Z$ are protected. As
$|X|=3n,|Y|=9k,|Z|=n-k$ and $|X|+|Y|+|Z|=4n+8k=k^{\prime}$. Therefore,
$S^{\prime}$ is a defensive alliance of size at most $k^{\prime}$. This
concludes the proof of Lemma 7. ∎

Lemma 8. If $G^{\prime}$ has a defensive alliance of size at most $k^{\prime}$
then $G$ has a dominating set of size at most $k$.
Proof. Let $S^{\prime}$ be a defensive alliance in $G^{\prime}$ of size at
most $k^{\prime}$. We define the sets $X,Y_{i}$ and $Z_{i}$ as follows.
$X=\bigcup\limits_{i=1}^{n}$ $\\{u_{i}^{0}\cup v_{i}^{0}\cup w_{i}^{0}\\}$
$Y_{i}=\bigcup\limits_{j\in\\{1,2,3\\}}$ $\\{u_{i}^{j}\cup v_{i}^{j}\cup
w_{i}^{j}\\},$ for $1\leq i\leq n$
$Z_{i}=s_{i},$ for $1\leq i\leq n$

  1. 1.

If $v\in X$ is a part of the defensive alliance $S^{\prime}$, then $X\subseteq
S^{\prime}$.

Picking any vertex from $\\{u_{i}^{0},w_{i}^{0}\\},1\leq i\leq n$ would lead
to $X\subseteq S^{\prime}$.

Let $v\in v_{i}^{0},1\leq i\leq n$ be a vertex in $S^{\prime}$. In the
neighbourhood of $v$, even after picking both the vertices from $Y_{i},Z_{i}$
to be a part of $S^{\prime}$, there is still a deficiency of one that needs to
be filled by one among $u_{i}^{0},w_{i}^{0}$. This creates a chain reaction
that pushes all of $X$ to $S^{\prime}$.

  2. 2.

If $v\in\\{Y_{i}\cup Z_{i}\\}$ is a part of the defensive alliance
$S^{\prime}$, then $X\subseteq S^{\prime}$.

Let $v\in Y_{i}$ is in $S^{\prime}$. For $v$ to be protected, all the
neighbours of $v$ (excluding the forbidden vertices) must be in $S^{\prime}$.
This triggers a chain reaction that pushes all of $Y_{i}$ and also $v_{i}^{0}$
to $S^{\prime}$. As $v_{i}^{0}$ is in $S^{\prime}$, $X\subseteq S^{\prime}$.

Let $v\in Z_{i}$ is a part of $S^{\prime}$. For $v$ to be protected, one of
its neighbours from $Y_{k}$, $k\in N_{G}[v]$ must be in $S$. This would again
lead to all of $Y_{k}$ and $v_{k}^{0}$ being in $S^{\prime}$ and hence
$X\subseteq S^{\prime}$.

  3. 3.

It is clear that if $S^{\prime}$ is non-empty then $X$ must be a part of
$S^{\prime}$. Here, we have consumed $3n$ vertices of $k^{\prime}$ and are
left with $n+8k$ vertices that can still go into $S^{\prime}$.

  4. 4.

Note that by now, vertex $v\in\\{u_{i}^{0}\cup w_{i}^{0}\\},1\leq i\leq n$ is
covered. Each vertex $v\in v_{i}^{0},1\leq i\leq n$ needs one more neighbour
either from $Y_{i}$ (or) $Z_{i}$ to be included in $S^{\prime}$ for it to be
protected.

If we choose to include the vertex $u_{i}^{1}$ from $Y_{i}$, then this would
trigger a chain reaction that pushes $Y_{i}$ to $S^{\prime}$.

If we choose to pick the neighbour $s_{i}$ from $Z_{i}$ then this would lead
to pushing only one vertex to $S^{\prime}$ before encountering a copy of
$v_{j}$, which also needs to be a part of $S^{\prime}$.

  5. 5.

We can’t pick neighbours to all $v_{i}^{0}$’s from $Y_{i}$ as this will force
us to go beyond the remaining capacity of $k^{\prime}$. Based on the remaining
threshold of $k^{\prime}$, which is $n+8k$, it is clear that we pick
neighbours from $Y_{i}$ to be a part of $S^{\prime}$ for $k$ number of
$v_{i}^{0}$’s and from $Z_{i}$ for $n-k$ number of $v_{i}^{0}$’s.

  6. 6.

Consider a vertex $v_{i}^{0}$ for which we pick the neighbour from $s_{i}$, we
finally encounter a copy of $v_{k}$ which is an adjacent vertex of $v_{i}$ in
$G$ and it needs to be a part of $S^{\prime}$ for $v_{i}^{0}$ to be protected.
This also indicates that if $v_{i}\notin S$ in $G$, then one of its neighbours
$v_{k}$ must be in $S$. Basically, if $s_{i}\notin S^{\prime}$ then the
corresponding $v_{i}(G)\in S$ and $S$ forms a dominating set.

Therefore, it can be inferred that the vertices part of $S$ must form a
dominating set of size at most $k$. This concludes the proof of Lemma 8. ∎ In
Figure 2, let $\\{v_{2},v_{5}\\}$ be a dominating set of $G$ of size 2, then
the corresponding defensive alliance in $G^{\prime}$ is
$\bigcup\limits_{i=1}^{6}$ $\\{u_{i}^{0}\cup v_{i}^{0}\cup w_{i}^{0}\\}$
$\cup\bigcup\limits_{i\in\\{2,5\\}}\bigcup\limits_{j\in\\{1,2,3\\}}$
$\\{u_{i}^{j}\cup v_{i}^{j}\cup w_{i}^{j}\\}$ $\cup$
$\bigcup\limits_{i\in\\{1,3,4,6\\}}s_{i}$ of size 40.
We have a 6-regular Ramanujan graph with one missing edge of size polynomial
in $k^{\prime}$. By using the vertices of the missing edge in place of the
forbidden vertices, the closed neighbourhood grows to seven. Even if the new
adjacent vertex from $I^{\prime}$ is in the defensive alliance, we still
compute MSMD(3) with one missing edge from the gadget, whose cardinality will
be at least $k^{\prime}+1$.
$G^{\prime}$ has a maximum degree of six. Hence, the DEFENSIVE ALLIANCE is NP-
Complete on $\Delta(G)=6$ graphs. This concludes the Proof of Theorem 2.
Theorem 3. The DEFENSIVE ALLIANCE problem is para-NP-hard for the parameter
maximum degree ($\Delta$).
Proof. From Theorem 2, we have that the DEFENSIVE ALLIANCE problem is NP-
Complete on $\Delta(G)=6$ graphs. As the problem is NP-complete for a constant
value of the parameter, it implies that the DEFENSIVE ALLIANCE problem is
para-NP-hard for the parameter maximum degree ($\Delta$).

##  5 DEFENSIVE ALLIANCE parameterized by distance to clique

In this section, we show that the DEFENSIVE ALLIANCE problem is FPT
parameterized by distance to clique. We reduce the given problem to the
integer linear programming problem (ILP), which is known to be FPT when
parameterized by the number of variables.
Definition 2. For a graph $G=(V,E)$, the parameter distance to clique is the
cardinality of the smallest set $D\subseteq V$ such that $V\setminus D$ is a
clique.
We can use a simple branching algorithm to compute set $D$ of size at most $k$
in $\mathcal{O}^{*}(2^{k})$ time, if such a set exists.
ILP formulation
Integer Linear Programming is a framework used to formulate a given problem
using a finite number of variables. The problem definition is given as
follows:
Problem. $p$-Opt-ILP Instance: A matrix $A\in\mathbb{Z}^{m*p}$, and vectors
$b\in\mathbb{Z}^{m}$ and $c\in\mathbb{Z}^{p}$.
Objective: Find a vector $x\in\mathbb{Z}^{p}$ that minimizes $c^{\top}x$ and
satisfies that $Ax\geq b$.
Parameter: $p$, the number of variables.
Lenstra [18] showed that deciding the feasibility of a $p$-ILP is fixed-
parameter tractable with running time doubly exponential in $p$, where $p$ is
the number of variables. Later, Kannan [14] gave a $p^{p}$ algorithm for
$p$-ILP. Fellows et al. [5] proved that $p$-Opt-ILP, the optimization version
of the problem, is also fixed-parameter tractable.
Theorem 4. [5] The optimization version of $p$-variable INTEGER LINEAR
PROGRAMMING can be solved using $\mathcal{O}(p^{2.5p+o(p)}\cdot L\cdot
log(MN))$ arithmetic operations and space polynomial in $L$, where $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.
Theorem 5. Given a graph $G=(V,E)$ and $D\subseteq V$ such that $V\setminus D$
is a clique, the DEFENSIVE ALLIANCE problem can be solved in
$\mathcal{O}^{*}(f(|D|))$ time.
Consider a graph $G=(V,E)$ and $D\subseteq V$ such that $|D|$ is the distance
to clique of $G$ and $C=V\setminus D$. We partition the vertices of $C$ into
$t$ twin classes, which are represented by $C_{1},C_{2},...,C_{t}$ ($t\leq
2^{|D|})$, such that all the vertices in a twin class $C_{i}$ have same
adjacency in $D$. Let $S\subseteq V$ be a defensive alliance of $G$. We guess
the vertex sets $P=S\cap D$ and compute $S_{C}=S\cap C$. We also guess a
subset of twin classes $C_{N}\subseteq C$ from which no vertices are picked in
the solution. See Figure 3 for an illustration. After the guess of $P$ and
$C_{N}$, we compute $S_{C}$ using integer linear programming. For each of
$u\in D$, we define $demand(u)$ = $\lceil\frac{1}{2}(d(u)+1)\rceil-|N[u]\cap
P|$. For each $u\in D$, we denote by $M(u)$ the set of indices $i$ such that
$C_{i}\subseteq N(u)$. In other words, $M(u)$ represents the indices of the
twin classes from $C$ that $u$ is adjacent to. Let $x_{i}$ represent the
number of vertices in $C_{i}\cap S$. In our ILP formulation, there are $t$
variables that are $x_{1},x_{2},...,x_{t}$.

$D$$P$$C$$C_{1}$$C_{j}$$C_{k}$$C_{N}$ Figure 3: Partitioning of the vertex set
$V$ into sets $D$ and $C$, where $|D|$ is the distance to clique and $C$ is a
clique.

Lemma 9. The set $S$ is a defensive alliance if and only if

  1. 1.

For $\forall C_{i}\in C_{N}$, $x_{i}$ = 0.

  2. 2.

For each $u\in P$, $\sum_{i\in M(u)}x_{i}\geq$ $demand(u)$.

  3. 3.

Each $v\in C\setminus C_{N}$ has to satisfy $|N(v)\cap
P|+\sum_{i\in\\{1,2,...,t\\}}x_{i}\geq|N[v]\setminus
P|-\sum_{i\in\\{1,2,...,t\\}}x_{i}-1.$

Proof.

  1. 1.

As $C_{N}$ represents the set of twin classes with no vertices in $S$, we have
$x_{i}$ = 0 for all $C_{i}\in C_{N}$.

  2. 2.

For each $u\in P$, $d(u)$ = $|N(u)\cap S|+|N(u)\setminus S|$ and $|N(u)\cap
S|\geq|N(u)\setminus S|-1$ holds if and only if $2*|N(u)\cap S|\geq d(u)-1$,
which is equivalent to $|N(u)\cap S_{C}|\geq demand(u)$ implies $\sum_{i\in
M(u)}x_{i}\geq$ $demand(u)$.

  3. 3.

For each $v\in C\setminus C_{N}$, $|N(v)\cap S|$ = $|N(v)\cap P|+|S_{C}|$,
which is indeed $|N(v)\cap P|+\sum_{i\in\\{1,2,...,t\\}}x_{i}$;
$|N(v)\setminus S|-1$ = $|(N(v)\cap D)\setminus
P|+|C|-\sum_{i\in\\{1,2,...,t\\}}x_{i}-1$, which equals $|N[v]\setminus
P|-\sum_{i\in\\{1,2,...,t\\}}x_{i}-1.$ ∎

The ILP formulation for the defensive alliance is given as
Minimize $\sum_{i\in\\{1,2,...,t\\}}x_{i}$ Subject to • $x_{i}=0$, for
$\forall C_{i}\in C_{N}$. • $\sum_{i\in M(u)}x_{i}\geq$ $demand(u)$, for each
$u\in P.$ • $|N(v)\cap P|+\sum_{i\in\\{1,2,...,t\\}}x_{i}\geq|N[v]\setminus
P|-\sum_{i\in\\{1,2,...,t\\}}x_{i}-1,$ for every $v\in C\setminus C_{N}.$ •
$x_{i}\leq|C_{i}|$, for each $i\in\\{1,2,...,t\\}.$
The ILP will output the optimal values of $x_{i}$ for all
$i\in\\{1,2,...,t\\}$. If $x_{i}>0$, we need to pick $x_{i}$ vertices from
$C_{i}$. As all the vertices in $C_{i}$ have the same neighbourhood, we can
pick any $x_{i}$ vertices. Hence, we obtain the vertex set $S_{C}$.
In our ILP formulation, we have at most $2^{|D|}$ variables. The values of all
the variables and the objective function are bounded by $n$. The constraints
can be represented using $\mathcal{O}(4^{|D|}\cdot logn)$ bits. With the help
of Theorem 4, we will be able to solve the problem with the guess
($P,\;C_{N}$) in FPT time. There are $2^{|D|}$ candidates for $P$ and
$2^{2^{|D|}}$ candidates for $C_{N}$. To obtain $S_{C}$, we solve $8^{|D|}$
ILP formulas where each formula can be computed in $\mathcal{O}^{*}(f(|D|))$
time. This concludes the proof of Theorem 5.

##  6 DEFENSIVE ALLIANCE parameterized by twin cover

In this section, we show that the DEFENSIVE ALLIANCE problem is FPT
parameterized by twin cover. We give an ILP formulation for the combined
parameter twin cover, the size of the largest clique outside the twin cover.
Using this, we show that the DEFENSIVE ALLIANCE problem is FPT for the
parameter twin cover.
Definition 3. For a graph $G=(V,E)$, the parameter twin cover is the
cardinality of the smallest set $T\subseteq V$ such that $V\setminus T$ is a
disjoint union of cliques wherein all the vertices in each clique have the
same adjacency in the twin cover.
Theorem 6. [10] If a minimum twin cover in $G$ has size at most $k$, then it
is possible to compute a twin cover of size at most $k$ in time
$\mathcal{O}(|E||V|+k|V|+1.2738^{k})$.
Theorem 7. Given a graph $G=(V,E)$, $T\subseteq V$ is a twin cover of $G$ and
$z$ is the size of the largest clique outside the twin cover, the DEFENSIVE
ALLIANCE problem can be solved in $\mathcal{O}^{*}(f(|T|,z))$ time.

$P$$T$$C_{1}$$C_{1}^{1}$$C_{1}^{2,F}$$C_{1}^{2,N}$

$C_{1}^{2,P_{1}}$

$C_{1}^{2,P_{2}}$

$C_{1}^{2,P_{3}}$

$C_{1}^{2,P_{y_{1}^{2}}}$

$C_{1}^{z}$$C_{2}$$C_{2}^{1}$$C_{2}^{2,F}$$C_{2}^{2,N}$

$C_{2}^{2,P_{1}}$

$C_{2}^{2,P_{2}}$

$C_{2}^{2,P_{3}}$

$C_{2}^{2,P_{y_{2}^{2}}}$

$C_{2}^{z}$$C_{t}$$C_{t}^{1}$$C_{t}^{2,F}$$C_{t}^{2,N}$

$C_{t}^{2,P_{1}}$

$C_{t}^{2,P_{2}}$

$C_{t}^{2,P_{3}}$

$C_{t}^{2,P_{y_{t}^{2}}}$

$C_{t}^{z}$$C$ Figure 4: Partitioning of the vertex set $V$ into sets $T$ and
$C$, where $T$ is the twin cover and $C$ is the union of clique sets outside
$T$. The figure also highlights the cliques of type full, partial and null of
length two in each clique set. The blue vertices belong in the alliance set.

Consider a graph $G=(V,E)$. Let $T\subseteq V$ be a twin cover of $G$ and
$C=V\setminus T$. We partition the vertices of $C$ into $t$ clique sets which
are represented by $C_{1},C_{2},...,C_{t}$ ($t\leq 2^{|T|})$, such that all
the vertices in a clique set $C_{i}$ have same adjacency in $T$. Let
$S\subseteq V$ be a defensive alliance of $G$. We guess the vertex set
$P=S\cap T$ and compute $S_{C}=S\cap C$. For each of $u\in P$, we define
$demand(u)$ = $\lceil\frac{1}{2}(d(u)+1)\rceil-|N[u]\cap P|$. For each $u\in
P$, we denote by $M(u)$ the set of indices $i$ such that $C_{i}\subseteq
N(u)$. In other words, $M(u)$ represents the indices of the clique sets from
$C$ that $u$ is adjacent to. We have at most $z$ different size cliques in
each clique set whose sizes range from 1 to $z$. We represent the cliques of
size $l$ in the clique set $C_{i}$ as $C_{i}^{l}$.
We place cliques of all sizes from each clique set into one of the following
three types: full, partial and null. full clique has all of its vertices
picked in the solution, partial clique has some of its vertices picked,
whereas a null clique has no vertices picked. $C_{i}^{l,F}$ represents the
union of all full cliques in $C_{i}^{l}$. $C_{i}^{l,P},C_{i}^{l,N}$ represent
the union of all partial cliques and union of all null cliques in $C_{i}^{l}$
respectively. We denote each partial clique in $C_{i}^{l,P}$ by
$C_{i}^{l,P_{j}}$, where $j$ denotes the index of a partial clique. See Figure
4 for an illustration of full, partial and null cliques of length two. Let
$x_{i}^{l,P_{j}}$ represent the number of vertices in $C_{i}^{l,P_{j}}\cap S$.
In the ILP formulation, we need an individual variable for every partial
clique in $C_{i}^{l,P}$. Here, the idea is to limit the number of partial
cliques in each clique set $C_{i}$, which results in formulating the ILP using
the desired number of variables.
Lemma 10. Consider a set $C_{i}^{l}$ from a clique set $C_{i}$, there exists
an optimal solution with at most $l-1$ partial cliques from $C_{i}^{l}$.
Proof. Consider an optimal solution $S$ with $p$ partial cliques from
$C_{i}^{l}$. We construct another optimal solution $S^{\prime}$ from $S$ with
at most $l-1$ partial cliques as follows. We arrange the partial cliques in
$S$ in ascending order based on their number of vertices in $S$. Let the order
be $C_{i}^{l,P_{1}},C_{i}^{l,P_{2}},...,C_{i}^{l,P_{p}}$. We perform the
following operation repeatedly to obtain $S^{\prime}$. In any iteration, let
the first clique in the list be $C^{*}$. We replace each vertex of $C^{*}$
that is in $S$ with a vertex that is not in $S$ in each of the last $|C^{*}|$
cliques in the list. We push $C^{*}$ to null clique set. If there are any
other cliques that become full by the recent addition of vertices, then we
simply move them into full cliques set. We perform this until we can place all
the vertices of $C^{*}$ into the cliques of larger sizes. It is easy to see
that all the vertices in the resultant instance are protected as the number of
vertices from any clique that belongs to the solution only grows. There is no
change in the number of vertices that go into the solution, therefore
$S^{\prime}$ is also optimal. The maximum number of partial cliques that would
remain when this process comes to a halt is $l$-1 partial cliques with $l-1$
vertices in $S$ from each clique. Hence, we conclude that there exists an
optimal solution with at most $l-1$ partial cliques.∎ Let $y_{i}^{l}$ be the
number of partial cliques in $C_{i}^{l}$. From Lemma 10, it is clear that
there is an optimal solution with at most $l-1$ partial cliques from
$C_{i}^{l}$ and we have $y_{i}^{l}\leq l-1$. We guess the cliques from
$C_{i}^{l}$ that go into $C_{i}^{l,P}$ in $y_{i}^{l}+1$ ways and from the
remaining $|C_{i}-C_{i}^{l,P}|$ cliques, $C_{i}^{l,F}$ can be guessed in
$m-y_{i}^{l}+1$ ways, where $m$ is the number of cliques in $C_{i}^{l}$. As we
have guessed $P,C_{i}^{l,F}$ and $C_{i}^{l,P}$, we compute $S_{C}$ using
integer linear programming. $x_{i}^{l,P}$ represents the sum of
$x_{i}^{l,P_{1}},x_{i}^{l,P_{2}},...,x_{i}^{l,P_{y_{i}^{l}}}$. In our ILP
formulation, there are at most $\sum_{i=1}^{t}\sum_{l=1}^{z}y_{i}^{l}$
variables that are
$x_{1}^{1,P_{1}},...,x_{1}^{z,P_{y_{1}^{z}}},x_{2}^{1,P_{1}},...,x_{2}^{z,P_{y_{2}^{z}}},...,x_{t}^{z,P_{y_{t}^{z}}}$.
Lemma 11. The set $S$ is a DEFENSIVE ALLIANCE if and only if

  1. 1.

For each $u\in P$, $\sum_{i\in M(u)}$ $\sum_{l=1}^{l=z}|C_{i}^{l,F}|$ \+
$\sum_{i\in M(u)}$ $\sum_{l=1}^{l=z}$
$\sum_{j=1}^{j=y_{i}^{l}}x_{i}^{l,P_{j}}$ $\geq$ $demand(u)$.

  2. 2.

Each $v\in C_{i}^{l,P_{j}}$ has to satisfy $|N(v)\cap
P|+x_{i}^{l,P_{j}}\geq|N[v]\setminus P|-x_{i}^{l,P_{j}}-1.$

Proof.

  1. 1.

For each $u\in P$, $d(u)$ = $|N(u)\cap S|+|N(u)\setminus S|$ and $N(u\cap
S_{C})=$ $\sum_{i\in M(u)}$ $\sum_{l=1}^{l=z}|C_{i}^{l,F}|+$ $\sum_{i\in
M(u)}\sum_{l=1}^{l=z}$ $\sum_{j=1}^{j=y_{i}^{l}}x_{i}^{l,P_{j}}$. $|N(u)\cap
S|\geq|N(u)\setminus S|-1$ holds if and only if $2*|N(u)\cap S|\geq$ $d(u)-1$,
which implies $\sum_{i\in M(u)}\sum_{l=1}^{l=z}|C_{i}^{l,F}|$ \+ $\sum_{i\in
M(u)}\sum_{l=1}^{l=z}\sum_{j=1}^{j=y_{i}^{l}}x_{i}^{l,P_{j}}$ $\geq$
$demand(u)$.

  2. 2.

For each $v\in C_{i}^{l,P_{j}}$, $|N(v)\cap S|$ = $|N(v)\cap
P|+x_{i}^{l,P_{j}}$; $|N(v)\setminus S|-1$ = $|N[v]\setminus
P|-x_{i}^{l,P_{j}}-1.$ ∎

The ILP formulation for the DEFENSIVE ALLIANCE is given as
Minimize
$\sum_{i=1}^{i=t}\sum_{l=1}^{l=z}\sum_{j=1}^{j=y_{i}^{l}}x_{i}^{l,P_{j}}$
Subject to • $\sum_{i\in M(u)}\sum_{l=1}^{l=z}|C_{i}^{l,F}|+\sum_{i\in
M(u)}\sum_{l=1}^{l=z}\sum_{j=1}^{j=y_{i}^{l}}x_{i}^{l,P_{j}}\geq$ $demand(u)$,
for each $u\in P.$ • $|N(v)\cap P|+x_{i}^{l,P_{j}}\geq|N[v]\setminus
P|-x_{i}^{l,P_{j}}-1$, for every $v\in C_{i}^{l,P_{j}}$. •
$x_{i}^{l,P_{j}}<l$, for each $i\in\\{1,2,...,t\\}$, $l\in\\{1,2,...,z\\}$ and
$j\in\\{1,2,...,y_{i}^{l}\\}$.
In our ILP formulation, we have at most
$\sum_{i=1}^{t}\sum_{l=1}^{z}y_{i}^{l}$ variables, where $z$ is the size of
the largest clique outside the twin cover and $y_{i}^{l}\leq l-1$. The values
of all the variables and the objective function are bounded by $n$. The
constraints can be represented using
$\mathcal{O}(\sum_{i=1}^{t}\sum_{l=1}^{z}y_{i}^{l}\cdot|T|\cdot logn)$ bits.
With the help of Theorem 4, we will be able to solve the problem with the
guess $(P,C_{i}^{l,F}$ and $C_{i}^{l,P})$ in FPT time. There are $2^{|T|}$
candidates for $P$ and there are
$\sum_{i=1}^{t}\sum_{l=1}^{z}y_{i}^{l}\cdot\mathcal{O}(n)$ candidates for
$(C_{i}^{l,F}$ and $C_{i}^{l,P})$. To obtain $S_{C}$, we solve
$2^{|T|}\cdot\sum_{i=1}^{t}\sum_{l=1}^{z}y_{i}^{l}\cdot\mathcal{O}(n)$ ILP
formulas, where each formula can be computed in $\mathcal{O}^{*}(f(|TC|,z))$
time. This concludes the proof of Theorem 7.
Theorem 8. The DEFENSIVE ALLIANCE problem is fixed-parameter tractable
parameterized by twin cover.
Lemma 12. If there exists a clique $C^{*}\in C_{i}$ of size at least
$|N(C_{i})\cap T|$ then there exist a defensive alliance $S\subseteq C^{*}$.
Proof. Consider a clique set $C_{i}$ outside the twin cover. Let $C^{*}$ be
the clique from $C_{i}$ of size at least $|N(C_{i})\cap T|$. Let $v$ be the
vertex from $C^{*}$ that is also a part of $S$. The closed neighbourhood of
$v$ is $|C^{*}|+|N(C_{i})\cap T|$. In order to protect $v$, we need to push at
least $\frac{|C^{*}|+|N(C_{i})\cap T|}{2}$ neighbours of $v$ to $S$. This can
be done in multiple ways, but we obtain a defensive alliance with smaller
cardinality by picking all the $\frac{|C^{*}|+|N(C_{i})\cap T|}{2}$ vertices
from $C^{*}$ itself. This concludes that, if there is any clique $C^{*}$ of
size at least $|N(C_{i})\cap T|$ has a vertex in $S$ then there exists a
defensive alliance, $S\subseteq C^{*}$. ∎ We consider two cases: (1) There
exists a vertex from a clique $C^{*}\in C_{i}$ of size at least $|N(C_{i})\cap
T|$ that is part of $S$. (2) No vertex from clique $C^{*}\in C_{i}$ of size at
least $|N(C_{i})\cap T|$ is a part of $S$.
For case 1, we solve $2^{|TC|}$ subproblems corresponding to each clique set.
We find the optimal solution in each subproblem by considering a vertex from
the shortest clique of size at least $|N(C_{i})\cap S|$ to be in $S$. From
Lemma 12, each subproblem can be solved in linear time in $n$. The minimum
value among all the $2^{|TC|}$ subproblems will be the optimal solution for
this case.
For case 2, we remove all the cliques from $G$ that cannot be a part of the
solution and obtain a new graph $G^{\prime}$. For each vertex $u\in P$, the
value of $demand(u)$ will remain the same as calculated in $G$. The size of
the largest clique outside the twin cover in $G^{\prime}$ is at most $|TC|$.
With the help of ILP formulation given in Theorem 7 and a bound on the largest
clique outside the twin cover $z\leq|TC|$, the instance can be solved in FPT
time.
The optimal solution to the problem is the minimum value obtained between the
two cases. This concludes the proof of Theorem 8.

##  7 Conclusions and Open Problems

In this work, we have proved that the DEFENSIVE ALLIANCE problem is
polynomial-time solvable on graphs with maximum degree at most 5 and NP-
Complete on graphs with maximum degree 6. The byproduct of our result is that
the problem is para-NP-hard parameterized by the maximum degree of the input
graph. Therefore, one could also work on larger structural parameters than the
maximum degree, such as the bandwidth and the maximum leaf number. A study of
the offensive and powerful alliance problems on bounded degree graphs can also
be considered.
We have also proved that the problem is fixed-parameter tractable
parameterized by twin cover and distance to clique. The problem remains
unsolved for the parameters modular width, and distance to cluster which is
also an interesting direction to pursue. It is interesting to study the
parameterized complexity of the offensive and powerful alliances for the
parameter twin cover and distance to cluster.

## Acknowledgements

The authors thank the anonymous reviewers for their valuable comments and
suggestions.

## References

  * [1] Chang, C.W., Chia, M.L., Hsu, C.J., Kuo, D., Lai, L.L., Wang, F.H.: Global defensive alliances of trees and cartesian product of paths and cycles. Discrete Applied Mathematics 160(4), 479–487 (2012)
  * [2] Chellali, M., Haynes, T.W.: Global alliances and independence in trees. Discuss. Math. Graph Theory 27(1), 19–27 (2007)
  * [3] Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)
  * [4] Enciso, R.: Alliances in graphs: parameterized algorithms and on partitioning series-parallel graphs. Ph.D. thesis, Clemson University, USA (2009)
  * [5] Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Proceedings of the 19th International Symposium on Algorithms and Computation. p. 294–305. Springer-Verlag (2008)
  * [6] Fernau, H., Binkele-Raible, D.: 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. pp. 61–70 (2007)
  * [7] Fernau, H., Rodríguez, J.A., Sigarreta, J.M.: Offensive $r$-alliances in graphs. Discrete Applied Mathematics 157(1), 177–182 (2009)
  * [8] Gaikwad, A., Maity, S., Tripathi, S.K.: Parameterized complexity of defensive and offensive alliances in graphs. In: Proceedings of the 17th International conference on Distributed Computing and Internet Technology. pp. 175–187 (2021)
  * [9] Gaikwad, A., Maity, S.: Defensive alliances in graphs. Theoretical Computer Science 928, 136–150 (2022)
  * [10] Ganian, R.: Improving Vertex Cover as a Graph Parameter. Discrete Mathematics and Theoretical Computer Science 17(2), 77–100 (2015)
  * [11] Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512–530 (2001)
  * [12] Jamieson, L., Hedetniemi, S., Mcrae, A.: The algorithmic complexity of alliances in graphs. JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing 68, 137–150 (2009)
  * [13] Jamieson, L.H.: Algorithms and Complexity for Alliances and Weighted Alliances of Various Types. Ph.D. thesis, Clemson University, USA (2007)
  * [14] Kannan, R.: Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research 12(3), 415–440 (1987)
  * [15] Kikuno, T., Yoshida, N., Kakuda, Y.: The np-completeness of the dominating set problem in cubic planer graphs. IEICE Transactions 6, 443–444 (1980)
  * [16] Kiyomi, M., Otachi, Y.: Alliances in graphs of bounded clique-width. Discrete Applied Mathematics 223, 91–97 (2017)
  * [17] Kristiansen, P., Hedetniemi, M., Hedetniemi, S.: Alliances in graphs. J. Comb. Math. Comb. Comput. 48, 157–177 (2004)
  * [18] Lenstra, H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8(4), 538–548 (1983)
  * [19] Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)
  * [20] Morgenstern, M.: Existence and explicit constructions of $q$ \+ 1 regular ramanujan graphs for every prime power $q$. Journal of Combinatorial Theory, Series B 62(1), 44–62 (1994)
  * [21] Shafique, K., Dutton, R.: Maximum alliance-free and minimum alliance-cover sets. Congressus Numerantium 162, 139–146 (2003)
  * [22] West, D.B.: Introduction to Graph theory. Prentice Hall (2000)