11institutetext: Indian Institute of Science Education and Research, Pune,
India 11email<EMAIL_ADDRESS>11email:
<EMAIL_ADDRESS>
# Offensive Alliances in Graphs

Ajinkya Gaikwad The first author gratefully acknowledges support from the
Ministry of Human Resource Development, Government of India, under Prime
Minister’s Research Fellowship Scheme (No. MRF-192002-211). Soumen Maity The
second author’s research was supported in part by the Science and Engineering
Research Board (SERB), Govt. of India, under Sanction Order No.
MTR/2018/001025.

###### Abstract

The Offensive Alliance problem has been studied extensively during the last
twenty years. A set $S\subseteq V$ of vertices is an offensive alliance in an
undirected graph $G=(V,E)$ if each $v\in N(S)$ has at least as many neighbours
in $S$ as it has neighbours (including itself) not in $S$. We study the
classical and parameterized complexity of the Offensive Alliance problem,
where the aim is to find a minimum size offensive alliance. We enhance our
understanding of the problem from the viewpoint of parameterized complexity by
showing that (1) the problem is W[1]-hard parameterized by a wide range of
fairly restrictive structural parameters such as the feedback vertex set
number, treewidth, pathwidth, and treedepth of the input graph; we thereby
resolve an open question stated by Bernhard Bliem and Stefan Woltran (2018)
concerning the complexity of Offensive Alliance parameterized by treewidth,
(2) unless ETH fails, Offensive Alliance problem cannot be solved in time
$\mathcal{O}^{*}(2^{o(k\log k)})$ where $k$ is the solution size, (3)
Offensive Alliance problem does not admit a polynomial kernel parameterized by
solution size and vertex cover of the input graph. On the positive side we
prove that (4) Offensive Alliance can be solved in time
$\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)})})$ where $\tt{vc(G)}$ is
the vertex cover number of the input graph. In terms of classical complexity,
we prove that (5) Offensive Alliance cannot be solved in time $2^{o(n)}$ even
when restricted to bipartite graphs, unless ETH fails, (6) Offensive Alliance
cannot be solved in time $2^{o(\sqrt{n})}$ even when restricted to apex
graphs, unless ETH fails. We also prove that (7) Offensive Alliance is NP-
complete even when restricted to bipartite, chordal, split and circle graphs.

###### Keywords:

Defensive and Offensive alliance Parameterized Complexity FPT W[1]-hard
treewidth ETH

##  1 Introduction

This paper studies the Offensive Alliance problem: given an undirected graph
$G$ and a positive integer $r$, determine whether $G$ admits an offensive
alliance of size at most $r$. It is not surprising that the complexity of
Offensive Alliance and several of its variants has been studied extensively by
the theory community in the past years. The decision version for several types
of alliances have been shown to be NP-complete. For an integer $\ell$, a
nonempty set $S\subseteq V(G)$ is a defensive $\ell$-alliance if for each
$v\in S$, $d_{S}(v)\geq d_{S^{c}}(v)+\ell$. A set is a defensive alliance if
it is a defensive $(-1)$-alliance. A defensive $\ell$-alliance $S$ is global
if $S$ is a dominating set. The defensive $\ell$-alliance problem is NP-
complete for any $\ell$ [SIGARRETA20091687]. The defensive alliance problem is
NP-complete even when restricted to split, chordal and bipartite graph
[Lindsay]. For an integer $\ell$, a nonempty set $S\subseteq V(G)$ is an
offensive $\ell$-alliance if for each $v\in N(S)$, $d_{S}(v)\geq
d_{S^{c}}(v)+\ell$. An offensive 1-alliance is called an offensive alliance.
An offensive $\ell$-alliance $S$ is global if $S$ is a dominating set. Fernau
et al. showed that the offensive $\ell$-alliance and global offensive
$\ell$-alliance problems are NP-complete for any fixed $\ell$ [FERNAU2009177].
They also proved that for $\ell>1$, $\ell$-offensive alliance is NP-hard, even
when restricted to $r$-regular planar graphs. There are polynomial time
algorithms for finding minimum alliances in trees [CHANG2012479, Lindsay]. A
polynomial time algorithm for finding minimum defensive alliance in series
parallel graph is presented in [10.5555/1292785].

Fernau and Raible showed in [Fernau] that the defensive, offensive and
powerful alliance problems and their global variants are fixed parameter
tractable when parameterized by solution size $r$. Kiyomi and Otachi showed in
[KIYOMI201791], the problems of finding smallest alliances of all kinds are
fixed-parameter tractable when parameteried by the vertex cover number. The
problems of finding smallest defensive and offensive alliances are also fixed-
parameter tractable when parameteried by the neighbourhood diversity
[ICDCIT2021]. Enciso [Enciso2009AlliancesIG] proved that finding defensive and
global defensive alliances is fixed parameter tractable when parameterized by
domino treewidth. Bliem and Woltran [BLIEM2018334] proved that deciding if a
graph contains a defensive alliance of size at most $r$ is W[1]-hard when
parameterized by treewidth of the input graph. This puts it among the few
problems that are FPT when parameterized by solution size but not when
parameterized by treewidth (unless FPT=W[1]).

_Contribution:_ The parameterized complexity of Offensive Alliance
parameterized by several structural parameters has remained unexplored. We
resolve the problem with most of these parameters. We mostly discuss the
parameters that deal with sparseness of graph. We show that the problem is
W[1]-hard parameterized by any of the following parameters: the feedback
vertex set number, treewidth, pathwidth, and treedepth of the input graph.
Interestingly, our result is significantly stronger since we show that
hardness even applies in the case that the remaining parts, after deleting the
feedback vertex set, are trees of height at most seven. Next, we turn our
attention to parameters vertex cover number and solution size. As mentioned
before, it is already proved that Offensive Alliance problem admits FPT
algorithms parameterized by each of these parameters individually. As there is
no hope to get FPT algorithms with small structural parameters, we need to
make the most out of these two parameters by obtaining efficient algorithms
and kernels. The algorithm mentioned in [Enciso2009AlliancesIG], has a running
time $\mathcal{O}^{*}(2^{\mathcal{O}(r\log r)})$. The first question that
arises from here is that whether we can get a single exponential algorithm? We
answer this question in a negative way by proving that unless ETH fails,
Offensive Alliance problem cannot be solved in time
$\mathcal{O}^{*}(2^{o(r\log r)})$. For the parameter vertex cover number, the
algorithm mentioned in [KIYOMI201791] has running time
$\mathcal{O}^{*}({(2^{\tt{vc(G)}})}^{\mathcal{O}(2^{\tt{vc(G)}})})$. In this
case, we improve the running time to
$\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)}})$ where $\tt{vc(G)}$ is
the vertex cover number of the input graph. Finally, we show that it is
unlikely to get polynomial kernel when parameterized by both of these
parameters combined.

In search of efficient algorithms, alliance problems have been studied on
special graph classes. There are polynomial time algorithms for finding
minimum alliances in trees [CHANG2012479, Lindsay]. A polynomial time
algorithm for finding minimum defensive alliance in series parallel graph is
given in [10.5555/1292785]. But still, alliance problems remained unexplored
on special classes of intersection graphs such as interval graphs, circle
graphs, circular arc graphs, unit disk graphs etc. We show that the problem
remains NP-hard even when restricted to bipartite, chordal, split and circle
graphs. We also prove that the known algorithms on general graphs and apex
graphs are unlikely to improve. This is done by showing that the problem
cannot be solved in $2^{o(n)}$ time even when restricted to bipartite graphs
and also the problem cannot be solved in $2^{o(\sqrt{n})}$ time even when
restricted to apex graphs, unless ETH fails.

##  2 Preliminaries

In real life, an alliance is a collection of people, groups, or states such
that the union is stronger than individual. The alliance can be either to
achieve some common purpose, to protect against attack, or to assert
collective will against others. This motivates the definitions of defensive
and offensive alliances in graphs. The properties of alliances in graphs were
first studied by Kristiansen, Hedetniemi, and Hedetniemi [kris]. They
introduced defensive, offensive and powerful alliances. An alliance is global
if it is a dominating set. The alliance problems have been studied extensively
during last twenty years [frick, SIGARRETA20061345, chel, ROD, SIGA], and
generalizations called $r$-alliances are also studied [SIGARRETA20091687].
Throughout this article, $G=(V,E)$ denotes a finite, simple and undirected
graph of order $|V|=n$. The subgraph induced by $S\subseteq V(G)$ is denoted
by $G[S]$. For a vertex $v\in V$, we use $N_{G}(v)=\\{u\leavevmode\nobreak\
:\leavevmode\nobreak\ (u,v)\in E(G)\\}$ to denote the (open) neighbourhood of
vertex $v$ in $G$, and $N_{G}[v]=N_{G}(v)\cup\\{v\\}$ to denote the closed
neighbourhood of $v$. The degree $d_{G}(v)$ of a vertex $v\in V(G)$ is
$|N_{G}(v)|$. For a subset $S\subseteq V(G)$, we define its closed
neighbourhood as $N_{G}[S]=\bigcup_{v\in S}N_{G}[v]$ and its open
neighbourhood as $N_{G}(S)=N_{G}[S]\setminus S$. For a non-empty subset
$S\subseteq V$ and a vertex $v\in V(G)$, $N_{S}(v)$ denotes the set of
neighbours of $v$ in $S$, that is, $N_{S}(v)=\\{u\in S\leavevmode\nobreak\
:\leavevmode\nobreak\ (u,v)\in E(G)\\}$. We use $d_{S}(v)=|N_{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}$.

######  Definition 1.

A non-empty set $S\subseteq V$ is a defensive alliance in $G$ if
$d_{S}(v)+1\geq d_{S^{c}}(v)$ for all $v\in S$.

Since each vertex in a defensive alliance $S$ has at least as many vertices
from its closed neighbor in $S$ as it has in $S^{c}$, by strength of numbers,
we say that every vertex in $S$ can be defended from possible attack by
vertices in $S^{c}$.

######  Definition 2.

A non-empty set $S\subseteq V$ is an offensive alliance in $G$ if
$d_{S}(v)\geq d_{S^{c}}(v)+1$ for all $v\in N(S)$.

Since each vertex in $N(S)$ has more neighbors in $S$ than in $S^{c}$, we say
that every vertex in $N(S)$ is vulnerable to possible attack by vertices in
$S$. Equivalently, since an attack by the vertices in $S$ on the vertices in
$V\setminus S$ can result in no worse than a “tie” for $S$, we say that $S$
can effectively attack $N(S)$.

######  Definition 3.

A non-empty set $S\subseteq V$ is a strong offensive alliance in $G$ if
$d_{S}(v)\geq d_{S^{c}}(v)+2$ for all $v\in N(S)$.

In this paper, we consider Offensive Alliance and Strong Offensive Alliance
problems under structural parameters. We define these problems as follows:
Offensive Alliance
Input: An undirected graph $G=(V,E)$ and an integer $r\geq 1$. Question: Is
there an offensive alliance $S\subseteq V(G)$ such that $1\leq|S|\leq r$?
Strong Offensive Alliance
Input: An undirected graph $G=(V,E)$ and an integer $r\geq 1$. Question: Is
there a strong offensive alliance $S\subseteq V(G)$ such that $1\leq|S|\leq
r$?

For standard notations and definitions in graph theory, we refer to West
[west]. For the standard concepts in parameterized complexity, see the recent
textbook by Cygan et al. [marekcygan]. The graph parameters we explicitly use
in this paper are feedback vertex set number, pathwidth, treewidth and
treedepth.

######  Definition 4.

For a graph $G=(V,E)$, the parameter feedback vertex set is the cardinality of
a smallest set $S\subseteq V(G)$ such that the graph $G-S$ is a forest and it
is denoted by $fvs(G)$.

We now review the concept of a tree decomposition, introduced by Robertson and
Seymour in [Neil]. Treewidth is a measure of how “tree-like” the graph is.

######  Definition 5.

[Downey] A tree decomposition of a graph $G=(V,E)$ is a tree $T$ together with
a collection of subsets $X_{t}$ (called _bags_) of $V$ labeled by the vertices
$t$ of $T$ such that $\bigcup_{t\in T}X_{t}=V$ and (1) and (2) below hold:

  1. 1.

For every edge $uv\in E(G)$, there is some $t$ such that $\\{u,v\\}\subseteq
X_{t}$.

  2. 2.

(Interpolation Property) If $t$ is a vertex on the unique path in $T$ from
$t_{1}$ to $t_{2}$, then $X_{t_{1}}\cap X_{t_{2}}\subseteq X_{t}$.

######  Definition 6.

[Downey] The width of a tree decomposition is the maximum value of $|X_{t}|-1$
taken over all the vertices $t$ of the tree $T$ of the decomposition. The
treewidth of a graph $G$ is the minimum width among all possible tree
decompositions of $G$.

$b$$a$$c$$d$$h$$e$$f$$g$$b,d$$a,b,d$$c,b,d$$c,d,h$$c,h,g$$h,e$$c,g,f$ Figure
1: Example of a tree decomposition of width 2

######  Example 1.

Figure 1 gives an example of a tree decomposition of width 2.

######  Definition 7.

If the tree $T$ of a tree decomposition is a path, then we say that the tree
decomposition is a path decomposition, and use pathwidth in place of
treewidth.

A rooted forest is a disjoint union of rooted trees. Given a rooted forest
$F$, its _transitive closure_ is a graph $H$ in which $V(H)$ contains all the
nodes of the rooted forest, and $E(H)$ contain an edge between two vertices
only if those two vertices form an ancestor-descendant pair in the forest $F$.

######  Definition 8.

The treedepth of a graph $G$ is the minimum height of a rooted forest $F$
whose transitive closure contains the graph $G$. It is denoted by $td(G)$.

vc nd tc vi td fvs pw mw cvd tw cw Figure 2:  Relationship between vertex
cover (vc), neighbourhood diversity (nd), twin cover (tc), modular width (mw),
cluster vertex deletion number (cvd), feedback vertex set (fvs), pathwidth
(pw), treewidth (tw) and clique width (cw). Note that $A\rightarrow B$ means
that there exists a function $f$ such that for all graphs, $f(A(G))\geq B(G)$.
It also gives an overview of the parameterized complexity landscape for the
Offensive alliance problem with general thresholds. The problem is FPT
parameterized by blue colored parameters and W[1]-hard when parameterized by
red colored parameters. The problem remains unsettled when parameterized by
twin cover, modular width and cluster vertex deletion number.

###  2.1 Parameterized Complexity

A _parameterized problem_ is a language
$L\subseteq\Sigma^{\star}\times\mathbb{N}$, where $\Sigma$ is a fixed, finite
alphabet. For an instance $(x,k)\in\Sigma^{\star}\times\mathbb{N}$, $k$ is
called the _parameter_. A parameterized problem $\mathcal{P}$ is _fixed-
parameter tractable_ (FPT in short) if a given instance $(x,k)$ can be solved
in time $f(k)\cdot{|(x,k)|}^{c}$ where $f$ is some (usually computable)
function, and $c$ is a constant. Parameterized complexity classes are defined
with respect to fpt-reducibility. A parameterized problem $\mathcal{P}$ is
fpt-reducible to $\mathcal{Q}$ if in time $f(k)\cdot{|(x,k)|}^{c}$, one can
transform an instance $(x,k)$ of $\mathcal{P}$ into an instance
$(x^{\prime},k^{\prime})$ of $Q$ such that $(x,k)\in\mathcal{P}$ if and only
if $(x^{\prime},k^{\prime})\in\mathcal{Q}$, and $k^{\prime}\leq g(k)$, where
$f$ and $g$ are computable functions depending only on $k$. Owing to the
definition, if $\mathcal{P}$ fpt-reduces to $\mathcal{Q}$ and $\mathcal{Q}$ is
fixed-parameter tractable then $\mathcal{P}$ is fixed-parameter tractable as
well.

What makes the theory more interesting is a hierarchy of intractable
parameterized problem classes above FPT which helps in distinguishing those
problems that are not fixed parameter tractable. Central to parameterized
complexity is the following hierarchy of complexity classes, defined by the
closure of canonical problems under fpt-reductions: FPT $\subseteq$ W[1]
$\subseteq$ W[2] $\subseteq\ldots\subseteq$ XP. All inclusions are believed to
be strict. In particular, FPT $\neq$ W[1] under the Exponential Time
Hypothesis [Paturi]. The class W[1] is the analog of NP in parameterized
complexity. A major goal in parameterized complexity is to distinguish between
parameterized problems which are in FPT and those which are _W[1]-hard_ ,
i.e., those to which every problem in W[1] is _fpt-reducible_. There are many
problems shown to be complete for W[1], or equivalently _W[1]-complete_ ,
including the MultiColored Clique (MCC) problem [Downey].

Closely related to fixed-parameter tractability is the notion of
preprocessing. A _reduction to a problem kernel_ , or equivalently, _problem
kernelization_ means to apply a data reduction process in polynomial time to
an instance $(x,k)$ such that for the reduced instance
$(x^{\prime},k^{\prime})$ it holds that $(x^{\prime},k^{\prime})$ is
equivalent to $(x,k)$, $|x^{\prime}|\leq g(k)$ and $k^{\prime}\leq g(k)$ for
some function $g$ only depending on $k$. Such a reduced instance is called a
_problem kernel_. It is easy to show that a parameterized problem is in FPT if
and only if there is kernelization algorithm. A _polynomial kernel_ is a
kernel, whose size can be bounded by a polynomial in the parameter. We refer
to [marekcygan, Downey] for further details on parameterized complexity.

##  3 W[1]-Hardness Parameterized by Structural Parameters

In this section we show that Offensive Alliance is W[1]-hard parameterized by
a vertex deletion set to trees of height at most seven, that is, a subset $D$
of the vertices of the graph such that every component in the graph, after
removing $D$, is a tree of height at most seven. On the way towards this
result, we provide hardness results for several interesting versions of the
Offensive Alliance problem which we require in our proofs. The problem
Offensive Alliance${}^{\mbox{F}}$ generalizes Offensive Alliance where some
vertices are forced to be outside the solution; these vertices are called
forbidden vertices. This variant can be formalized as follows:
Offensive Alliance${}^{\mbox{F}}$
Input: An undirected graph $G=(V,E)$, an integer $r$ and a set
$V_{\square}\subseteq V$ of forbidden vertices such that each degree one
forbidden vertex is adjacent to another forbidden vertex and each forbidden
vertex of degree greater than one is adjacent to a degree one forbidden
vertex. Question: Is there an offensive alliance $S\subseteq V$ such that (i)
$1\leq|S|\leq r$, and (ii) $S\cap V_{\square}=\emptyset$?
Strong Offensive Alliance${}^{\mbox{FN}}$ is a generalization of Strong
Offensive Alliance${}^{\mbox{F}}$ that, in addition, requires some “necessary”
vertices to be in $S$. This variant can be formalized as follows:
Strong Offensive Alliance${}^{\mbox{FN}}$
Input: An undirected graph $G=(V,E)$, an integer $r$, a set
$V_{\triangle}\subseteq V$, and a set $V_{\square}\subseteq V$ of forbidden
vertices such that each degree one forbidden vertex is adjacent to another
forbidden vertex and each forbidden vertex of degree greater than one is
adjacent to a degree one forbidden vertex. Question: Is there a strong
offensive alliance $S\subseteq V$ such that (i) $1\leq|S|\leq r$, (ii) $S\cap
V_{\square}=\emptyset$, and (iii) $V_{\triangle}\subseteq S$?

While the Offensive Alliance problem asks for offensive alliance of size at
most $r$, we also consider the Exact Offensive Alliance problem that concerns
offensive alliance of size exactly $r$. Analogously, we also define exact
versions of Strong Offensive Alliance presented above. To prove Lemma 2, we
consider a variant of the following problem:
Multidimensional Subset Sum (MSS)
Input: An integer $k$, a set $S=\\{s_{1},\ldots,s_{n}\\}$ of vectors with
$s_{i}\in\mathbb{N}^{k}$ for every $i$ with $1\leq i\leq n$ and a target
vector $t\in\mathbb{N}^{k}$. Parameter: $k$
Question: Is there a subset $S^{\prime}\subseteq S$ such that
$\sum\limits_{s\in S^{\prime}}{s}=t$?

In the Multidimensional Relaxed Subset Sum (MRSS) problem, an additional
integer $k^{\prime}$ is given (which will be part of the parameter) and we ask
whether there is a subset $S^{\prime}\subseteq S$ with $|S^{\prime}|\leq
k^{\prime}$ such that $\sum\limits_{s\in S^{\prime}}{s}\geq t$. More formally,
Multidimensional Relaxed Subset Sum (MRSS)
Input: Two integers $k$ and $k^{\prime}$, a set $S=\\{s_{1},\ldots,s_{n}\\}$
of vectors with $s_{i}\in\mathbb{N}^{k}$ for every $i$ with $1\leq i\leq n$
and a target vector $t\in\mathbb{N}^{k}$. Parameter: $k+k^{\prime}$
Question: Is there a subset $S^{\prime}\subseteq S$ with $|S^{\prime}|\leq
k^{\prime}$ such that $\sum\limits_{s\in S^{\prime}}{s}\geq t$?

######  Lemma 1.

[mss] MRSS is W[1]-hard when parameterized by the combined parameter
$k+k^{\prime}$, even if all integers in the input are given in unary.

We now show that the Strong Offensive Alliance${}^{\mbox{FN}}$ problem is
W[1]-hard parameterized by the size of a vertex deletion set into trees of
height at most 5, via a reduction from MRSS.

######  Lemma 2.

The Strong Offensive Alliance${}^{\mbox{FN}}$ problem is W[1]-hard when
parameterized by the size of a vertex deletion set into trees of height at
most 5.

###### Proof.

To prove this we reduce from MRSS, which is known to be W[1]-hard when
parameterized by the combined parameter $k+k^{\prime}$, even if all integers
in the input are given in unary [mss]. Let $I=(k,k^{\prime},S,t)$ be an
instance of MRSS. We construct an instance
$I^{\prime}=(G,r,V_{\triangle},V_{\square})$ of Strong Offensive
Alliance${}^{\mbox{FN}}$ in the following way. See Figure 3 for an
illustration.

${u_{1}}$${u_{2}}$${a_{2}^{\square s_{1}}}$${a_{1}^{\square
s_{1}}}$$b_{1}^{\square s_{1}}$$a_{1}^{s_{1}}$$b_{1}^{s_{1}}$$b_{3}^{\square
s_{1}}$$a_{3}^{s_{1}}$$b_{3}^{s_{1}}$${a_{3}^{\square s_{1}}}$$b_{2}^{\square
s_{1}}$$a_{2}^{s_{1}}$$b_{2}^{s_{1}}$$x_{s_{1}}$${z_{s_{1}}}$$y_{s_{1}}$$c_{1}^{s_{1}}$$c_{2}^{s_{1}}$$c_{3}^{s_{1}}$$c_{4}^{s_{1}}$${a}$${a_{1}^{\triangle}}$${a_{2}^{\triangle}}$${a_{3}^{\triangle}}$${a^{\square}}$${a_{1}^{\square
s_{2}}}$${a_{2}^{\square s_{2}}}$$b_{1}^{\square
s_{2}}$$a_{1}^{s_{2}}$$b_{1}^{s_{2}}$$b_{2}^{\square
s_{2}}$$a_{2}^{s_{2}}$$b_{2}^{s_{2}}$${z_{s_{2}}}$$x_{s_{2}}$$y_{s_{2}}$$c_{1}^{s_{2}}$$c_{2}^{s_{2}}$$c_{3}^{s_{2}}$$c_{4}^{s_{2}}$${a_{1}^{\square
s_{3}}}$${a_{2}^{\square s_{3}}}$${a_{3}^{\square s_{3}}}$$b_{1}^{\square
s_{3}}$$a_{1}^{s_{3}}$$b_{1}^{s_{3}}$$b_{2}^{\square
s_{3}}$$a_{2}^{s_{3}}$$b_{2}^{s_{3}}$$b_{3}^{\square
s_{3}}$$a_{3}^{s3}$$b_{3}^{s_{3}}$${z_{s_{3}}}$$x_{s_{3}}$$y_{s_{3}}$$c_{1}^{s_{3}}$$c_{2}^{s_{3}}$$c_{3}^{s_{3}}$$c_{4}^{s_{3}}$$c_{5}^{s_{3}}$$c_{6}^{s_{3}}$
Figure 3: The graph $G$ in the proof of Lemma 2 constructed for MRSS instance
$S=\\{(2,1),(1,1),(1,2)\\}$, $t=(3,3)$, $k=2$ and $k^{\prime}=2$.

First, we introduce a set of $k$ forbidden vertices
$U=\\{u_{1},u_{2},\ldots,u_{k}\\}$. For each vector
$s=(s(1),s(2),\ldots,s(k))\in S$, we introduce a tree $T_{s}$ into $G$. We
define $\mbox{max}(s)=\max\limits_{1\leq i\leq k}\\{s(i)\\}$. The vertex set
of tree $T_{s}$ is defined as follows:

$V(T_{s})=A_{s}\cup B_{s}\cup A^{\square}_{s}\cup B^{\square}_{s}\cup
C_{s}\cup Z_{s}\cup\Big{\\{}x_{s},y_{s},z_{s}\Big{\\}}$

where $A_{s}=\\{a^{s}_{1},\ldots,a^{s}_{\max(s)+1}\\}$,
$B_{s}=\\{b^{s}_{1},\ldots,b^{s}_{\max(s)+1}\\}$,
$A_{s}^{\square}=\\{a^{\square s}_{1},\ldots,a^{\square s}_{\max(s)+1}\\}$,
$B_{s}^{\square}=\\{b^{\square s}_{1},\ldots,b^{\square s}_{\max(s)+1}\\}$ and
$C_{s}=\\{c_{1}^{s},\ldots,c_{2\max{(s)+2}}^{s}\\}$ are five sets of vertices,
and the set $Z_{s}=\\{z^{\triangle s}_{1},z^{\triangle s}_{2},z^{\triangle
s}_{3},z^{\triangle s}_{4},z^{\triangle s}_{5},z^{\square s}\\}$ contains five
necessary vertices and one forbidden vertex. We now create the edge set of
$T_{s}$.

$\displaystyle E(T_{s})$
$\displaystyle=\bigcup\limits_{i=1}^{{\max(s)+1}}\Big{\\{}(a_{i}^{\square
s},b_{i}^{\square s}),(a_{i}^{\square s},a_{i}^{s}),(a_{i}^{\square
s},b_{i}^{s}),(x_{s},a_{i}^{\square s})\Big{\\}}$
$\displaystyle\bigcup\limits_{i=1}^{5}\\{(z_{s},z_{i}^{\triangle
s}),(z_{s},z^{\square
s})\\}\bigcup\\{(x_{s},z_{s}),(z_{s},y_{s})\\}\bigcup\limits_{i=1}^{2\max(s)+2}(y_{s},c_{i}^{s})$

Next we introduce a vertex $a$ and a set of four vertices
$A=\\{a_{1}^{\triangle},a_{2}^{\triangle},a_{3}^{\triangle},a^{\square}\\}$
containing three necessary vertices and one forbidden vertex. Make $a$
adjacent to all the vertices in $A$. For each $i\in\\{1,2,\ldots,k\\}$ and for
each $s\in S$, we make $u_{i}$ adjacent to exactly $s(i)$ many vertices of
$A_{s}$ in arbitrary manner. For each $s\in S$, we make $a$ adjacent to all
the vertices of $A_{s}\cup B_{s}\cup C_{s}$. For every $u_{i}\in U$, we create
a set $V_{u_{i}\square}$ of $\sum\limits_{s\in S}{s(i)}$ forbidden vertices
and a set $V_{u_{i}\triangle}$ of $2\sum\limits_{s\in S}{s(i)}-2t(i)+2$
necessary vertices; and make $u_{i}$ adjacent to every vertex of
$V_{u_{i}\square}\cup V_{u_{i}\triangle}$. We define

$V_{\triangle}=\bigcup\limits_{i=1}^{k}V_{u_{i}\triangle}\bigcup
A\setminus\\{a^{\square}\\}\bigcup\limits_{s\in S}{Z_{s}\setminus\\{z^{\square
s}\\}}$

and

$V_{\square}=U\cup\\{a,a^{\square}\\}\bigcup\limits_{i=1}^{k}V_{u_{i}\square}\bigcup\limits_{s\in
S}A_{s}^{\square}\cup B_{s}^{\square}\cup\\{z_{s},z^{\square s}\\}.$

We set $r=\sum\limits_{i=1}^{k}{2\Big{(}\sum\limits_{s\in
S}{s(i)}-t(i)+1\Big{)}}+\sum\limits_{s\in S}2(\max(s)+1)+5n+3+k^{\prime}$.
Observe that if we remove the set $U\cup\\{a\\}$ of $k+1$ vertices from $G$,
each connected component of the resulting graph is a tree with height at most
5. Note that, $I^{\prime}$ can be constructed in polynomial time. The reason
is this. As all integers in $I$ are bounded by a polynomial in $n$, the number
of vertices in $G$ is also polynomially bounded in $n$.

It remains to show that $I$ is a yes instance if and only if $I^{\prime}$ is a
yes instance. Towards showing the forward direction, let $S^{\prime}$ be a
subset of $S$ such that $|S^{\prime}|\leq k^{\prime}$ and $\sum\limits_{s\in
S^{\prime}}{s}\geq t$. We claim

$R=V_{\triangle}\bigcup\limits_{s\in S^{\prime}}A_{s}\cup
B_{s}\cup\\{x_{s}\\}\bigcup\limits_{s\in S\setminus S^{\prime}}C_{s}$

is a strong offensive alliance of $G$ such that $|R|\leq r$,
$V_{\triangle}\subseteq R$, and $V_{\square}\cap R=\emptyset$. Observe that
$N_{G}(R)=U\cup\\{a\\}\bigcup\limits_{s\in S}\\{z_{s}\\}\bigcup\limits_{s\in
S\setminus S^{\prime}}\\{y_{s}\\}\bigcup\limits_{s\in
S^{\prime}}A_{s}^{\square}$. Let $u_{i}\in U$, then we show that
$d_{R}(u_{i})\geq d_{R^{c}}(u_{i})+2$. As $\sum\limits_{s\in
S^{\prime}}s(i)-t(i)\geq 0$, we get

$\begin{split}d_{R}(u_{i})&=\sum\limits_{s\in
S^{\prime}}s(i)+|V_{u_{i}\triangle}|\\\ &=\sum\limits_{s\in
S^{\prime}}s(i)+2\sum\limits_{s\in S}{s(i)}-2t(i)+2\\\
&=\Big{(}\sum\limits_{s\in S^{\prime}}s(i)-t(i)\Big{)}+\sum\limits_{s\in
S}{s(i)}-t(i)+\sum\limits_{s\in S}{s(i)}+2\\\ &\geq\sum\limits_{s\in
S}{s(i)}-t(i)+\sum\limits_{s\in S}{s(i)}+2\\\ &=\sum\limits_{s\in S\setminus
S^{\prime}}{s(i)}+\Big{(}\sum\limits_{s\in
S^{\prime}}{s(i)}-t(i)\Big{)}+\sum\limits_{s\in S}{s(i)}+2\\\
&\geq\sum\limits_{s\in S\setminus S^{\prime}}{s(i)}+\sum\limits_{s\in
S}{s(i)}+2=\sum\limits_{s\in S\setminus
S^{\prime}}{s(i)}+|V_{u_{i}\square}|+2\\\ &=d_{R^{c}}(u_{i})+2.\end{split}$

For the remaining vertices $x$ in $N(R)$, it is easy to see that $d_{R}(x)\geq
d_{R^{c}}(x)+2$. Therefore, $R$ is a strong offensive alliance.

Towards showing the reverse direction of the equivalence, suppose $G$ has a
strong offensive alliance $R$ of size at most $r$ such that
$V_{\triangle}\subseteq R$ and $V_{\square}\cap R=\emptyset$. From the
definition of $V_{\triangle}$ and $V_{\square}$, it is easy to note that
$U\subseteq N(R)$. We know $V_{\triangle}$ contains
$\sum\limits_{i=1}^{k}{\Big{(}\sum\limits_{s\in S}{2s(i)}-2t(i)\Big{)}+5n+3}$
vertices; thus besides the vertices of $V_{\triangle}$, there are at most
$\sum\limits_{s\in S}2(\max(s)+1)+k^{\prime}$ vertices in $R$. Since $a\in
N(V_{\triangle})$ and $d_{G}(a)=\sum\limits_{s\in S}4(\max(s)+1)+4$ where $a$
is adjacent to three necessary vertices, it must have at least
$\sum\limits_{s\in S}2(\max(s)+1)$ many neighbours in $R$ from the set
$\bigcup\limits_{s\in S}(A_{s}\cup B_{s}\cup C_{s})$. It is to be noted that
if a vertex from the set $A_{s}\cup B_{s}$ is in the solution then the whole
set $A_{s}\cup B_{s}\cup\\{x_{s}\\}$ lie in the solution. Otherwise $v\in
A_{s}^{\square}\subseteq N(R)$ will have $d_{R}(v)<d_{R^{c}}(v)+2$ which is a
contradiction as $R$ is a strong offensive alliance. This shows that at most
$k^{\prime}$ many sets of the form $A_{s}\cup B_{s}\cup\\{x_{s}\\}$ contribute
to the solution as otherwise the size of solution exceeds $r$. Therefore, any
strong offensive alliance $R$ of size at most $r$ can be transformed to
another strong offensive alliance $R^{\prime}$ of size at most $r$ as follows:

$R^{\prime}=V_{\triangle}\bigcup\limits_{x_{s}\in R}A_{s}\cup
B_{s}\cup\\{x_{s}\\}\bigcup\limits_{x_{s}\in V(G)\setminus R}C_{s}.$

We define a subset $S^{\prime}=\Big{\\{}s\in S\leavevmode\nobreak\
|\leavevmode\nobreak\ x_{s}\in R^{\prime}\Big{\\}}.$ Clearly,
$|S^{\prime}|\leq k^{\prime}$. We claim that $\sum\limits_{s\in
S^{\prime}}s(i)\geq t(i)$ for all $1\leq i\leq k$. Assume for the sake of
contradiction that $\sum\limits_{s\in S^{\prime}}s(i)<t(i)$ for some
$i\in\\{1,2,\ldots,k\\}$. Then, we have

$\begin{split}d_{R^{\prime}}(u_{i})&=\sum\limits_{s\in
S^{\prime}}{s(i)}+|V_{u_{i}\triangle}|\\\ &=\sum\limits_{s\in
S^{\prime}}{s(i)}+2\sum\limits_{s\in S}{s(i)}-2t(i)+2\\\ &=\sum\limits_{s\in
S^{\prime}}{s(i)}-t(i)+\sum\limits_{s\in S}{s(i)}-t(i)+\sum\limits_{s\in
S}{s(i)}+2\\\ &<\sum\limits_{s\in S}{s(i)}-t(i)+\sum\limits_{s\in
S}{s(i)}+2\\\ &=\sum\limits_{s\in S\setminus
S^{\prime}}{s(i)}+\Big{(}\sum\limits_{s\in
S^{\prime}}{s(i)}-t(i)\Big{)}+\sum\limits_{s\in S}{s(i)}+2\\\
&<\sum\limits_{s\in S\setminus S^{\prime}}{s(i)}+\sum\limits_{s\in
S}{s(i)}+2=\sum\limits_{s\in S\setminus
S^{\prime}}{s(i)}+|V_{u_{i}\square}|+2\\\ &=d_{R^{\prime
c}}(u_{i})+2\end{split}$

and we also know $u_{i}\in N(R^{\prime})$, which is a contradiction to the
fact that $R^{\prime}$ is a strong offensive alliance. This shows that $I$ is
a yes instance. ∎

We have the following corollaries from Lemma 2.

######  Corollary 1.

The Strong Offensive Alliance${}^{\mbox{FN}}$ problem is W[1]-hard when
parameterized by the size of a vertex deletion set into trees of height at
most 5, even when $|V_{\triangle}|=1$.

###### Proof.

Given an instance $I=(G,r,V_{\triangle},V_{\square})$ of Strong Offensive
Alliance${}^{\mbox{FN}}$, we construct an equivalent instance
$I^{\prime}=(G^{\prime},r^{\prime},V_{\triangle}^{\prime},V_{\square}^{\prime})$
with $|V_{\triangle}^{\prime}|=1$. See Figure 4 for an illustration.

$x$$y$$v_{1}$$v_{2}$$v_{\ell}$$V_{x}^{\square}$ Figure 4: An illustration of
the gadget used in the proof of Corollary 1.

Let $v_{1},v_{2},\dots,v_{\ell}$ be vertices of $V_{\triangle}$ where we
assume that $\ell>1$. We introduce two vertices $x$ and $y$ where $x$ is a
forbidden vertex and $y$ is a necessary vertex; and make $x$ and $y$ adjacent.
We make $x$ adjacent to all the vertices in $V_{\triangle}$. We also introduce
a set $V_{x\square}$ of $\ell-1$ forbidden vertices and make them adjacent to
$x$. Set $r^{\prime}=r+1$. Define $V_{\triangle}^{\prime}=\\{y\\}$ and
$V_{\square}^{\prime}=\\{x\\}\cup V_{x\square}\cup V_{\square}$. We also
define $G^{\prime}$ as follows

$V(G^{\prime})=V(G)\cup\\{x,y\\}\cup V_{x\square}$

and

$E(G^{\prime})=E(G)\bigcup\Big{\\{}(x,y),(x,\alpha),(x,\beta)\leavevmode\nobreak\
|\leavevmode\nobreak\ \alpha\in V_{x\square},\beta\in V_{\triangle}\Big{\\}}.$

Let $H$ be a vertex deletion set of $G$ into trees of height at most 5.
Clearly, if $H$ has at most $k$ vertices then the set $H\cup\\{x\\}$ has at
most $k+1$ vertices and is a vertex deletion set of $G^{\prime}$ into trees of
height at most 5. It is easy to see that $I$ and $I^{\prime}$ are equivalent
instances.∎

We can get an analogous result for the exact variant.

######  Corollary 2.

The Exact Strong Offensive Alliance${}^{\mbox{FN}}$ problem is W[1]-hard when
parameterized by the size of a vertex deletion set into trees of height at
most 5 even when $|V_{\triangle}|=1$.

Next, we give an FPT reduction that eliminates necessary vertices.

######  Lemma 3.

The Offensive Alliance${}^{\mbox{F}}$ problem is W[1]-hard when parameterized
by the size of a vertex deletion set into trees of height at most 5.

###### Proof.

To prove this we reduce from the Strong Offensive Alliance${}^{\mbox{FN}}$
problem, which is W[1]-hard when parameterized by the size of a vertex
deletion set into trees of height at most 5, even when $|V_{\triangle}|=1$.
See Corollary 1. Given an instance $I=(G,r,V_{\triangle}=\\{x\\},V_{\square})$
of Strong Offensive Alliance${}^{\mbox{FN}}$, we construct an instance
$I^{\prime}=(G^{\prime},r^{\prime},V^{\prime}_{\square})$ of Offensive
Alliance${}^{\mbox{F}}$ the following way. See Figure 5 for an illustration.

${x^{\square}}$${v_{1}}$${v_{2}}$${v_{n^{\prime}}}$${f_{1}}$${f_{n^{\prime\prime}}}$${G}$$V_{x}^{\square}$${x}$${t_{1}}$${t_{2}}$${t_{4n}}$${t^{\square}}$${V_{t}^{\square}}$
Figure 5: The reduction from Strong Offensive Alliance${}^{\mbox{FN}}$ to
Offensive Alliance${}^{\mbox{F}}$ in Lemma 3. Note that the set
$\\{v_{1},\ldots,v_{n^{\prime}}\\}$ may contain forbidden vertices of degree
greater than one.

Let $n$ be the number of vertices in $G$ and let
$V(G)=\\{x,v_{1},v_{2},\ldots,v_{n^{\prime}},f_{1},\ldots,f_{n^{\prime\prime}}\\}$
where $F=\\{f_{1},\ldots,f_{n^{\prime\prime}}\\}$ is the set of degree one
forbidden vertices in $V(G)$. We introduce two vertices
$t^{\square},x^{\square}$ into $G^{\prime}$. We create a set
$V_{t}^{\square}=\\{t^{\square}_{1},\ldots,t^{\square}_{4n}\\}$ of $4n$
forbidden vertices into $G^{\prime}$ and make them adjacent to $t^{\square}$.
We introduce a set $V_{x}^{\square}$ of $n$ forbidden vertices and make them
adjacent to $x^{\square}$. Finally we create a set
$T=\\{t_{1},\ldots,t_{4n}\\}$ of $4n$ vertices and make the vertices in $T$
adjacent to $t^{\square}$ and $x^{\square}$, and make the vertices in
$V(G)\setminus F$ adjacent to $x^{\square}$. We also add an edge
$(x,t^{\square})$. Set $r^{\prime}=r+4n$. We define $G^{\prime}$ as follows:

$V(G^{\prime})=V(G)\cup T\cup V_{t}^{\square}\cup
V_{x}^{\square}\cup\\{t^{\square},x^{\square}\\}$

and

$\displaystyle E(G^{\prime})=$ $\displaystyle
E(G)\cup\Big{\\{}(t^{\square},\alpha)\leavevmode\nobreak\
:\leavevmode\nobreak\ \alpha\in T\cup V_{t}^{\square}\cup\\{x\\}\Big{\\}}$
$\displaystyle\cup\Big{\\{}(x^{\square},\beta)\leavevmode\nobreak\
:\leavevmode\nobreak\ \beta\in T\cup V_{x}^{\square}\cup V(G)\setminus
F\Big{\\}}$

We define $V_{\square}^{\prime}=V_{\square}\cup V_{t}^{\square}\cup
V_{x}^{\square}\cup\\{t^{\square},x^{\square}\\}$. Observe that there exists a
set of at most $k+2$ vertices in $G^{\prime}$ whose deletion makes the
resulting graph a forest containing trees of height at most 5. We can find
such a set because there exists a vertex deletion set $H$ of $G$ into trees of
height at most 5. We just add $\\{x^{\square},t^{\square}\\}$ to the set $H$,
then the resulting set is of size $k+2$ whose deletion makes the resulting
graph a forest containing trees of height at most 5.

We now claim that $I$ is a yes-instance if and only if $I^{\prime}$ is a yes-
instance. Assume first that $R$ is a strong offensive alliance of size at most
$r$ in $G$ such that $\\{x\\}\subseteq R$ and $V_{\square}\cap R=\emptyset$.
We claim $R^{\prime}=R\cup T$ is an offensive alliance of size at most $r+4n$
in $G^{\prime}$ such that $V^{\prime}_{\square}\cap R^{\prime}=\emptyset$.
Clearly, $N(R^{\prime})=\\{t^{\square},x^{\square}\\}\cup N(R)$. For each
$v\in N(R)$, we know that $d_{R}(v)\geq d_{R^{c}}(v)+2$ in $G$. Therefore in
graph $G^{\prime}$, we get $d_{R^{\prime}}(v)\geq d_{R^{\prime c}}(v)+1$ for
each $v\in N(R)$ due to the vertex $x^{\square}$. For
$v\in\\{x^{\square},t^{\square}\\}$, it is clear that $d_{R^{\prime}}(v)\geq
d_{R^{\prime c}}(v)+1$. This shows that $I^{\prime}$ is a yes instance.

To prove the reverse direction of the equivalence, suppose $R^{\prime}$ is an
offensive alliance of size at most $r^{\prime}=r+4n$ in $G^{\prime}$ such that
$R^{\prime}\cap V_{\square}^{\prime}=\emptyset$. We claim that
$T\cup\\{x\\}\subseteq R^{\prime}$. Since $R^{\prime}$ is non empty, it must
contain a vertex from the set $T\cup V(G)\setminus F$. Then $x^{\square}\in
N(R^{\prime})$ and it satisfies the condition $d_{R^{\prime}}(x^{\square})\geq
d_{R^{\prime c}}(x^{\square})+1$. Due to $n$ forbidden vertices in the set
$V_{x}^{\square}$, node $x^{\square}$ must have at least $n+1$ neighbours in
$R^{\prime}$. This implies that $R^{\prime}$ contains at least one vertex from
$T$. Then $t^{\square}\in N(R^{\prime})$ and it satisfies the condition
$d_{R^{\prime}}(t^{\square})\geq d_{{R^{\prime}}^{c}}(t^{\square})+1$. Since
$|V_{t}^{\square}|=4n$, the condition $d_{R^{\prime}}(t^{\square})\geq
d_{R^{\prime c}}(t^{\square})+1$ forces the set $\\{x\\}\cup T$ to be inside
the solution. Consider $R=R^{\prime}\cap V(G)$. Clearly $|R|\leq r$, $x\in R$,
$R\cap V_{\square}=\emptyset$ and we show that $R$ is a strong offensive
alliance in $G$. For each $v\in N(R^{\prime})\cap V(G)=N(R)$, we have
$N_{R^{\prime}}(v)\geq N_{R^{\prime c}}(v)+1$ in $G^{\prime}$. Notice that we
do not have $x^{\square}$ in $G$ which is adjacent to all vertices in $N(R)$.
Thus for each $v\in N(R)$, we get $N_{R}(v)\geq N_{R^{c}}(v)+2$ in $G$.
Therefore $R$ is a strong offensive alliance of size at most $r$ in $G$ such
that $x\in R$ and $R\cap V_{\square}=\emptyset$. This shows that $I$ is a yes
instance. ∎

######  Corollary 3.

The Exact Offensive Alliance${}^{\mbox{F}}$ problem is W[1]-hard when
parameterized by the size of a vertex deletion set into trees of height at
most 5.

We are now ready to show our main hardness result for Offensive Alliance using
a reduction from Offensive Alliance${}^{\mbox{F}}$.

######  Theorem 3.1.

The Offensive Alliance problem is W[1]-hard when parameterized by the size of
a vertex deletion set into trees of height at most 7.

###### Proof.

We give a parameterized reduction from Offensive Alliance${}^{\mbox{F}}$ which
is W[1]-hard when parameterized by the size of a vertex deletion set into
trees of height at most 5. Let $I=(G,r,V_{\square})$ be an instance of
Offensive Alliance${}^{\mbox{F}}$. Let $n=|V(G)|$. We construct an instance
$I^{\prime}=(G^{\prime},r^{\prime})$ of Offensive Alliance the following way.
We set $r^{\prime}=r$. Recall that each degree one forbidden vertex is
adjacent to another forbidden vertex and each forbidden vertex of degree
greater than one is adjacent to a degree one forbidden vertex. Let $u$ be a
degree one forbidden vertex in $G$ and $u$ is adjacent to another forbidden
vertex $v$. For each degree one forbidden vertex $u\in V_{\square}$, we
introduce a tree $T_{u}$ rooted at $u$ of height 2 as shown in Figure 6. The
forbidden vertex $v$ has additional neighbours from the original graph $G$
which are not shown in the figure. We define $G^{\prime}$ as follows:

$V(G^{\prime})=V(G)\bigcup\limits_{u\in
V_{\square}}\Big{\\{}V(T_{u})\leavevmode\nobreak\ |\leavevmode\nobreak\
\text{where }u\text{ is a degree one forbidden vertex in }G\Big{\\}}$

and

$\displaystyle E(G^{\prime})=E(G)\bigcup\limits_{u^{\prime}\in
V_{\square}}{E(T_{u})}.$

$v$$u$$u_{1}$$u_{4r}$${u_{1}^{1}}$${u_{1}^{4r}}$${u_{4r}^{4r}}$${u_{4r}^{1}}$
Figure 6: Our tree gadget $T_{u}$ for each degree one forbidden vertex $u\in
V_{\square}$

We claim $I$ is a yes instance if and only if $I^{\prime}$ is a yes instance.
It is easy to see that if $R$ is an offensive alliance of size at most $r$ in
$G$ such that $R\cap V_{\square}=\emptyset$, then it is also an offensive
alliance of size at most $r^{\prime}=r$ in $G^{\prime}$.

To prove the reverse direction of the equivalence, suppose that $G^{\prime}$
has an offensive alliance $R^{\prime}$ of size at most $r^{\prime}=r$. We
claim that no vertex from the set $V_{\square}\bigcup\limits_{u\in
V_{\square}}V(T_{u})$ is part of $R^{\prime}$. It is easy to see that if any
vertex from the set $V_{\square}\bigcup\limits_{u\in V_{\square}}V(T_{u})$ is
in $R^{\prime}$ then the size of $R^{\prime}$ exceeds $2r$. This implies that
$R=R^{\prime}\cap G$ is an offensive alliance such that $R\cap
V_{\square}=\emptyset$ and $|R|\leq r$. This shows that $I$ is a yes
instance.∎

We have the following consequences.

######  Corollary 4.

The Exact Offensive Alliance problem is W[1]-hard when parameterized by the
size of a vertex deletion set into trees of height at most 7.

Clearly trees of height at most seven are trivially acyclic. Moreover, it is
easy to verify that such trees have pathwidth [Kloks94] and treedepth
[Sparsity] at most seven, which implies:

######  Theorem 3.2.

The Offensive Alliance and Exact Offensive Alliance problems are W[1]-hard
when parameterized by any of the following parameters:

  * •

the feedback vertex set number,

  * •

the treewidth and pathwidth of the input graph,

  * •

the treedepth of the input graph.

##  4 FPT Lower Bound Parameterized by Solution Size

We know that Offensive Alliance admits an FPT algorithm when parameterized by
the solution size [Enciso2009AlliancesIG]. The algorithm in
[Enciso2009AlliancesIG] uses branching technique and solves the problem in
$\mathcal{O}^{*}(2^{\mathcal{O}(k\log k)})$ time. It appears that this running
time is essentially optimal assuming ETH, which is proved in the following
theorem. Hardness for Offensive Alliance follows from a reduction from
$k\times k$ (Permutation) Hitting Set with Thin Sets. In the $k\times k$
(Permutation) Hitting Set problem, we are given a family $\mathcal{F}$ of
subsets of $[k]\times[k]$, and we would like to find a set $X$, consisting of
one vertex from each row and induces a permutation of $[k]$, such that $X\cap
F\neq\emptyset$ for each $F\in\mathcal{F}$. In the _thin set_ variant we
assume that each $F\in\mathcal{F}$ contains at most one vertex from each row.
In the proof, we will use the fact that $k\times k$ (Permutation) Hitting Set
with Thin Sets cannot be solved in time $2^{o(k\log{k})}$, unless ETH fails
[Daniel-2018].

######  Theorem 4.1.

Unless ETH fails, Offensive Alliance cannot be solved in time
$\mathcal{O}^{*}(2^{o(k\log k)})$, where $k$ is the solution size.

###### Proof.

We provide a polynomial-time algorithm that takes an instance
$(\mathcal{F},k)$ of $k\times k$ (Permutation) Hitting Set with Thin Sets, and
outputs an equivalent instance $(G,r)$ of Offensive Alliance with $r=5k$. We
construct $G$ the following way.

  1. 1.

For every $F\in\mathcal{F}$, we introduce a vertex $v_{F}$ into $G$. Let
$V_{\mathcal{F}}=\\{v_{F}\leavevmode\nobreak\ |\leavevmode\nobreak\
F\in\mathcal{F}\\}$. We also introduce a set of $k^{2}$ vertices
$W=\\{w_{i,j}\leavevmode\nobreak\ :\leavevmode\nobreak\ i\in[k],j\in[k]\\}$.
Make $v_{F}$ adjacent to $w_{ij}$ if $(i,j)\in F$.

  2. 2.

We introduce a clique $D^{\triangle}$ of size $4k$ into $G$. For every $d\in
D^{\triangle}$, we add a set of $10k$ vertices and make them adjacent to $d$.
For every $F\in\mathcal{F}$, we make $v_{F}$ adjacent to every vertex of
$D^{\triangle}$.

  3. 3.

We introduce another clique $D^{\square}$ of size $12k+1$ into $G$. Let
$d_{W}(v_{F})=d_{F}$. As we are dealing with thin sets, we have $d_{F}\leq k$
for all $F\in\mathcal{F}$. For every $F\in\mathcal{F}$, we make $v_{F}$
adjacent to any $4k-d_{F}+1$ vertices of $D^{\square}$.

  4. 4.

For every row $i\in[k]$, create a vertex $r_{i}$ into $G$ and make $r_{i}$
adjacent to $w_{ij}$ for all $j\in[k]$. Let $R=\\{r_{1},\ldots,r_{k}\\}$. For
every $r\in R$, make $r$ adjacent to every vertex of $D^{\triangle}$ and any
$3k+1$ vertices of $D^{\square}$.

  5. 5.

For every column $j\in[k]$, create a vertex $c_{j}$ into $G$ and make $c_{j}$
adjacent to $w_{ij}$ for all $i\in[k]$. Let $C=\\{c_{1},\ldots,c_{k}\\}$. For
every $c\in C$, make $c$ adjacent to every vertex of $D^{\triangle}$ and any
$3k+1$ vertices of $D^{\square}$.

$r_{5}$$r_{4}$$r_{3}$$r_{2}$$r_{1}$$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$C$$R$$W$$v_{F_{1}}$$v_{F_{2}}$$v_{F_{3}}$$D^{\square}$$D^{\triangle}$
Figure 7: Example of the reduction in Theorem 4.1 applied to an instance
$(\mathcal{F}=\\{F_{1},F_{2},F_{3}\\},5)$ of $5\times 5$ Permutation Hitting
Set with Thin Sets that has three sets
$F_{1}=\\{(1,1),(2,1),(4,4),(5,3)\\},F_{2}=\\{(1,4),(3,4),(5,1)\\},F_{3}=\\{(1,1),(2,5),(3,2),(5,5)\\}$
with each set containing at most one element from each row.

This completes the construction of $G$. Set $r=5k$. We now formally argue that
instances $(\mathcal{F},k)$ and $(G,r)$ are equivalent. Assume first that $X$
is a solution to the instance $(\mathcal{F},k)$. For each $i\in[k]$, let
$j_{i}$ be the unique index such that $(i,j_{i})\in X$. We claim that the set

$S=D^{\triangle}\cup\\{w_{1j_{1}},w_{2j_{2}},\ldots,w_{kj_{k}}\\}$

is an offensive alliance of size exactly $5k$ in $G$. We see that $N(S)=R\cup
C\cup\\{v_{F}\leavevmode\nobreak\ :\leavevmode\nobreak\ F\in\mathcal{F}\\}$.
Let $v$ be an arbitrary element of $N(S)$. We need to prove that $d_{S}(v)\geq
d_{S^{c}}(v)+1$ for all $v\in N(S)$. If $v$ is an element of $R$ or $C$, the
neighbours of $v$ in $S$ are the elements of $D^{\triangle}$ and one element
from $W$. Thus we have $d_{S}(v)=4k+1$. The neighbours of $v$ in $S^{c}$ are
$3k+1$ elements of $D^{\square}$ and $k-1$ elements of $W$; therefore we have
$d_{S^{c}}(v)=4k$. If $v$ is an element of $\\{v_{F}\leavevmode\nobreak\
:\leavevmode\nobreak\ F\in\mathcal{F}\\}$, the neighbours of $v$ in $S$ are
the elements of $D^{\triangle}$ and at least one element from $W$ as $X$ is a
hitting set; thus we have $d_{S}(v)\geq 4k+1$. The neighbours of $v$ in
$S^{c}$ are $4k-d+1$ elements of $D^{\square}$ and at most $d-1$ elements from
$W$; thus we have $d_{S^{c}}(v)\leq(4k-d+1)+(d-1)=4k$. This shows that $S$ is
indeed an offensive alliance.

In the reverse direction, let $S$ be an offensive alliance of size at most
$5k$ in $G$. First we show that it can be assumed that $N(S)\cap
D^{\square}=\emptyset$. Suppose, for the sake of contradiction, that $v\in
N(S)\cap D^{\square}$. Then $v$ must satisfy the condition $d_{S}(v)\geq
d_{S^{c}}(v)+1$. As $v$ has degree at least $12k$, in order to satisfy the
condition $d_{S}(v)\geq d_{S^{c}}(v)+1$, the size of $S$ must be at least
$6k$, a contradiction to the assumption that the size of $S$ is at most $5k$.
Next we show that it can be assumed that $S\cap D^{\square}=\emptyset$.
Suppose that $S$ contains an element of $D^{\square}$. As $D^{\square}$ is a
clique and $D^{\square}\cap N(S)=\emptyset$, if $S$ contains one element of
$D^{\square}$ then $D^{\square}\subseteq S$. This is not possible as
$D^{\square}$ has $12k+1$ elements and $S$ has at most $5k$ elements.
Therefore, we may assume that $(S\cup N(S))\cap D^{\square}=\emptyset$. This
in turn implies that that $(R\cup C\cup V_{\mathcal{F}})\cap S=\emptyset$. As
the offensive alliance $S$ is non-empty, we have $S\cap
D^{\triangle}\neq\emptyset$ or $S\cap W\neq\emptyset$. Note that in either
case, we get $N(S)\cap(R\cup C\cup V_{\mathcal{F}})\neq\emptyset$. Let $u$ be
an arbitrary element of $N(S)\cap(R\cup C\cup V_{\mathcal{F}})$. If $S\cap
D^{\triangle}=\emptyset$ then clearly we have $d_{S}(u)<d_{S^{c}}(u)+1$ which
is not possible. Therefore $S\cap D^{\triangle}\neq\emptyset$. We observe that
if $S$ contains one element of $D^{\triangle}$ then it contains all elements
of $D^{\triangle}$, that is, $D^{\triangle}\subseteq S$. As
$D^{\triangle}\subseteq S$ and $(R\cup C\cup V_{\mathcal{F}})\cap
S=\emptyset$, we get $(R\cup C\cup V_{\mathcal{F}})\subseteq N(S)$. As $S$ is
an offensive alliance, every element $u$ of $N(S)$ has to satisfy the
condition $d_{S}(u)\geq d_{S^{c}}(u)+1$. Consider an arbitrary vertex $r_{i}$
of $R$. If $S\cap\\{w_{ij}\leavevmode\nobreak\ :\leavevmode\nobreak\
j\in[k]\\}=\emptyset$ then $d_{S}(r_{i})=4k$ and $d_{S^{c}}(r_{i})=4k$ which
is not possible as $r_{i}$ does not satisfy the condition $d_{S}(r_{i})\geq
d_{S^{c}}(r_{i})+1$. This implies that, for each $i\in[k]$, $S$ contains at
least one element from $\\{w_{ij}\leavevmode\nobreak\ :\leavevmode\nobreak\
j\in[k]\\}$ but since $|S|\leq 5k$ and $D^{\triangle}\subseteq S$, $S$
contains exactly one element from $\\{w_{ij}\leavevmode\nobreak\
:\leavevmode\nobreak\ j\in[k]\\}$. Using the same argument for an arbitrary
vertex $c_{j}\in C$, we get that $S$ contains exactly one element from
$\\{w_{ij}\leavevmode\nobreak\ :\leavevmode\nobreak\ i\in[k]\\}$. We claim
that $X=\\{(i,j)\leavevmode\nobreak\ |\leavevmode\nobreak\ w_{ij}\in S\\}$ is
a permutation hitting set of size $k$. Let us assume that there exists a set
$F\in\mathcal{F}$ which is not hit by $X$. In that case, we have
$d_{S}(v_{F})=4k$ and $d_{S^{c}}(v_{F})=(4k-d_{F})+d_{F}=4k$. This means that
$d_{S}(v_{F})<d_{S^{c}}(v_{F})+1$ which is a contradiction. Therefore, $X$ is
a hitting set of size $k$. As $X$ has exactly one element in each row and in
each column, $X$ is a permutation hitting set.

An algorithm solving Offensive Alliance in time $2^{o(k\log k)}$ would
therefore translate into an algorithm running in time $2^{o(k\log k)}$ for
$k\times k$ (Permutation) Hitting Set with Thin Sets and contradicts the ETH.
∎

######  Corollary 5.

Unless ETH fails, Exact Offensive Alliance problem cannot be solved in time
$\mathcal{O}^{*}(2^{o(k\log k)})$, where $k$ is the solution size.

##  5 No polynomial kernel parameterized by solution size and vertex cover

Parameterized by the solution size, the problem is FPT and in this section we
show the following kernelization hardness of Offensive Alliance.

######  Theorem 5.1.

Offensive Alliance parameterized by the solution size and vertex cover
combined does not admit a polynomial compression unless coNP $\subseteq$
NP/poly.

To prove Theorem 5.1, we give a polynomial parameter transformation (PPT) from
Closest String to Offensive Alliance parameterized by the solution size. In
the Closest string problem, we are given a set of $k$ strings
$\mathcal{X}=\\{x_{1},x_{2},\ldots,x_{k}\\}$, each string over an alphabet
$\Sigma$ and of length $n$, and an integer $d$. The objective is to check
whether there exists a string $y$ of length $n$ over $\Sigma$ such that
$d_{H}(y,x_{i})\leq d$ for all $i\in\\{1,2,\ldots,k\\}$. Here $d_{H}(x,y)$ is
the _Hamming distance_ between strings $x$ and $y$, that is, the number of
places where strings $x$ and $y$ differ. We call any such string $y$ a
_central string_. Let $x$ be a string over alphabet $\Sigma$. We denote the
letter on the $p$-th position of $x$ as $x[p]$. Thus $x=x[1]x[2]\ldots x[n]$
for a string of length $n$. We say string $x$ and $y$ _differ_ on the $p$-th
position if $x[p]\neq y[p]$. The following theorem is known:

######  Theorem 5.2.

[Basavaraju2018OnTK] $(d,n)$Closest String does not admit a polynomial kernel
unless NP $\subseteq$ coNP/poly.

They also observe that the kernelization lower bound for Closest String works
for any fixed alphabet $\Sigma$ of size at least two. Therefore, without loss
of generality, we assume that $\Sigma=\\{A_{1},A_{2}\\}$.

###  5.1 Proof of Theorem 5.1

We give a PPT from the Closest String problem. Given an instance
$(\mathcal{X},d)$ of the Closest String problem, we construct an instance
$(G,r)$ of Offensive Alliance the following way.

  1. 1.

For every $x\in\mathcal{X}$, we introduce a vertex $v_{x}$ into $G$. Let
$V_{\mathcal{X}}=\\{v_{x}\leavevmode\nobreak\ |\leavevmode\nobreak\
x\in\mathcal{X}\\}$. We also introduce a set of $2n$ vertices
$W=\\{w_{i,j}\leavevmode\nobreak\ :\leavevmode\nobreak\ i\in[n],j\in[2]\\}$.
Make $v_{x}$ adjacent to $w_{i1}$ if the letter on the $i$th position of $x$
is $A_{1}$; make $v_{x}$ adjacent to $w_{i2}$ if the letter on the $i$th
position of $x$ is $A_{2}$.

  2. 2.

We introduce a clique $D^{\triangle}$ of size $3n+2d+1$ into $G$. For every
$d\in D^{\triangle}$, we add a set $V_{d}$ of $12n$ vertices and make them
adjacent to $d$. For every $v_{x}\in V_{\mathcal{X}}$, we make $v_{x}$
adjacent to every vertex of $D^{\triangle}$.

  3. 3.

We introduce another clique $D^{\square}$ of size $12n+1$ into $G$. For every
$v_{x}\in V_{\mathcal{F}}$, we make $v_{x}$ adjacent to any $4n$ vertices of
$D^{\square}$.

  4. 4.

For every row $i\in[n]$, create a vertex $r_{i}$ into $G$ and make $r_{i}$
adjacent to $w_{i1}$ and $w_{i2}$. Let $R=\\{r_{1},\ldots,r_{n}\\}$. For every
$r\in R$, make $r$ adjacent to any three vertices of $D^{\triangle}$ and any
two vertices of $D^{\square}$.

$v_{x_{1}}$$v_{x_{2}}$$v_{x_{3}}$$D^{\square}$$D^{\triangle}$$d$$V_{d}$$V_{\mathcal{X}}$$R$$W$$3$$2$
Figure 8: Example of reduction of Theorem 5.1 applied to an instance
$(\chi,d)$ of Closest String where $\chi$ contains three strings
$x_{1}=1011100,x_{2}=1101010,x_{3}=1110001$ and $d=3$. A solution string
$y=1000000$ is shown in red circles.

This completes the construction of $G$. Note that the set $R\cup W\cup
D^{\square}\cup D^{\triangle}$ forms a vertex cover of $G$ of size $18n+2d+2$.
We set $r=4n+2d+1$. It is easy to see that the above construction takes
polynomial time. We now formally argue that instances $(\mathcal{X},d)$ and
$(G,r)$ are equivalent. Assume first that $y$ is a solution to the instance
$(\mathcal{X},d)$, that is, $d_{H}(x_{i},y)\leq d$ for all
$i\in\\{1,2,\ldots,k\\}$. We claim that

$S=D^{\triangle}\cup\Big{\\{}w_{ij}\leavevmode\nobreak\ |\leavevmode\nobreak\
y[i]=A_{j}\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
i=1,2,\ldots,n\Big{\\}}$

is an offensive alliance of size at most $r$. We see that $N(S)=R\cup
V_{\mathcal{X}}$. We need to prove that $d_{S}(v)\geq d_{S^{c}}(v)+1$ for
every $v\in R\cup V_{\mathcal{X}}$. If $r$ is an element of $R$, the
neighbours of $r$ in $S$ are three elements of $D^{\triangle}$ and one element
from $W$. Thus we have $d_{S}(r)=4$. The neighbours of $r$ in $S^{c}$ are two
elements of $D^{\square}$ and one elements of $W$; therefore we have
$d_{S^{c}}(r)=3$ and $r$ satisfies the required condition. If $v_{x}$ is an
element of $V_{\mathcal{X}}$, the neighbours of $v_{x}$ in $S$ are $3n+2d+1$
elements of $D^{\triangle}$ and $n-d_{H}(x,y)$ element from $W$. Thus we have
$d_{S}(v_{x})\geq(3n+2d+1)+(n-d)=4n+d+1$. The neighbours of $v_{x}$ in $S^{c}$
are $4n$ elements of $D^{\square}$ and $d_{H}(x,y)$ element from $W$; hence
$d_{S^{c}}(v_{x})=4n+d_{H}(x,y)\leq 4n+d$. Therefore $v_{x}$ satisfies the
required condition.

In the reverse direction, let $S$ be an offensive alliance of size at most
$4n+2d+1$ in $G$. First we show that it can be assumed that $N(S)\cap
D^{\square}=\emptyset$. Suppose, for the sake of contradiction, that $v\in
N(S)\cap D^{\square}$. Then $v$ must satisfy the condition $d_{S}(v)\geq
d_{S^{c}}(v)+1$. As $v$ has degree at least $12k$, in order to satisfy the
condition $d_{S}(v)\geq d_{S^{c}}(v)+1$, the size of $S$ must be at least
$6k$, a contradiction to the assumption that the size of $S$ is at most
$4n+2d+1$. Next we show that it can be assumed that $S\cap
D^{\square}=\emptyset$. Suppose that $S$ contains an element of $D^{\square}$.
As $D^{\square}$ is a clique and $D^{\square}\cap N(S)=\emptyset$, if $S$
contains one element of $D^{\square}$ then $D^{\square}\subseteq S$. This is
not possible as $D^{\square}$ has $12n+1$ elements and $S$ has at most
$4n+2d+1$ elements. Therefore, we may assume that $(S\cup N(S))\cap
D^{\square}=\emptyset$. This in turn implies that $S$ does not contain any
element from $V_{\mathcal{X}}\cup R$. As the offensive alliance $S$ is non-
empty, we have $S\cap D^{\triangle}\neq\emptyset$ or $S\cap W\neq\emptyset$.
Note that in either case, we get $N(S)\cap(R\cup
V_{\mathcal{X}})\neq\emptyset$. Let $u$ be an arbitrary element of
$N(S)\cap(R\cup V_{\mathcal{X}})$. If $S\cap D^{\triangle}=\emptyset$ then
clearly we have $d_{S}(u)<d_{S^{c}}(u)+1$ which is not possible. Therefore
$S\cap D^{\triangle}\neq\emptyset$. We observe that if $S$ contains one
element of $D^{\triangle}$ then it contains all elements of $D^{\triangle}$,
that is, $D^{\triangle}\subseteq S$. As $D^{\triangle}\subseteq S$ and $(R\cup
V_{\mathcal{X}})\cap S=\emptyset$, we get $(R\cup V_{\mathcal{X}})\subseteq
N(S)$. As $S$ is an offensive alliance, every element $u$ of $N(S)$ has to
satisfy the condition $d_{S}(u)\geq d_{S^{c}}(u)+1$. Consider an arbitrary
vertex $r_{i}$ of $R$. If $S\cap\\{w_{i1},w_{i2}\\}=\emptyset$ then
$d_{S}(r_{i})=3$ and $d_{S^{c}}(r_{i})=4$ which is not possible as $r_{i}$
does not satisfy the condition $d_{S}(r_{i})\geq d_{S^{c}}(r_{i})+1$. This
implies that, for each $i\in[n]$, $S$ contains at least one element from
$\\{w_{i1},w_{i2}\\}$. Since $|S|\leq 4n+2d+1$ and $D^{\triangle}\subseteq S$,
$S$ contains exactly one element from $\\{w_{i1},w_{i2}\\}$ for each $i$.
Define a string $y=y[1]y[2]\ldots y[n]$, where $y[i]=1$ if $w_{i1}\in S$ and
$y[i]=2$ if $w_{i2}\in S$. We claim $y$ is a central string. Assume, for the
sake of contradiction, that there exists a string $x_{i}$ such that
$d_{H}(x_{i},y)>d$. In this case, we see that
$d_{S}(v_{x_{i}})<(3n+2d+1)+n-d\leq 4n+d$ and $d_{S^{c}}(v_{x_{i}})>4n+d$.
Therefore, $d_{S}(v_{x_{i}})<d_{S^{c}}(v_{x_{i}})+1$, which is a
contradiction. ∎

##  6 Faster FPT algorithms parameterized by vertex cover number

We know that both Offensive Alliance and Strong Offensive Alliance admit FPT
algorithms [KIYOMI201791] when parameterized by the vertex cover number of the
input graph. The algorithms in [KIYOMI201791] use Integer Linear Programming,
and thus their dependency on the parameter may be gigantic. The reason is
this. The Offensive Alliance problem is mapped to an ILP with at most
$2^{\tt{vc(G)}}$ many variables where $\tt{vc(G)}$ is the vertex cover number
of the input graph. It is proved in [fellows] that $p$-Variable Integer Linear
Programming Optimization ($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$. Thus the algorithm in [KIYOMI201791] requires
$\mathcal{O}^{*}({(2^{\tt{vc(G)}})}^{\mathcal{O}(2^{\tt{vc(G)})}})$ time. The
natural question would be whether they admit
$\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)}})$ time algorithm. We
answer this question with the following theorem.

######  Theorem 6.1.

Offensive Alliance can be solved in time
$\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)}})$ where $\tt{vc(G)}$ is
the vertex cover number of the input graph $G$.

###### Proof.

Let $C$ be a vertex cover of $G$ of size vc(G). Note that $C$ forms an
offensive alliance. This is because $N(C)$ is an independent set and every
vertex of $N(C)$ has no neighbours in $C^{c}$ and has at least one neighbour
in $C$. Therefore we have $d_{C}(v)\geq d_{C^{c}}(v)+1$ for all $v\in N(C)$,
and hence $C$ is an offensive alliance. This implies that the size of minimum
offensive alliance is at most $\tt{vc(G)}$. In [DA-FPT], it was proved using
branching technique that Offensive Alliance problem parameterized by solution
size admits a $\mathcal{O}(n^{2}k(2k)^{k-1})$. This implies that, we have an
algorithm with running time $\mathcal{O}^{*}(\tt{vc(G)})^{\tt{vc(G)}}$. ∎

The arguments in the proof of Theorem 6.1 is also applicable to Strong
Offensive Alliance as long as the input graph $G$ has minimum degree at least
two. As a direct consequence of Theorem 6.1, we have the following corollary.

######  Corollary 6.

Strong Offensive Alliance can be solved in time
$\mathcal{O}^{*}(\tt{vc(G)}^{\mathcal{O}(\tt{vc(G)}})$ where $\tt{vc(G)}$ is
the vertex cover number of the input graph $G$ with $\delta(G)\geq 2$.

##  7 Classical lower bounds under ETH

In this section, we prove lower bound based on ETH for the time needed to
solve the Offensive Alliance problem. In order to prove that a too fast
algorithm for Offensive Alliance contradicts ETH, we give a reduction from
Vertex Cover in graphs of maximum degree 3 and argue that a too fast algorithm
for Offensive Alliance would solve Vertex Cover in graphs of maximum degree 3
in time $2^{o(n)}$. Johnson and Szegedy [soda1999] proved that, assuming ETH,
there is no algorithm with running time $2^{o(n)}$ to compute a minimum vertex
cover in graphs of maximum degree 3.

######  Theorem 7.1.

Unless ETH fails, Offensive Alliance does not admit a $2^{o(n)}$ algorithm,
even when restricted to bipartite graphs.

###### Proof.

We give a linear reduction from Vertex Cover in graphs of maximum degree 3 to
Offensive Alliance, that is, a polynomial-time algorithm that takes an
instance of Vertex Cover and outputs an equivalent instance of Offensive
Alliance whose size is bounded by $O(n)$. Let $(G,k)$ be an instance of Vertex
Cover, where $G=(V,E)$ has maximum degree 3. We construct an equivalent
instance $(G^{\prime},k^{\prime})$ of Offensive Alliance the following way.
See Figure 9 for an illustration.

${E_{0}}$${V_{0}}$${V_{1}}$${v_{1}}$${v_{2}}$${v_{3}}$${v^{0}_{1}}$${v^{0}_{2}}$${v^{0}_{3}}$${v^{1}_{1}}$${v^{1}_{2}}$${v^{1}_{3}}$$e_{1}$$e_{2}$$e_{3}$$a$$e$$b$$d$$c$${V_{a}}$${V_{b}}$${V_{c}}$${V_{d}}$${V_{e}}$$G^{\prime}$$G$$e_{1}$$e_{2}$$e_{3}$
Figure 9: An illustration of the reduction from Vertex Cover to Offensive
Alliance in Theorem 7.1.

Take two distinct copies $V_{0},V_{1}$ of $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$,
and let $v^{i}$ be the copy of $v\in V$ in $V_{i}$. We introduce the vertex
set $E_{0}$ into $G^{\prime}$, where $E_{0}=\\{e_{1},\ldots,e_{m}\\}$, the
edge set of $G$. We make $v^{0}_{i}$ adjacent to $e_{j}$ if and only if
$v_{i}$ is an endpoint of $e_{j}$ in $G$. We make $v^{0}_{i}$ adjacent to
$v^{1}_{i}$ for all $i$. Next, introduce five new vertices $a,b,c,d,e$. For
each $x\in\\{a,b,c,d,e\\}$, introduce a set $V_{x}$ of $4k^{\prime}$ vertices
and make $x$ adjacent to every vertex of $V_{x}$. Moreover, we make vertex $a$
and $e$ adjacent to every vertex of $E_{0}$ and make $b$ and $c$ adjacent to
every vertex of $V_{1}$. We also make $d$ adjacent to every vertex of
$\\{a,b,c,e\\}$. Note that $G^{\prime}$ is a bipartite graph with bipartition
$\\{d\\}\cup V_{1}\cup E_{0}\bigcup\limits_{x\in\\{a,b,c\\}}{V_{x}}$ and
$\\{a,b,c,e\\}\cup V_{d}\cup V_{0}$. We set $k^{\prime}=k+5$. Clearly, the
size of $G^{\prime}$ is bounded by $O(n)$.

We claim that $(G,k)$ is a yes-instance of Vertex Cover if and only if
$(G^{\prime},k^{\prime})$ is a yes-instance of Offensive Alliance. Suppose $G$
has a vertex cover $S$ of size at most $k$. We show that $D=\\{v^{0}\in
V_{0}\leavevmode\nobreak\ |\leavevmode\nobreak\ v\in S\\}\cup\\{a,b,c,d,e\\}$
is an offensive alliance of size at most $k^{\prime}$ in $G^{\prime}$. We see
$N(D)=E_{0}\cup V_{1}\bigcup\limits_{x\in\\{a,b,c,d\\}}{V_{x}}$. It is clear
that for each $v\in V_{1}\bigcup\limits_{x\in\\{a,b,c,d\\}}{V_{x}}$, we have
$d_{D}(v)\geq d_{D^{c}}(v)+1$. Each $v\in E_{0}$ has at least three neighbours
in $D$, more precisely, $a$, $e$ and at least one neighbour in $V_{0}$. This
implies that for each $v\in E_{0}$, we have $d_{D}(v)\geq d_{D^{c}}(v)+1$.

Conversely, assume that $G^{\prime}$ admits an offensive alliance $D$ of size
at most $k^{\prime}=k+5$. Note that the vertices $a,b,c,d$ and $e$ cannot be
part of the set $N(D)$ as each of them has degree $4k^{\prime}$; otherwise the
size of $D$ will exceed $k^{\prime}$. We now show that
$\\{a,b,c,d,e\\}\subseteq D$. By definition, offensive alliance cannot be
empty; therefore it must contain a vertex from $V(G^{\prime})$.

######  Case 1.

Suppose $D$ contains an arbitrary vertex of
$\bigcup\limits_{x\in\\{a,b,c,d,e\\}}{V_{x}}$. Without loss of generality,
assume that $D$ contains an arbitrary vertex of $V_{a}$. Since $a\not\in
N(D)$, it implies that $a\in D$. Since $a\in D$, we get $b,c,d$ and $e$ also
lie in $D$ as otherwise $\\{b,c,d,e\\}\subseteq N(D)$. Therefore, if any
vertex from the set $\\{a,b,c,d,e\\}$ is in $D$, it implies that the whole set
is in $D$.