11institutetext: Indian Institute of Science Education and Research
Dr. Homi Bhabha Road, Pune 411008, INDIA 11email:
<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
# Defensive 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/00125.

###### Abstract

A set $S$ of vertices of a graph is a defensive alliance if, for each element
of $S$, the majority of its neighbours are in $S$. We study the parameterzied
complexity of the Defensive Alliance problem, where the aim is to find a
minimum size defensive alliance. Our main results are the following: (1) The
Defensive Alliance problem has been studied extensively during the last twenty
years, but the question whether it is FPT when parameterized by feedback
vertex set has still remained open. We prove that 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; (2) the problem parameterized by the vertex cover number of the
input graph does not admit a polynomial compression unless coNP $\subseteq$
NP/poly, (3) it does not admit $2^{o(n)}$ algorithm under ETH, and (4) the
Defensive Alliance problem on circle graphs is NP-complete.

###### Keywords:

Defensive alliance Parameterized Complexity FPT W[1]-hard treedepth feedback
vertex set ETH circle graph

##  1 Introduction

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 [19]. 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 fifteen years [10, 24, 3, 22, 25], and generalizations called
$r$-alliances are also studied [23]. 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=(V,E)$ if
$d_{S}(v)+1\geq d_{S^{c}}(v)$ for all $v\in S$.

A vertex $v\in S$ is said to be protected if $d_{S}(v)+1\geq d_{S^{c}}(v)$. A
set $S\subseteq V$ is a defensive alliance if every vertex in $S$ is
protected. In this paper, we consider Defensive Alliance under structural
parameters. We define the problem as follows:
Defensive Alliance
Input: An undirected graph $G=(V,E)$ and an integer $k\geq 1$. Question: Is
there a defensive alliance $S\subseteq V(G)$ such that $|S|\leq k$?

For standard notations and definitions in graph theory and parameterized
complexity, we refer to West [26] and Cygan et al. [4], respectively. The
graph parameters we explicitly use in this paper are feedback vertex set
number, pathwidth, treewidth and treedepth.

######  Definition 2.

For a graph $G=(V,E)$, the parameter feedback vertex set is the cardinality of
the 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 [21]. Treewidth is a measure of how “tree-like” the graph is.

######  Definition 3.

[5] 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 $(u,v)\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 4.

[5] 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 $tw(G)$ of a graph $G$ is the minimum width among all possible tree
decomposition of $G$.

######  Definition 5.

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 6.

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)$.

###  1.1 Our Main Results

Our main results are as follows:

  * •

the Defensive Alliance is W[1]-hard when parameterized by the the vertex
deletion set into trees of height at most two, even when restricted to
bipartite graphs.

  * •

the Defensive Alliance problem parameterized by the vertex cover number of the
input graph does not admit a polynomial compression unless coNP $\subseteq$
NP/poly.

  * •

the Defensive Alliance problem does not admit $2^{o(n)}$ algorithm under ETH.

  * •

the Defensive Alliance problem on circle graphs is NP-complete.

###  1.2 Known Results

The decision version for several types of alliances have been shown to be NP-
complete. For an integer $r$, a nonempty set $S\subseteq V(G)$ is a defensive
$r$-alliance if for each $v\in S$, $|N(v)\cap S|\geq|N(v)\setminus S|+r$. A
set is a defensive alliance if it is a defensive $(-1)$-alliance. A defensive
$r$-alliance $S$ is global if $S$ is a dominating set. The defensive
$r$-alliance problem is NP-complete for any $r$ [23]. The defensive alliance
problem is NP-complete even when restricted to split, chordal and bipartite
graph [14]. For an integer $r$, a nonempty set $S\subseteq V(G)$ is an
offensive $r$-alliance if for each $v\in N(S)$, $|N(v)\cap
S|\geq|N(v)\setminus S|+r$. An offensive 1-alliance is called an offensive
alliance. An offensive $r$-alliance $S$ is global if $S$ is a dominating set.
Fernau et al. showed that the offensive $r$-alliance and global offensive
$r$-alliance problems are NP-complete for any fixed $r$ [8]. They also proved
that for $r>1$, $r$-offensive alliance is NP-hard, even when restricted to
$r$-regular planar graphs. There are polynomial time algorithms for finding
minimum alliances in trees [2, 14]. A polynomial time algorithm for finding
minimum defensive alliance in series parallel graph is presented in [13].
Fernau and Raible showed in [7] that the defensive, offensive and powerful
alliance problems and their global variants are fixed parameter tractable when
parameterized by solution size $k$. Kiyomi and Otachi showed in [17], 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 [11]. Enciso [6]
proved that finding defensive and global defensive alliances is fixed
parameter tractable when parameterized by domino treewidth. Bliem and Woltran
[1] proved that deciding if a graph contains a defensive alliance of size at
most $k$ 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]).

##  2 Hardness Results of Defensive Alliance

In this section we show that the Defensive Alliance problem is W[1]-hard when
parameterized by the size of a vertex deletion set into trees of height at
most 2, even when restricted to bipartite graphs, via a reduction from the
Multidimensional Relaxed Subset Sum (MRSS) 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$?

We consider a variant of MSS that we require in our proofs. 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$. This variant can be
formalized as follows:

Multidimensional Relaxed Subset Sum (MRSS)
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$, a target vector
$t\in\mathbb{N}^{k}$ and an integer $k^{\prime}$. 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$?

It is known that 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
[12]. We now show that the Defensive Alliance problem is W[1]-hard
parameterized by the size of a vertex deletion set into trees of height at
most 2, via a reduction from MRSS. We now prove the following theorem:

######  Theorem 2.1.

The Defensive Alliance problem is W[1]-hard when parameterized by the size of
a vertex deletion set into trees of height at most 2, even when restricted to
bipartite graphs.

###### Proof.

Let $I=(k,k^{\prime},S,t)$ be an instance of MRSS. From this we construct an
instance $I^{\prime}=(G,r)$ of Defensive Alliance the following way. See
Figure 1 for an illustration.

$u_{1}$$u_{2}$$f_{1}$$f_{2}$$f_{3}$$V_{u_{1}}^{\square}$$V_{f_{3}}^{\square}$$x_{s_{1}}$$A_{s_{1}}$$y_{s_{1}}$$B_{s_{1}}$$x_{s_{2}}$$A_{s_{2}}$$y_{s_{2}}$$B_{s_{2}}$$x_{s_{3}}$$A_{s_{3}}$$y_{s_{3}}$$B_{s_{3}}$$H_{u_{1}u_{2}}$$h^{0}_{u_{1}u_{2}}$$V_{u_{1}u_{2}}^{\square}$$H_{u_{2}f_{1}}$$h^{0}_{u_{2}f_{1}}$$H_{f_{1}f_{2}}$$h^{0}_{f_{1}f_{2}}$$H_{f_{2}f_{3}}$$h^{0}_{f_{2}f_{3}}$$H_{f_{3}u_{1}}$$h^{0}_{f_{3}u_{1}}$$V_{f_{3}u_{1}}^{\square}$$h_{1}^{\square}$$h_{2}^{\square}$$h_{3}^{\square}$$a_{1}^{\square}$$a_{2}^{\square}$$a_{3}^{\square}$$a_{4}^{\square}$$a_{5}^{\square}$$a_{6}^{\square}$$a_{7}^{\square}$
Figure 1: The graph $G$ in the proof of Theorem 2.1 constructed for MRSS
instance $S=\\{(2,1),(1,1),(1,2)\\}$, $t=(3,3)$, $k=2$ and $k^{\prime}=2$. The
vertices $t$ and $t^{\prime}$, and their adjacency are not shown. Every square
vertex is adjacent to $2r+2$ vertices which are also not shown in the diagram.

Let $s=(s(1),s(2),\ldots,s(k))\in S$ and let $\text{max}(s)$ denote the value
of the largest coordinate of $s$. We set $N=\sum\limits_{s\in
S}(2\text{max}(s)+2)$. First we introduce a set of $k$ new vertices
$U=\\{u_{1},u_{2},\ldots,u_{k}\\}$. For every $u_{i}\in U$, we introduce a set
$V_{u_{i}}^{\square}$ of $\sum\limits_{s\in S}{s(i)}+2N-2(\sum\limits_{s\in
S}{s(i)}-t(i))$ square vertices and make $u_{i}$ adjacent to every vertex of
$V_{u_{i}}^{\square}$. We also introduce a set $F=\\{f_{1},f_{2},f_{3}\\}$ of
three new vertices and make each $f\in F$ adjacent to a set $V_{f}^{\square}$
of $2N$ square vertices. We consider the vertices of $U$ and $F$ in the
following order: $u_{1},u_{2},\ldots,u_{k},f_{1},f_{2},f_{3},u_{1}$. Let

$P=\\{(u_{1},u_{2}),\ldots,(u_{k-1},u_{k}),(u_{k},f_{1}),(f_{1},f_{2}),(f_{2},f_{3}),(f_{3},u_{1})\\}$

be the set of pairs of consecutive vertices. For each pair $(x,y)\in P$, we
add a set $H_{xy}=\\{h^{1}_{xy},\ldots,h^{N}_{xy}\\}$ of $N$ new vertices and
add a special vertex $h^{0}_{xy}$ which is adjacent to all the vertices of
$H_{xy}$; $h^{0}_{xy}$ is also adjacent to a set $V_{xy}^{\square}$ of $N$ new
square vertices. Finally, we introduce a set
$H^{\square}=\\{h_{1}^{\square},h_{2}^{\square},h_{3}^{\square}\\}$ of three
new square vertices and for each pair $(x,y)\in P$, make vertices of $H_{xy}$
adjacent to square vertices of $H^{\square}$.

Recall that a star $S_{k}$ is the complete bipartite graph $K_{1,k}$: a tree
with one internal node and $k$ leaves. For each vector $s\in S$, we introduce
two stars $S^{1}_{\mbox{max}(s)+1}$ and $S^{2}_{\mbox{max}(s)+1}$. The first
star has internal node $x_{s}$ and $\mbox{max}(s)+1$ leaves
$A_{s}=\\{a_{1}^{s},\ldots,a_{\text{max}(s)+1}^{s}\\}$; the second star has
internal node $y_{s}$ and $\mbox{max}(s)+1$ leaves
$B_{s}=\\{b_{1}^{s},\ldots,b_{\text{max}(s)+1}^{s}\\}$. 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 an arbitrary manner. We make the
three vertices $f_{1},f_{2},f_{3}$ from the set $F$ adjacent to all vertices
of $\bigcup\limits_{s\in S}{A_{s}\cup B_{s}}$.

Finally we add a set
$V_{a}^{\square}=\\{a_{1}^{\square},\ldots,a_{k+5}^{\square}\\}$ of $k+5$
square vertices. We make each vertex in $A_{s}$ adjacent to exactly
$|N_{U}(a^{s})|+5$ many vertices of $V_{a}^{\square}$ arbitrarily. We define
the set of square vertices as $V_{\square}={V_{a}^{\square}}\cup
H^{\square}\bigcup\limits_{(x,y)\in P}V_{xy}^{\square}\bigcup\limits_{u\in
U}V_{u}^{\square}\bigcup\limits_{f\in F}V_{f}^{\square}$ and we also define
$V_{\triangle}=U\cup F\bigcup\limits_{(x,y)\in P}H_{xy}\cup\\{h^{0}_{xy}\\}$.
We set $r=(k+3)N+2k+6+\sum\limits_{i=1}^{n}(\text{max}(s_{i})+1)+k^{\prime}$.
For every vertex $x\in V_{\square}$, we introduce a set
$V_{x}=\\{x_{1},x_{2},\dots,x_{2r+2}\\}$ of $2r+2$ many vertices adjacent to
$x$. We also add two vertices $t$ and $t^{\prime}$. The vertex $t$ is adjacent
to all the vertices in $\bigcup\\{V_{x}\leavevmode\nobreak\
|\leavevmode\nobreak\ x\in\bigcup\limits_{(x,y)\in
P}V_{xy}^{\square}\bigcup\limits_{u\in U}V_{u}^{\square}\bigcup\limits_{f\in
F}V_{f}^{\square}\\}$. Similarly, the vertex $t^{\prime}$ is adjacent to all
the vertices in $\bigcup\\{V_{x}\leavevmode\nobreak\ |\leavevmode\nobreak\
x\in{V_{a}^{\square}}\cup H^{\square}\\}$. This completes the construction of
graph $G$. The strategy is to force all the square vertices outside the
solution and all the vertices in $V_{\triangle}$ inside the solution. Observe
that if we remove the set $U\cup F\cup H^{\square}\cup
V_{a}^{\square}\cup\\{h^{0}_{xy}\leavevmode\nobreak\ |\leavevmode\nobreak\
(x,y)\in P\\}\bigcup\\{t,t^{\prime}\\}$ of $3k+16$ vertices from $G$ then we
are left with only star graphs. It is easy to see that $G$ is a bipartite
graph with bipartition

$V_{1}=H^{\square}\cup V_{a}^{\square}\cup U\cup
F\cup\\{t^{\prime}\\}\bigcup\limits_{x\in V_{\square}\setminus(H^{\square}\cup
V_{a}^{\square})}V_{x}\bigcup\limits_{(x,y)\in
P}\\{h^{0}_{xy}\\}\bigcup\limits_{s\in S}\\{x_{s},y_{s}\\}$

and

$V_{2}=\\{t\\}\bigcup\limits_{(x,y)\in P}(V_{xy}^{\square}\cup
H_{xy})\bigcup\limits_{u\in U}V_{u}^{\square}\bigcup\limits_{f\in
F}V_{f}^{\square}\bigcup\limits_{x\in H^{\square}\cup
V_{a}^{\square}}V_{x}\bigcup\limits_{s\in S}(A_{s}\cup B_{s}).$

We claim that $I=(k,k^{\prime},S,t)$ is a positive instance of MRSS if and
only if $I^{\prime}=(G,r)$ is a positive instance of Defensive Alliance. Let
$S^{\prime}\subseteq S$ be such that $|S^{\prime}|\leq k^{\prime}$ and
$\sum\limits_{s\in S^{\prime}}{s}\geq t$. We claim that the set

$\displaystyle R=$ $\displaystyle U\cup F\bigcup\limits_{(x,y)\in
P}H_{xy}\cup\\{h^{0}_{xy}\\}\bigcup\limits_{s\in
S^{\prime}}A_{s}\cup\\{x_{s}\\}\bigcup\limits_{s\in S\setminus
S^{\prime}}B_{s}$

is a defensive alliance in $G$ such that $|R|\leq r$. Let $x$ be an arbitrary
element of $R$.
Case 1: If $x=u_{i}\in U$, then

$d_{R}(u_{i})=\sum\limits_{s\in S^{\prime}}s(i)+2N$

and

$d_{R^{c}}(u_{i})=\sum\limits_{s\in S\backslash
S^{\prime}}s(i)+|V_{u_{i}}^{\square}|=\sum\limits_{s\in S\backslash
S^{\prime}}s(i)+\sum\limits_{s\in S}s(i)+2N-2(\sum\limits_{s\in S}s(i)-t(i))$

$\begin{split}d_{R^{c}}(u_{i})&=2N+\sum\limits_{s\in S\backslash
S^{\prime}}s(i)+\sum\limits_{s\in S}s(i)-2(\sum\limits_{s\in S}s(i)-t(i))\\\
&=2N-\Big{(}\sum\limits_{s\in S}s(i)-\sum\limits_{s\in S\backslash
S^{\prime}}s(i)\Big{)}+2t(i)\\\ &=2N-\sum\limits_{s\in
S^{\prime}}s(i)+2t(i)\\\ &=2N+\sum\limits_{s\in
S^{\prime}}s(i)+2\Big{(}t(i)-\sum\limits_{s\in S^{\prime}}s(i)\Big{)}\\\ &\leq
2N+\sum\limits_{s\in S^{\prime}}s(i)\\\ &=d_{R}(u_{i})\end{split}$

Therefore, we have $d_{R}(u_{i})+1\geq d_{R^{c}}(u_{i})$, and hence $u_{i}$ is
protected.

Case 2: If $x=a^{s}\in A_{s}$, then
$d_{R}(a^{s})=|N_{U}(a^{s})|+|\\{f_{1},f_{2},f_{3},x_{s}\\}|=|N_{U}(a^{s})|+4$
and $d_{R^{c}}(a^{s})=|N_{U}(a^{s})|+5$. Therefore, we get $d_{R}(a^{s})+1\geq
d_{R^{c}}(a^{s})$.

Case 3: If $x=f_{1}\in F$, then $N_{R}(f_{1})=\bigcup\limits_{s\in
S^{\prime}}A_{s}\bigcup\limits_{s\in S\backslash S^{\prime}}B_{s}\cup
H_{u_{2}f_{1}}\cup H_{f_{1}f_{2}}$ and $N_{R^{c}}(a)=\bigcup\limits_{s\in
S^{\prime}}B_{s}\bigcup\limits_{s\in S\backslash S^{\prime}}A_{s}\cup
V_{f_{1}}^{\square}$. As $|A_{s}|=|B_{s}|$,
$|H_{u_{2}f_{1}}|=|H_{f_{1}f_{2}}|=N$ and $|V_{f_{1}}^{\square}|=2N+1$, we
have $d_{R}(f_{1})+1\geq d_{R^{c}}(f_{1})$. We can similarly check that
$\\{f_{2},f_{2}\\}$ are also protected.

For the rest of the vertices in $R$, it is easy to see that $d_{R}(x)+1\geq
d_{R^{c}}(x)$. Therefore, $I^{\prime}=(G,r)$ is a yes instance.

For the reverse direction, suppose that $G$ has a defensive alliance $R$ of
size at most $r$. It is easy to see that
$(V_{\square}\cup\\{t,t^{\prime}\\})\cap R=\emptyset$ as any defensive
alliance of size at most $r$ cannot contain vertices of degree greater than
$2r$. This also shows that $\bigcup\limits_{x\in V_{\square}}{V_{x}\cap
R=\emptyset}$. Now we show that $V_{\triangle}=U\cup F\bigcup\limits_{(x,y)\in
P}H_{xy}\cup\\{h^{0}_{xy}\\}\subseteq R$. We claim that if $V_{\triangle}\cap
R\neq\emptyset$ then $V_{\triangle}\subseteq R$.

Case 1: Suppose $R$ contains $u_{1}$ from $U$. We observe that if some
$h_{u_{1}u_{2}}\in H_{u_{1}u_{2}}$ is not in $R$ then $h^{0}_{u_{1}u_{2}}$ is
also not in $R$. This implies that no vertex from $H_{u_{1}u_{2}}$ is in $R$.
In this case $N_{R^{c}}(u_{1})\geq 3N+2t(i)-\sum\limits_{s\in S}s(i)$ and
$N_{R}(u_{1})\leq N+\sum\limits_{i=1}^{n}(\text{max}(s_{i})+2)$. This implies
that $u_{1}$ is not protected in $R$ which is a contradiction as $u_{1}\in R$.
This implies that $H_{u_{1}u_{2}}\cup\\{h^{0}_{u_{1}u_{2}}\\}\subseteq R$.
Applying the same argument for $h_{f_{3},u_{1}}\in H_{f_{3}u_{1}}$, we see
that $H_{f_{3}u_{1}}\cup\\{h^{0}_{f_{3}u_{1}}\\}\subseteq R$. Clearly, this
shows that $f_{3}$ and $u_{2}$ are in $R$ for protection of vertices in
$H_{u_{1}u_{2}}\cup H_{f_{3}u_{1}}$. Applying the same argument for $u_{2}$
and $f_{3}$, we get $H_{u_{2}u_{3}}\cup\\{h^{0}_{u_{2}u_{3}}\\}\subseteq R$
and $H_{f_{3}u_{1}}\cup\\{h^{0}_{f_{3}u_{1}}\\}\subseteq R$, respectively.
Repeatedly applying the above argument, we get $V_{\triangle}\subseteq R$.
Observe that this argument can be easily extended to all the vertices of $U$
and $F$. Therefore, we see that if $(U\cup F)\cap R\neq\emptyset$, then
$V_{\triangle}\subseteq R$.

Case 2: Suppose $R$ contains $h_{xy}$ from $H_{xy}$ for some $(x,y)\in P$.
Clearly, this implies $R$ contains both $x$ and $y$ from $U\cup F$. Using Case
1, we get $V_{\triangle}\subseteq R$.

Case 3: Suppose $R$ contains $h^{0}_{xy}$ for some $(x,y)\in P$. Clearly, this
implies that $H_{xy}\subseteq R$. Using Case 2, we get $V_{\triangle}\subseteq
R$.

Therefore we proved that if $V_{\triangle}\cap R\neq\emptyset$ then
$V_{\triangle}\subseteq R$. Next we claim that if $R$ is non-empty then $R$
contains the set $V_{\triangle}$. Since $R$ is non-empty, we see that $R$ must
contain a vertex from graph $G$. We consider the following cases:

Case 1: Suppose $R$ contains $a^{s}$ from $A_{s}$ for some $s\in S$. Then we
know that $d_{R^{c}}(a^{s})\geq|N_{U}(a^{s})|+5$. We see that $a^{s}$ is
protected if and only if $F\cap R\neq\emptyset$. This implies that
$V_{\triangle}\cap R\neq\emptyset$ which implies $V_{\triangle}\subseteq R$.

Case 2: Suppose $R$ contains $x_{s}$ for some $s\in S$. We know that $x_{s}$
has at least two neighbours in $A_{s}$ as $\text{max}(s)+1\geq 2$. This
implies that $x_{s}$ is protected if and only if at least one vertex $a_{s}\in
A_{s}$ is in $R$. Now, Case 1 implies that $V_{\triangle}\subseteq R$.

Case 3: Suppose $R$ contains $b^{s}\in B_{s}$ for some $s\in S$. Then we know
that $N(b^{s})=\\{y_{s}\\}\cup F$. Clearly, the protection of $b^{s}$ requires
at least one vertex from $F$. This implies that $F\cap R\neq\emptyset$.
Therefore, we have $V_{\triangle}\cap R\neq\emptyset$ and hence
$V_{\triangle}\subseteq R$.

Case 4: Suppose $R$ contains $y_{s}$ for some $s\in S$. We know that $y_{s}$
has at least two neighbours in $B_{s}$ as $\text{max}(s)+1\geq 2$. This
implies that $y_{s}$ is protected if and only if at least one vertex $b_{s}\in
B_{s}$ is in $R$. Now, Case 3 implies that $V_{\triangle}\subseteq R$.

This shows if $R$ is non-empty then $V_{\triangle}\subseteq R$. We know
$V_{\triangle}$ contains exactly $(k+3)N+2k+6$ many vertices; thus besides the
vertices of $V_{\triangle}$, there are at most
$\sum\limits_{i=1}^{n}(\text{max}(s_{i})+1)+k^{\prime}$ vertices in $R$. Since
$f_{1}\in R$ and $d_{V_{\triangle}}(f_{1})=d_{V_{\square}}(f_{1})=2N$, it must
have at least $\sum\limits_{i=1}^{n}(\text{max}(s_{i})+1)$ many neighbours in
$R$ from the set $\bigcup\limits_{s\in S}A_{s}\cup B_{s}$. We also observe
that if a vertex $a^{s}$ from the set $A_{s}$ is in the solution then $x_{s}$
also lie in the solution for the protection of $a^{s}$. This shows that at
most $k^{\prime}$ many sets of the form $A_{s}$ contribute to the solution as
otherwise the size of solution exceeds $r$. Therefore, any arbitrary defensive
alliance $R$ of size at most $r$ can be transformed to another defensive
alliance $R^{\prime}$ of size at most $r$ as follows:

$R^{\prime}=V_{\triangle}\bigcup\limits_{x_{s}\in
R}A_{s}\cup\\{x_{s}\\}\bigcup\limits_{x_{s}\in V(G)\setminus R}B_{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\\}$. Note that

$d_{R^{\prime}}(u_{i})=\sum\limits_{s\in S^{\prime}}{s(i)}+2N$

and

$d_{R^{\prime c}}(u_{i})=\sum\limits_{s\in S\backslash
S^{\prime}}s(i)+|V_{u_{i}}^{\square}|=\sum\limits_{s\in S\backslash
S^{\prime}}s(i)+\sum\limits_{s\in S}s(i)+2N-2(\sum\limits_{s\in S}s(i)-t(i))$

Then, we have

$\begin{split}d_{R^{\prime c}}(u_{i})&=2N+\sum\limits_{s\in S\backslash
S^{\prime}}s(i)+\sum\limits_{s\in S}s(i)-2(\sum\limits_{s\in S}s(i)-t(i))\\\
&=2N-\Big{(}\sum\limits_{s\in S}s(i)-\sum\limits_{s\in S\backslash
S^{\prime}}s(i)\Big{)}+2t(i)\\\ &=2N-\sum\limits_{s\in
S^{\prime}}s(i)+2t(i)\\\ &=2N+\sum\limits_{s\in
S^{\prime}}s(i)+2\Big{(}t(i)-\sum\limits_{s\in S^{\prime}}s(i)\Big{)}\\\
&>2N+\sum\limits_{s\in S^{\prime}}s(i)=d_{R^{\prime}}(u_{i})\end{split}$

We also know that $u_{i}\in R^{\prime}$, which is a contradiction to the fact
that $R^{\prime}$ is a defensive alliance. This shows that
$I=(k,k^{\prime},S,t)$ is a yes instance. ∎

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

######  Theorem 2.2.

The Defensive Alliance problem is W[1]-hard when parameterized by any of the
following parameters:

  * •

the feedback vertex set number,

  * •

the treewidth and clique width of the input graph,

  * •

the pathwidth and treedepth of the input graph,

even when restricted to bipartite graphs.

##  3 No Polynomial Kernel Parameterized by Vertex Cover Number

A set $C\subseteq V$ is a vertex cover of $G=(V,E)$ if each edge $e\in E$ has
at least one endpoint in $X$. The minimum size of a vertex cover in $G$ is the
vertex cover number of $G$, denoted by $vc(G)$. Parameterized by vertex cover
number $vc$, the Defensive Alliance problem is FPT [17] and in this section we
prove the following kernelization hardness of the Defensive Alliance problem.

######  Theorem 3.1.

The Defensive Alliance problem parameterized by the vertex cover number of the
input graph does not admit a polynomial compression unless coNP $\subseteq$
NP/poly.

To prove Theorem 3.1, we give a polynomial parameter transformation (PPT) from
the well-known Red Blue Dominating Set problem (RBDS) to Defensive Alliance
parameterized by vertex cover number. Recall that in RBDS we are given a
bipartite graph $G=(T\cup S,E)$ and an integer $k$, and we are asked whether
there exists a vertex set $X\subseteq S$ of size at most $k$ such that every
vertex in $T$ has at least one neighbour in $X$. We also refer to the vertices
of $T$ as terminals and to the vertices of $S$ as sources or nonterminals. The
following theorem is known:

######  Theorem 3.2.

[9] RBDS parameterized by $|T|$ does not admit a polynomial compression unless
coNP $\subseteq$ NP/poly.

###  3.1 Proof of Theorem 3.1

By Theorem 3.2, RBDS parameterized by $|T|$ does not admit a polynomial
compression unless coNP $\subseteq$ NP/poly. To prove Theorem 3.1, we give a
PPT from RBDS parameterized by $|T|$ to Defensive Alliance parameterized by
the vertex cover number. Given an instance $(G=(T\cup S,E),k)$ of RBDS, we
construct an instance $(G^{\prime},k^{\prime})$ of Defensive Alliance as
follows. Take three distinct copies $T_{0},T_{1},T_{2}$ of $T$, and let
$t_{i}$ be the copy of $t\in T$ in $T_{i}$. Similarly, take two distinct
copies $S_{0},S_{1}$ of $S$, and let $s_{i}$ be the copy of $s\in S$ in
$S_{i}$. Now for every vertex in $t\in T_{1}\cup T_{2}$, we introduce a set
$V_{t}=\\{t_{1},\ldots,t_{4\ell}\\}$ of vertices adjacent to $t$ where the
number $\ell$ is defined later in the proof. Moreover, create three vertices
$a,b$ and $c$. The vertices $a,b$ and $c$ are adjacent to all the vertices in
set $\bigcup\limits_{t\in T_{1}\cup T_{2}}V_{t}$. We also make $a$ and $b$
adjacent to every vertex in $T_{0}$; and make $a$ adjacent to every vertex in
$S_{1}$. If $(t,s)\in E(G)$ then we add the edges
$(t_{0},s_{0}),(t_{0},s_{1}),(t_{1},s_{1})$ and $(t_{2},s_{0})$ in
$E(G^{\prime})$. Finally, we add a vertex $x^{*}$ which is adjacent to every
vertex in $S_{1}$ and also adjacent to exactly $|S|$ many arbitrary vertices
from $V_{t}$ for some $t\in T_{1}\cup T_{2}$. We observe that $C=T_{0}\cup
T_{1}\cup T_{2}\cup\\{a,b,c,x^{*}\\}$ is a vertex cover of $G^{\prime}$.
Therefore the vertex cover size of $G^{\prime}$ is bounded by $3|T|+4$. We set
$k^{\prime}=|T|+|S|+k+1$ and $l=4k^{\prime}$. See Figure 2 for an
illustration. We now claim that $G$ is a yes-instance of RBDS if and only if
$G^{\prime}$ is a yes-instance of Defensive Alliance.

$G$$G^{\prime}$$t$$t^{\prime}$$s$$s^{\prime}$$t_{1}$$T_{1}$$V_{t_{1}}$$t^{\prime}_{1}$$V_{t_{1}^{\prime}}$$t_{2}$$T_{2}$$V_{t_{2}}$$t^{\prime}_{2}$$V_{t_{2}^{\prime}}$$t_{0}$$T_{0}$$t^{\prime}_{0}$$s_{1}$$S_{1}$$s^{\prime}_{1}$$s_{0}$$S_{0}$$s^{\prime}_{0}$$a$$b$$c$$x^{*}$
Figure 2:  PPT from RBDS to Defensive Alliance, where graph $G$ is show on the
left and $G^{\prime}$ is shown on the right.

Suppose there exists a vertex set $X\subseteq S$ of size at most $k$ in $G$
such that every vertex in $T$ has at least one neighbour in $X$. We claim that
the set $R=S_{1}\cup\big{\\{}s_{0}\in S_{0}\leavevmode\nobreak\
|\leavevmode\nobreak\ s\in X\big{\\}}\cup T_{0}\cup\\{x^{*}\\}$ is a defensive
alliance in graph $G^{\prime}$. Let $x$ be an arbitrary element of $R$. We
prove that $x$ is protected in $R$.

Case 1: Suppose $x\in S_{1}$. Note that
$N_{R}(x)=N_{T_{0}}(x)\cup\\{x^{*}\\}$. Thus, including itself, it has
$d_{G}(x)+2$ defenders in $G^{\prime}$. The attackers of $x$ consist of
elements of $N_{T_{1}}(x)$ and element $a$. Hence $x$ has $d_{G}(x)+1$
attackers. This shows that $x$ has at least as many defenders as attackers;
hence $x$ is protected.

Case 2: Suppose $x\in\big{\\{}s_{0}\in S_{0}\leavevmode\nobreak\
|\leavevmode\nobreak\ s\in X\big{\\}}$. Note that $N_{R}(x)=N_{T_{0}}(x)$.
Thus, including itself, it has $d_{G}(x)+1$ defenders in $G^{\prime}$. The
attackers of $x$ consist of elements of $N_{T_{2}}(x)$. Hence $x$ has
$d_{G}(x)$ attackers in $G^{\prime}$. This shows that $x$ is protected.

Case 3: Suppose $x\in T_{0}$. Clearly, including itself, $x$ has $2d_{G}(x)+3$
neighbours in $G^{\prime}$. Thus it requires at least $d_{G}(x)+2$ many
defenders in $G^{\prime}$. Note that, including itself, $x$ has $d_{G}(x)+1$
neighbours in $S_{1}\subseteq R$. Therefore, it requires at least one
neighbour from the set $\big{\\{}s_{0}\in S_{0}\leavevmode\nobreak\
|\leavevmode\nobreak\ s\in X\big{\\}}$ inside the solution and this is true
because $G$ is a yes instance.

Case 4: Suppose $x=x^{*}$. It has the same number of defenders and attackers
in $G^{\prime}$. This shows that $x$ is protected.

Conversely, suppose there exists a defensive alliance $R$ of size at most
$k^{\prime}$ in $G^{\prime}$. We observe that no vertex from the set
$Q=T_{1}\cup T_{2}\cup\\{a,b,c\\}\bigcup\limits_{t\in T_{1}\cup T_{2}}V_{t}$
can be part of $R$ as otherwise its size will exceed $k^{\prime}$. Since $R$
is non-empty, it must contain a vertex from one of the sets
$\\{x^{*}\\},S_{1},T_{0}$ or $S_{0}$.
Case 1: Suppose $x^{*}\in R$. Since $x^{*}$ has $|S|$ many neighbours in $Q$,
it implies that all the neighbours of $x^{*}$ in $S_{1}$ must be inside the
solution for protection of $x^{*}$. This implies that $S_{1}\subseteq R$. Let
$v$ be an arbitrary vertex in $S_{1}$. Note that $v$ has $d_{G}(v)$ neighbours
in $T_{0}$, and it has $d_{G}(v)+1$ neighbours in $Q$. For protection of $v$
all the neighbours of $v$ in $T_{0}$ must be part of the solution. This
implies that $T_{0}\subseteq R$ as all the vertices in $S_{1}$ must be
protected. Note that till now we have added $|S|+|T|+1$ many vertices in the
solution. Therefore, we can add at most $k$ vertices to the solution from the
set $S_{0}$ as otherwise the solution size will exceed $k^{\prime}$. Suppose
we add a set $X\subseteq S_{0}$ of size at most $k$ to the solution. Consider
the protection of vertices in $T_{0}$. If $v$ is a vertex of $T_{0}$, then it
has $d_{G}(v)$ neighbours in $S_{0}$ and similarly $d_{G}(v)$ neighbours in
$S_{1}$. Excluding itself, $v$ has $2d_{G}(v)+2$ neighbours in $G^{\prime}$.
Thus it requires at least $d_{G}(v)+1$ many neighbours inside the solution. We
know that $d_{G}(v)$ neighbours are inside the solution due to the fact that
$S_{1}\subseteq R$. Therefore, it requires at least one neighbour from $S_{0}$
inside the solution. Since there exists a set $X\subseteq S$ of size at most
$k$ such that all the vertices in $T_{0}$ are protected, it shows that all
vertices in $T_{0}$ have at least one neighbour in $X$. This proves that $G$
is a yes instance.

Case 2: Suppose $R$ contains a vertex $v$ from the set $S_{1}$. In this case,
the protection of $v$ requires $x^{*}$ to be inside the solution and then the
same argument as in Case 1 will lead to the proof.

Case 3: Suppose $R$ contains a vertex $v$ from the set $T_{0}$. Excluding
itself, $v$ has $2d_{G}(v)+2$ neighbours in $G^{\prime}$. Thus it requires at
least $d_{G}(v)+1$ many neighbours from $S_{0}\cup S_{1}$ inside the solution.
This implies that at least one neighbour from the set $S_{1}$ must be inside
the solution. Now the same argument as in Case 2 will lead to the proof.

Case 4: Suppose $R$ contains a vertex $v$ from the set $S_{0}$. Clearly, it
has $d_{G}(v)$ neighbours in $T_{2}\subseteq Q$ and $d_{G}(v)$ neighbours in
$T_{0}$. Since the vertices in the set $Q$ cannot be part of the solution, the
protection of $v$ will imply that all the neighbours of $v$ in $T_{0}$ are
part of the solution. In other words, there exists a vertex in $T_{0}$ which
is inside the solution. Now the same argument as in Case 3 will lead to the
proof.

This proves that $G$ is a yes-instance. ∎

##  4  Defensive Alliance has no Subexponential Algorithm

In this section, we prove lower bound based on ETH for the time needed to
solve the Defensive Alliance problem. In order to prove that a too fast
algorithm for Defensive Alliance contradicts ETH, we give a reduction from
Vertex Cover in graphs of maximum degree 3 and argue that a too fast algorithm
for Defensive Alliance would solve Vertex Cover in graphs of maximum degree 3
in time $2^{o(n)}$. Johnson and Szegedy [15] 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 4.1.

Unless ETH fails, Defensive Alliance does not admit a $2^{o(n)}$ algorithm
where $n$ is the number of vertices of the input graph.

###### Proof.

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

  1. 1.

We introduce the vertex sets $X$ and $Y$ into $G^{\prime}$, where
$X=V(G)=\\{v_{1},\ldots,v_{n}\\}$ and $Y=E(G)=\\{e_{1},e_{2},\ldots,e_{m}\\}$,
the edge set of $G$. We make $v_{i}$ adjacent to $e_{j}$ if and only if
$v_{i}$ is an endpoint of $e_{j}$.

  2. 2.

For every $1\leq i\leq m$, we introduce a cycle $C_{i}$ of length $4$. For
every $1\leq i\leq m-1$, make every vertex of $C_{i}$ adjacent to $e_{i}$ and
$e_{i+1}$; and make every vertex of $C_{m}$ adjacent to $e_{m}$ and $e_{1}$.

  3. 3.

We add a set $F=\\{f_{1},f_{2},\ldots,f_{8}\\}$ of $8$ new vertices into
$G^{\prime}$. Set $k^{\prime}=5m+k$. For every vertex $f\in F$ we introduce a
set $V_{f}$ of $4k^{\prime}$ new vertices into $G^{\prime}$ and make them
adjacent to $f$. We make every vertex of $\\{f_{1},f_{2},f_{3},f_{4},f_{5}\\}$
adjacent to every vertex of $C_{i}$ for $i=1,2,\ldots,m$. We also make every
vertex of $F$ adjacent to every vertex of $Y$.

  4. 4.

Finally, we introduce a vertex $a$ and make it adjacent to every vertex of
$X\cup\bigcup\limits_{f\in F}{V_{f}}$.

Figure 3: The reduction from Vertex Cover to Defensive Alliance.

We now argue equivalence of the instances. Suppose there exists a vertex cover
$S$ of size at most $k$ in $G$. We show that $D=S\cup
Y\bigcup\limits_{i=1}^{m}V(C_{i})$ is a defensive alliance of size at most
$k^{\prime}$ in $G^{\prime}$. It is easy to verify that all the vertices in
$D$ are protected.

To prove the reverse direction of the equivalence, suppose now that $D$ is a
defensive alliance of size at most $k^{\prime}$ in $G^{\prime}$. Observe that
no vertex from $Q=\\{a\\}\cup F\cup\bigcup\limits_{f\in F}V_{f}$ can be part
of $D$ as otherwise the size of $D$ will exceed $k^{\prime}$. To prove this
theorem we need the following simple claim:

######  Claim.

Every defensive alliance $D$ of $G^{\prime}$ contains the set
$Y\bigcup\limits_{i=1}^{m}V(C_{i})$.

###### Proof.

Since the defensive alliance is non-empty, it must contain a vertex from
$X\cup Y\bigcup\limits_{i=1}^{m}V(C_{i})$.

Case 1: Suppose $D$ contains $e_{i}$ from $Y$. We observe that
$\text{deg}_{G^{\prime}}(e_{i})=18$. Note that eight neighbours of $e_{i}$ in
$F$ cannot be part of the solution as they belong to the forbidden set $Q$.
This implies that we need to add at least one vertex from the set
$V(C_{i-1})\cup V(C_{i})$ to the solution for the protection of $e_{i}$.
Without loss of generality, suppose we include one vertex from $V(C_{i})$ in
the solution. Inclusion of one vertex from the set $V(C_{i})$ in the solution
forces $V(C_{i})\subseteq D$. This in turn forces $e_{i+1}$ in the solution.
Repeatedly applying the above argument, we see that
$Y\bigcup\limits_{i=1}^{m}V(C_{i})\subseteq D$.

Case 2: Suppose $D$ contains an arbitrary vertex from the set
$X\bigcup\limits_{i=1}^{m}V(C_{i})$. Then the protection of that vertex forces
at least one vertex from $Y$ in the solution. Using the argument in Case 1, it
implies that $Y\bigcup\limits_{i=1}^{m}V(C_{i})\subseteq D$. $\lrcorner$

We observe that for every vertex $e\in Y$, we have included eight out of its
18 neighbours in the solution. For the protection of $e$, we need to include
at least one more of its neighbours from $X$ in the solution. As we have
already added $5m$ vertices in the solution, we can add a set $S\subseteq X$
of at most $k$ vertices in $D$ such that every vertex $e\in Y$ has at least
one neighbour in $S$. If such a set $S$ exists then it forms a vertex cover of
$G$. This shows that $I$ is a yes instance. ∎

##  5 Defensive Alliance on Circle Graphs

A circle graph is the intersection graph of a set of chords of a circle. That
is, it is an undirected graph whose vertices can be associated with chords of
a circle such that two vertices are adjacent if and only if the corresponding
chords cross each other. Here, we prove that the Defensive Alliance problem is
NP-complete even when restricted to circle graphs, via a reduction from
Dominating Set. It is known that the Dominating Set problem on circle graphs
is NP-hard [16].

######  Theorem 5.1.

The Defensive Alliance problem on circle graphs is NP-complete.

On the way towards this result, we provide hardness result for a variant of
the Defensive Alliance problem which we require in the proof of Theorem 5.1.
The problem Defensive Alliance${}^{\mbox{F}}$ generalizes Defensive Alliance
where some vertices are forced to be outside the solution; these vertices are
called forbidden vertices. This variant can be formalized as follows:

Defensive Alliance${}^{\mbox{F}}$
Input: An undirected graph $G=(V,E)$, a positive integer $r$ and a set
$V_{\square}\subseteq V(G)$ of forbidden vertices. Question: Is there a
defensive alliance $S\subseteq V$ such that $1\leq|S|\leq r$, and $S\cap
V_{\square}=\emptyset$?

######  Lemma 1.

The Defensive Alliance${}^{\mbox{F}}$ problem on circle graphs is NP-complete.

###### Proof.

It is easy to see that the problem is in NP. To show that the problem is NP-
hard we give a polynomial reduction from Dominating Set on circle graphs. Let
$(G,k)$ be an instance of Dominating Set, where $G$ is a circle graph. Suppose
we are also given the circle representation $C$ of $G$. Without loss of
generality, we can assume that none of the endpoints of chords overlap with
each other. We create a graph $G^{\prime}$ and output the instance
$(G^{\prime},V_{\square},k^{\prime})$. See Figure 6. The steps given below
describe the construction of $G^{\prime}$:

  * •

Step 1: Take two distinct copies $G_{1}$ and $G_{2}$ of $G$ and let $v_{i}$ be
the copy of $v\in V(G)$ in graph $G_{i}$. For each $v\in V$, make $v_{1}$
adjacent to every vertex of $N_{G_{2}}(v_{2})\cup\\{v_{2}\\}$ and similarly
make $v_{2}$ adjacent to every vertex of $N_{G_{1}}(v_{1})\cup\\{v_{1}\\}$.
Note that this operation can be easily incorporated in the circle
representation by replacing the chord corresponds to $v$ with two crossing
cords correspond to $v_{1}$ and $v_{2}$ as shown in Figure 4.

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{a}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{b}$$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{c}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{a_{1}}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{b_{1}}$$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{c_{1}}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{a_{2}}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{b_{2}}$$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{c_{2}}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{b}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{a}$$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{c}$$(i)$$(ii)$
Figure 4:  (i) Graph $G$ and its circle representation. (ii) The graph
produced after the first step of reduction and its circle representation.

  * •

Step 2: For every $v\in V$, create two sets of vertices
$X^{v}=\\{x_{1}^{v},\ldots,x^{v}_{2n+1}\\}$ and
$Y^{v}=\\{y_{1}^{v},\ldots,y^{v}_{2n+1}\\}$ and make $v_{1},v_{2}$ adjacent to
every vertex of $X^{v}\cup Y^{v}$. This can be easily incorporated in circle
representation by introducing $2n+1$ parallel chords for the vertices
$x_{1}^{v},\ldots,x_{2n+1}^{v}$ which cross the chords for $v_{1},v_{2}$.
Similarly, introduce $2n+1$ parallel chords for the vertices
$y_{1}^{v},\ldots,y_{2n+1}^{v}$ which cross the chords for $v_{1},v_{2}$, as
shown in Figure 5.

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{v_{1}}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{v_{2}}$$x^{v}_{1}$$x^{v}_{7}$$y^{v}_{1}$$y^{v}_{7}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}v_{1}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}v_{2}$$x_{1}^{v}$$x_{7}^{v}$$y_{7}^{v}$$y_{1}^{v}$
Figure 5: Illustration of Step 2. Here $2n+1=7$.

  * •

Step 3: For each $x^{v}\in X^{v}$, create two 3-vertex cliques $C^{1}_{x^{v}}$
and $C^{2}_{x^{v}}$, and make $x^{v}$ adjacent to every vertex of
$C^{1}_{x^{v}}$ and $C^{2}_{x^{v}}$. For $1\leq i\leq 2n$, make every vertex
of $C^{1}_{x_{i}^{v}}$ adjacent to every vertex of $C^{1}_{x_{i+1}^{v}}$.
Similarly, make every vertex of $C^{2}_{x_{i}^{v}}$ adjacent to every vertex
of $C^{2}_{x_{i+1}^{v}}$ for $1\leq i\leq 2n$. For each $y^{v}\in Y^{v}$,
create two 3-vertex cliques $C^{1}_{y^{v}}$ and $C^{2}_{y^{v}}$, and make
$y^{v}$ adjacent to every vertex of $C^{1}_{y^{v}}$ and $C^{2}_{y^{v}}$. Make
every vertex of $C^{1}_{y_{i}^{v}}$ adjacent to every vertex of
$C^{1}_{y_{i+1}^{v}}$ for $1\leq i\leq 2n$. Similarly, make every vertex of
$C^{2}_{y_{i}^{v}}$ adjacent to every vertex of $C^{2}_{y_{i+1}^{v}}$ for
$1\leq i\leq 2n$. We start at an arbitrary vertex on the circle representation
of $C$ of $G$ and then traverse the circle in counter clockwise direction. We
record the sequence in which the chords are visited. For example, in Figure
4(i), if we start at the red vertex on the circle, then the sequence in which
the chords are visited, is $a,b,c,a,b,c$. Note that every vertex appears twice
in the sequence as every chord is visited twice while traversing the circle.
Thus we get a sequence $S$ of length $2n$ where $n$ is the number of chords.
We use the sequence to connect newly added cliques. For every consecutive pair
$(u,v)$ in the sequence $S$, make every vertex of $C^{2}_{x_{2n+1}^{u}}$
adjacent to every vertex of $C^{1}_{x_{2n+1}^{v}}$ when both $u$ and $v$
appear for the first time in the sequence $S$; make every vertex of
$C^{2}_{y_{2n+1}^{u}}$ adjacent to every vertex of $C^{1}_{y_{2n+1}^{v}}$ when
both $u$ and $v$ appear for the second time; and make every vertex of
$C^{2}_{x_{2n+1}^{u}}$ adjacent to every vertex of $C^{1}_{y_{2n+1}^{v}}$ when
$u$ appears for the first time and $v$ appear for the second time. These
adjacency are shown in green color in Figure 6 and 7.

$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}c_{1}$$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}c_{2}$$x_{1}^{c}$$C^{2}_{x_{1}^{c}}$$C^{1}_{x_{1}^{c}}$$x_{2}^{c}$$C^{2}_{x_{2}^{c}}$$C^{1}_{x_{2}^{c}}$$x_{7}^{c}$$C^{2}_{x_{7}^{c}}$$C^{1}_{x_{7}^{c}}$$y_{1}^{c}$$C^{2}_{y_{1}^{c}}$$C^{1}_{y_{1}^{c}}$$y_{2}^{c}$$C^{2}_{y_{2}^{c}}$$C^{1}_{y_{2}^{c}}$$y_{7}^{c}$$G^{\prime}$$C^{2}_{y_{7}^{c}}$$C^{1}_{y_{7}^{c}}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b_{1}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}b_{2}$$x_{1}^{b}$$C^{2}_{x_{1}^{b}}$$C^{1}_{x_{1}^{b}}$$x_{2}^{b}$$C^{2}_{x_{2}^{b}}$$C^{1}_{x_{2}^{b}}$$x_{7}^{b}$$C^{2}_{x_{7}^{b}}$$C^{1}_{x_{7}^{b}}$$y_{1}^{b}$$C^{2}_{y_{1}^{b}}$$C^{1}_{y_{1}^{b}}$$y_{2}^{b}$$C^{2}_{y_{2}^{b}}$$C^{1}_{y_{2}^{b}}$$y_{7}^{b}$$C^{2}_{y_{7}^{b}}$$C^{1}_{y_{7}^{b}}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{1}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}a_{2}$$x_{1}^{a}$$C_{x^{a}_{1}}^{2}$$C_{x^{a}_{1}}^{1}$$x_{2}^{c}$$C_{x^{a}_{2}}^{2}$$C_{x^{a}_{2}}^{1}$$x_{7}^{a}$$C_{x^{a}_{7}}^{2}$$C_{x^{a}_{7}}^{1}$$y_{1}^{a}$$C_{y^{a}_{1}}^{2}$$C_{y^{a}_{1}}^{1}$$y_{2}^{a}$$C_{y^{a}_{2}}^{2}$$C_{y^{a}_{2}}^{1}$$y_{7}^{a}$$C_{y^{a}_{7}}^{2}$$C_{y^{a}_{7}}^{1}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{a}$$\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{b}$$\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}{c}$$G$
Figure 6:  The reduction of an instance $G$ of the Dominating Set problem on
circle graphs to an instance $G^{\prime}$ of the Defensive
Alliance${}^{\mbox{F}}$ problem in Theorem 5.1. Here $2n+1=7$. One degree
forbidden vertices introduced in Step 4 are not shown here.
$y_{2n+1}^{a}$$C_{y^{a}_{2n+1}}^{2}$$C_{y^{a}_{2n+1}}^{1}$$y_{2n+1}^{b}$$C^{2}_{y_{2n+1}^{b}}$$C^{1}_{y_{2n+1}^{b}}$$y^{b}_{2n+1}$$y^{a}_{2n+1}$$\color[rgb]{0.0,0.5,1.0}\definecolor[named]{pgfstrokecolor}{rgb}{0.0,0.5,1.0}{C^{1}_{y^{b}_{2n+1}}}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{C^{2}_{y^{a}_{2n+1}}}$$C^{1}_{y^{a}_{2n+1}}$$C^{2}_{y^{b}_{2n+1}}$
Figure 7:  Illustration of Step 3.

  * •

Step 4: For every vertex $u$ in cliques, add $d$ forbidden vertices where $d$
is the degree of $u$ until now in $G^{\prime}$. For every vertex $u\in
X^{v}\cup Y^{v}$, add six forbidden vertices and make them adjacent with $u$.
For very vertex $u\in V(G_{1})\cup V(G_{2})$, add $4n+3$ forbidden vertices
and make them adjacent to $u$. This completes the construction of
$G^{\prime}$. We set $k^{\prime}=7n(4n+2)+n+k$ and $V_{\square}$ be the set of
all one degree forbidden vertices.

We observed that the constructed graph $G^{\prime}$ is indeed a circle graph,
and the construction can be performed in time polynomial in $n$. We now claim
that $G$ admits a dominating set of size at most $k$ if and only if
$G^{\prime}$ admits a defensive alliance $D$ of size at most $k^{\prime}$ such
that $D\cap V_{\square}=\emptyset$. Assume first that $G$ admits a dominating
set $S$ of size at most $k$. Consider

$D=\Big{\\{}v_{1}\leavevmode\nobreak\ :\leavevmode\nobreak\ v\in
S\Big{\\}}\bigcup V(G_{2})\bigcup\limits_{v\in V(G)}X^{v}\cup
Y^{v}\bigcup\limits_{v\in
V(G)}\bigcup\limits_{i=1}^{2n+1}V(C^{1}_{x^{v}_{i}})\cup
V(C^{2}_{x^{v}_{i}})\cup V(C^{1}_{y^{v}_{i}})\cup V(C^{2}_{y^{v}_{i}}).$

Clearly, $|D|\leq 7n(4n+2)+n+k$ and $D\cap V_{\square}=\emptyset$, so it
suffices to prove that $D$ is a defensive alliance in $G^{\prime}$. We observe
that every vertex in $\bigcup\limits_{v\in
V(G)}\bigcup\limits_{i=1}^{2n+1}V(C^{1}_{x^{v}_{i}})\cup
V(C^{2}_{x^{v}_{i}})\cup V(C^{1}_{y^{v}_{i}})\cup V(C^{2}_{y^{v}_{i}})$, has
equal neighbours inside and outside the solution. Every vertex
$v\in\bigcup\limits_{v\in V(G)}X^{v}\cup Y^{v}$ is protected as it has at
least 7 neighbours inside the solution and at most 7 neighbours outside the
solution. Each $v\in\Big{\\{}v_{1}\leavevmode\nobreak\ :\leavevmode\nobreak\
v\in S\Big{\\}}\bigcup V(G_{2})$ has at least $d+1+4n+2$ neighbours inside the
solution and at most $d+1+4n+2$ neighbours outside the solution where
$d=d_{G}(x)$. This shows that $D$ is a defensive alliance of size at most
$k^{\prime}$ in $G^{\prime}$.

Conversely, suppose that $G^{\prime}$ admits a defensive alliance $D$ of size
at most $k^{\prime}$ such that $D\cap V_{\square}=\emptyset$. We define

$V_{\triangle}=\bigcup\limits_{v\in V(G)}X^{v}\cup Y^{v}\bigcup\limits_{v\in
V(G)}\bigcup\limits_{i=1}^{2n+1}V(C^{1}_{x^{v}_{i}})\cup
V(C^{2}_{x^{v}_{i}})\cup V(C^{1}_{y^{v}_{i}})\cup V(C^{2}_{y^{v}_{i}}).$

We first show that $V_{\triangle}\subseteq D$. Since $D$ in non-empty, it
should contain a vertex from either $V_{\triangle}$ or $V(G_{1})\cup
V(G_{2})$. We consider the following cases:

Case 1: Suppose $D$ contains a vertex from
$\bigcup\limits_{i=1}^{2n+1}V(C^{1}_{x^{v}_{i}})\cup V(C^{2}_{x^{v}_{i}})\cup
V(C^{1}_{y^{v}_{i}})\cup V(C^{2}_{y^{v}_{i}})$. Without loss of generality, we
may assume that $D$ contains a vertex $u$ from $V(C^{1}_{x^{v}})$. It is easy
to see that $u$ is protected if and only if all its non-forbidden neighbours
are inside $D$ because the number of forbidden neighbours of $u$ is equal to
the number of non-forbidden neighbours. This implies that $x^{v}\in D$. It is
easy to note that either $C_{x^{v}}\subseteq D$ or $C_{x^{v}}\cap
D=\emptyset$. Since $d_{G^{\prime}}(x^{v})=15$ and $x^{v}$ has $6$ forbidden
neighbours, the above observation implies that $C^{1}_{x^{v}}\cup
C^{2}_{x^{v}}\subseteq D$. This implies that
$\bigcup\limits_{i=1}^{2n+1}C^{1}_{x_{i}^{v}}\cup C^{2}_{x_{i}^{v}}\subseteq
D$. This in turn implies that $X^{v}\subseteq D$. Note that
$C^{2}_{x_{2n+1}^{v}}$ is adjacent to $C^{1}_{x_{2n+1}^{w}}$ (resp.
$C^{1}_{y_{2n+1}^{w}}$) for some $w\in G$ such that $u,w$ are consecutive
elements in the sequence $S$ and $w$ appears for the first (resp. second) time
in the sequence. Therefore $\bigcup\limits_{i=1}^{2n+1}C^{1}_{x_{i}^{w}}\cup
C^{2}_{x_{i}^{w}}\subseteq D$ and also $X^{w}\subseteq D$ if $w$ appears for
the first time in the sequence; whereas
$\bigcup\limits_{i=1}^{2n+1}C^{1}_{y_{i}^{w}}\cup C^{2}_{y_{i}^{w}}\subseteq
D$ and also $Y^{w}\subseteq D$ if $w$ appears for the second time in the
sequence. Repeatedly applying the above argument, we get
$V_{\triangle}\subseteq D$.

Case 2: Suppose $D$ contains a vertex from $\bigcup\limits_{v\in
V(G)}X^{v}\cup Y^{v}$. Without loss of generality, we may assume that $D$
contains $x^{v}$ from $X^{v}$. We observe that the protection of $x^{v}$
clearly requires at least one vertex from the set $C^{1}_{x^{v}}\cup
C^{2}_{x^{v}}$. Now, Case 1 implies that $V_{\triangle}\subseteq D$.

Case 3: Suppose $D$ contains a vertex $v$ from $V(G_{1})\cup V(G_{2})$. The
protection of $v$ requires at least one vertex from the set $X^{v}\cup Y^{v}$.
Now, Case 2 implies that $V_{\triangle}\subseteq D$.

Observe that $|V_{\triangle}|=7n(4n+2)$. Therefore $|D\cap(V(G_{1})\cup
V(G_{2}))|\leq n+k$. For each $v\in V(G)$, the protection of every vertex in
$X^{v}\cup Y^{v}$ requires either $v_{1}$ or $v_{2}$ inside the solution.
Since, $v_{1}$ and $v_{2}$ are twins, we can assume that $V(G_{2})\subseteq
D$. Let $v_{2}\in V(G_{2})$. We see that $v_{2}$ has $d+1+4n+2$ neighbours
(including itself) inside the solution. The vertex $v_{2}$ has $4n+3$
forbidden neighbours. The only unsettled neighbours of $v_{2}$ are in
$V(G_{1})$ and $v_{2}$ has $d+1$ neighbours in $V(G_{1})$. For protection of
each $v_{2}\in V(G_{2})$, we require at least one neighbour from $V(G_{1})$
inside the solution. We can add at most $k$ vertices from $V(G_{1})$ to the
solution as we have already added $7n(4n+2)+n$ vertices. Clearly,
$S=V(G_{1})\cap D$ is a dominating set of size at most $k$. ∎

###  5.1 Proof of Theorem 5.1

It is easy to see that the problem is in NP. To show that the problem is NP-
hard we give a polynomial reduction from Defensive Alliance${}^{\mbox{F}}$.
Let $(G,k,V_{\square})$ be an instance of Defensive Alliance${}^{\mbox{F}}$,
where $G$ is a circle graph. We construct an instance
$(G^{\prime},k^{\prime})$ of Defensive Alliance the following way. For every
$x\in V_{\square}$, create a vertex $x^{\prime}$ and a set of $2k^{\prime}$
vertices $V^{x}_{\square}$. Make both $x$ and $x^{\prime}$ adjacent to every
vertex in $V^{x}_{\square}$. This completes the construction of $G^{\prime}$.
Set $k^{\prime}=k$.

$x$$x^{\prime}$$x$$x^{\prime}$ Figure 8:  The circle representation to get rid
of forbidden vertices when $k^{\prime}=2$.

We observe in Figure 8 that the constructed graph $G^{\prime}$ is indeed a
circle graph, and the construction can be performed in time polynomial in $n$.
We now claim that $G$ admits a defensive alliance $D$ of size at most $k$ such
that $D\cap V_{\square}=\emptyset$ if and only if $G^{\prime}$ admits a
defensive alliance $D^{\prime}$ of size at most $k^{\prime}$. Assume first
that $D$ is a defensive alliance of size at most $k$ in $G$ such that $D\cap
V_{\square}=\emptyset$. Consider $D^{\prime}=D$. Clearly, $D^{\prime}$ is a
defensive alliance of size at most $k^{\prime}$ in $G^{\prime}$. Conversely,
suppose that $G^{\prime}$ admits a defensive alliance $D^{\prime}$ of size at
most $k^{\prime}$. Observe that $D^{\prime}\cap\bigcup\limits_{x\in
V_{\square}}V^{x}_{\square}\cup\\{x,x^{\prime}\\}=\emptyset$. As $x$ and
$x^{\prime}$ are of degree $2k^{\prime}$, they cannot be part of a defensive
alliance of size at most $k^{\prime}$. As $x$ and $x^{\prime}$ are outside
$D^{\prime}$, the vertices in $V^{x}_{\square}$ cannot be in $D^{\prime}$.
Consider $D=D^{\prime}$. Clearly, $D$ is a defensive alliance of size at most
$k$ in $G$ such that $D\cap V_{\square}=\emptyset$.∎

##  6 Conclusions

In this work we proved that the Defensive Alliance problem is W[1]-hard
parameterized by a wide range of fairly restrictive structural parameters such
as the feedback vertex set number, pathwidth, treewidth, treedepth, and clique
width of the input graph, even when restricted to bipartite graph. We also
proved that the problem parameterized by the vertex cover number of the input
graph does not admit a polynomial compression unless coNP $\subseteq$ NP/poly;
it cannot be solved in time $2^{o(n)}$, unless ETH fails, and the Defensive
Alliance problem on circle graphs is NP-complete. By the construction of our
proofs in Section 2, it is clear that hardness also holds for problem variants
that ask for defensive alliances exactly of a given size. In the future it may
be interesting to study if our ideas can be useful for different kinds of
alliances from the literature such as offensive and powerful alliances. The
parameterized complexity of offensive and defensive alliance problems remain
unsettled when parameterized by other important structural graph parameters
like twin cover and modular-width.

## References

  * [1] B. Bliem and S. Woltran.  Defensive alliances in graphs of bounded treewidth.  Discrete Applied Mathematics, 251:334 – 339, 2018.
  * [2] C.-W. Chang, M.-L. Chia, C.-J. Hsu, D. Kuo, L.-L. Lai, and F.-H. Wang.  Global defensive alliances of trees and cartesian product of paths and cycles.  Discrete Applied Mathematics, 160(4):479 – 487, 2012.
  * [3] M. Chellali and T. W. Haynes.  Global alliances and independence in trees.  Discuss. Math. Graph Theory, 27(1):19–27, 2007.
  * [4] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [5] R. G. Downey and M. R. Fellows.  Parameterized Complexity.  Springer, 2012.
  * [6] R. Enciso.  Alliances in graphs: Parameterized algorithms and on partitioning series -parallel graphs.  PhD thesis, USA, 2009.
  * [7] H. Fernau and D. Raible.  Alliances in graphs: a complexity-theoretic study.  In Proceeding Volume II of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science, 2007.
  * [8] H. Fernau, J. A. Rodríguez, and J. M. Sigarreta.  Offensive r-alliances in graphs.  Discrete Applied Mathematics, 157(1):177 – 182, 2009.
  * [9] F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Kernelization: Theory of Parameterized Preprocessing.  Cambridge University Press, 2019.
  * [10] G. Fricke, L. Lawson, T. Haynes, M. Hedetniemi, and S. Hedetniemi.  A note on defensive alliances in graphs.  Bulletin of the Institute of Combinatorics and its Applications, 38:37–41, 2003.
  * [11] A. Gaikwad, S. Maity, and S. K. Tripathi.  Parameterized complexity of defensive and offensive alliances in graphs.  In D. Goswami and T. A. Hoang, editors, Distributed Computing and Internet Technology, pages 175–187, Cham, 2021. Springer International Publishing.
  * [12] R. Ganian, F. Klute, and S. Ordyniak.  On structural parameterizations of the bounded-degree vertex deletion problem.  Algorithmica, 2020.
  * [13] L. H. Jamieson.  Algorithms and Complexity for Alliances and Weighted Alliances of Various Types.  PhD thesis, USA, 2007.
  * [14] L. H. Jamieson, S. T. Hedetniemi, and A. A. McRae.  The algorithmic complexity of alliances in graphs.  Journal of Combinatorial Mathematics and Combinatorial Computing, 68:137–150, 2009.
  * [15] D. S. Johnson and M. Szegedy.  What are the least tractable instances of max independent set?  In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’99, page 927–928, USA, 1999. Society for Industrial and Applied Mathematics.
  * [16] J. Keil.  The complexity of domination problems in circle graphs.  Discrete Applied Mathematics, 42(1):51–63, 1993.
  * [17] M. Kiyomi and Y. Otachi.  Alliances in graphs of bounded clique-width.  Discrete Applied Mathematics, 223:91 – 97, 2017.
  * [18] T. Kloks.  Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science.  Springer, 1994.
  * [19] P. Kristiansen, M. Hedetniemi, and S. Hedetniemi.  Alliances in graphs.  Journal of Combinatorial Mathematics and Combinatorial Computing, 48:157–177, 2004.
  * [20] J. Nesetril and P. O. de Mendez.  Sparsity: Graphs, Structures, and Algorithms.  Springer Publishing Company, Incorporated, 2014.
  * [21] N. Robertson and P. Seymour.  Graph minors. iii. planar tree-width.  Journal of Combinatorial Theory, Series B, 36(1):49 – 64, 1984\.
  * [22] J. Rodríguez-Velázquez and J. Sigarreta.  Global offensive alliances in graphs.  Electronic Notes in Discrete Mathematics, 25:157 – 164, 2006.
  * [23] J. Sigarreta, S. Bermudo, and H. Fernau.  On the complement graph and defensive k-alliances.  Discrete Applied Mathematics, 157(8):1687 – 1695, 2009.
  * [24] J. Sigarreta and J. Rodríguez.  On defensive alliances and line graphs.  Applied Mathematics Letters, 19(12):1345 – 1350, 2006.
  * [25] J. Sigarreta and J. Rodríguez.  On the global offensive alliance number of a graph.  Discrete Applied Mathematics, 157(2):219 – 226, 2009.
  * [26] D. B. West.  Introduction to Graph Theory.  Prentice Hall, 2000.


# Grounding Natural Language Instructions: Can Large Language Models Capture
Spatial Information?

Julia Rozanova1, Deborah Ferreira*1, Krishna Dubba3,
Weiwei Cheng3, Dell Zhang4, Andre Freitas12
1Department of Computer Science, University of Manchester, UK
2Idiap Research Institute, Switzerland
3Blue Prism AI Labs, London, UK
4ByteDance AI Lab, London, UK
{julia.rozanova, deborah.ferreira<EMAIL_ADDRESS>{krishna.dubba<EMAIL_ADDRESS><EMAIL_ADDRESS>Equal
contribution.

###### Abstract

Models designed for intelligent process automation are required to be capable
of grounding user interface elements. This task of _interface element
grounding_ is centred on linking instructions in natural language to their
target referents. Even though BERT and similar pre-trained language models
have excelled in several NLP tasks, their use has not been widely explored for
the UI grounding domain. This work concentrates on testing and probing the
grounding abilities of three different transformer-based models: BERT, RoBERTa
and LayoutLM. Our primary focus is on these models’ spatial reasoning skills,
given their importance in this domain. We observe that LayoutLM has a
promising advantage for applications in this domain, even though it was
created for a different original purpose (representing scanned documents): the
learned spatial features appear to be transferable to the UI grounding
setting, especially as they demonstrate the ability to discriminate between
target _directions_ in natural language instructions.

## Introduction

The majority of human-computer interactions are mediated by Graphical User
Interfaces (GUIs) within desktop and mobile environments. GUIs provide the
interaction backbone in which end-users compose and repurpose atomic
functional elements embedded within existing applications.

Recently, there is an emerging effort to build models to support the
automation of long-tail processes within a multi-application Desktop/GUI
environment (Ferreira et al. 2020). This effort encompasses the interfacing of
Human-Desktop Interaction (HDI) with natural language, both for HDI
understanding (the creation of natural language descriptions that describe
HDIs) and HDI semantic parsing (the execution of HDI actions from commands
expressed in natural language).

One fundamental skill required for designing such models is being able to
_ground_ UI element mentions in natural language instructions, in the style of
a mapping task. A natural language command in most cases will contain an
action verb. Often, this verb has as an argument an object that refers to an
interface element. A model geared towards understanding this instruction
should be aware of the mapping between words and interface elements’ concrete
realisation. This mapping is named interface element grounding task (Pasupat
et al. 2018) or UI grounding. Consider the instruction “Click on the cancel
button.”: in order to ground this instruction, one is expected to find the
cancel button in a screen. Applications of a UI grounding model ranges from
intelligent process automation to the creation of accessibility tools.

Transformer-based models have achieved excellent performance in tasks
requiring semantic inference, with state of the art results in various NLP
tasks. However, such models’ expertise in reasoning with elements positioned
in a 2-dimensional space has limited research, especially in the interface
element grounding domain.

This work focuses on testing and probing the grounding abilities of three
different transformer-based models, namely BERT (Devlin et al. 2019), RoBERTa
(Liu et al. 2019), and LayoutLM (Xu et al. 2020). This process is performed in
two parts: first, evaluating the accuracy for UI grounding for different
reasoning types, and second, probing the generated representations using
spatial auxiliary tasks.

The contributions of this work can be summarised as follows:

  * •

We provide a first systematic study of the spatial reasoning capabilities of
transformer-based models in the UI grounding setting.

  * •

We compare different pre-trained transformer-based architectures and present a
probing-based analysis of their spatial reasoning capabilities.

  * •

We empirically demonstrate that the semantic representation of textual and
layout information from scanned documents can also be successfully transferred
to represent user interfaces.

  * •

We propose a novel application domain for transformer-based models.

  * •

We demonstrate the need for more complex spatial reasoning datasets and models
capable of relative spatial reasoning.

## Problem Formulation: Grounding Interface Elements

Given a command (noun phrase) $c$ contained in a natural language command and
an user interface composed of a set $U=\\{u_{1},u_{2},\ldots,u_{2}\\}$ of
_interface elements_ , where each element $i$ is composed of a given text
content $u_{i_{T}}$ and a bounding box
$u_{i_{BB}}=[u_{i_{x_{0}}},u_{i_{x_{1}}},u_{i_{y_{0}}},u_{i_{y_{1}}}]$, the
grounding task aims to select the correct element $u_{i}\in U$ which is
referred in phrase $c$, assuming that this phrase only refers to a unique
element.

Given $U$ and $c$, the following condition distribution over the elements is
defined:

$p(u_{i}|p)\propto exp[s(f(c),g(u_{i}))]$ (1)

where $g(\cdot)$ and $f(\cdot)$ are embedding functions for the UI elements
and phrase, respectively, and $s(\cdot,\cdot)$ is a scoring function between
command and UI element. To obtain the correct interface element, one needs to
maximise the log-likelihood for the correct interface element.

To solve the grounding task, a model needs mainly to focus on three types of
reasoning (Li et al. 2020; Pasupat et al. 2018), subject to what is required
by the command $c$. The types of reasoning are _extractive_ , _absolute
spatial_ and _relative spatial_.

Extractive reasoning is required in the most trivial cases, where one needs
only to match the textual content $u_{i_{T}}$ of the interface element with
the text in $c$. This scenario includes cases where there is an exact keyword
matching and also where some paraphrasing is required. As shown in example (a)
from Figure 1, for this type of reasoning, a model does not require any
spatial information about the interface element.

When spatial reasoning is needed, the task increases in complexity. Absolute
spatial reasoning requires a model to understand the positional information
contained in the command and to be able to locate the interface element inside
a screen. Figure 1(b) presents an example of this case, where it is not
possible to identify the element without having the values of its bounding
box. However, it does not require the representation of surrounding interface
elements, unlike relative spatial reasoning.

Relative spatial reasoning is the most challenging type considering a model is
expected to interpret a relative spatial command, demanding an understanding
of the screen as a whole. In this type of command, an interface element is
referred to in relation to another element. As shown in Figure 1(c), this type
of instruction can be easily mistaken with an extractive reasoning command in
circumstances where a model is not knowledgeable of the spatial nature of the
task given then extra noise with textual information from a different element.

Figure 1: Example of three different commands, requiring different types of
reasoning, and matching interface elements in a mobile screen. The screen
presented here is part of the Rico dataset (Deka et al. 2017).

## Related Work

### UI Grounding

Past research on grounding interface elements has mainly focused on
applications to mobile screens and web elements. Li et al. (2020) proposes
Seq2Act, a two-stage Transformer model for grounding UI elements in an Android
environment. In our work, we compare pre-trained models with the Seq2Act
model. Pasupat et al. (2018) proposes an embedding based model for grounding
instructions based on web elements. They are able to represent not only
positional information but also properties of UI elements.

There is still limited research in the task of interface element grounding.
However, a considerable amount of literature has been published on semantic
parsing for task execution. Goldwasser and Roth (2011) and Volkova et al.
(2013) focus on using natural language instructions to learn the concepts and
rules of an environment, where these elements can be used to execute and
verify tasks. Similarly, the work by Branavan, Silver, and Barzilay (2012) use
text from manuals to learn the rules of the game Civilization II.

For goal-oriented tasks, the parsing can be modelled around a
reward/punishment function. Branavan, Zettlemoyer, and Barzilay (2010)
explicitly models an environment where a reward function is used to evaluate
how well a command sequence achieves a described task. MacGlashan et al.
(2014) propose a learning algorithm for generating high-level task definitions
from instruction, derived from online human-delivered reward and punishment.

### Probing

There is often interest in the _intermediate_ features or information captured
by neural models. There are two broad categories of approaches to determining
the extent to which certain features or phenomena are captured: either
_behavioural_ analysis or _structural_ analysis. The common practise of
evaluating a model’s accuracy on a targeted challenge dataset (designed to be
representative of the feature or phenomenon in question) is a form of
_behavioural_ analysis. On the other hand, _structural_ analysis concerns the
structural properties of the representation space, such as emergent feature
clusters or geometric regularities.

A recently popular style of structural analysis is methodical diagnostic
classification or _probing 111The term _probing_ is sometimes also used for
studies featuring only behavioural analyses, but we refer specifically to the
methodology surrounding auxiliary classification on top of intermediate model
representations, as in Alain and Bengio (2018); Hewitt and Manning (2019a) and
Pimentel et al. (2020c)_. First introduced in Alain and Bengio (2018) as
_diagnostic classification_ , probing has been popular in the study of natural
language processing models, where it has shown the prevalence of rich
syntactic features (for example in Hewitt and Manning (2019a)) and semantic
features (Vulić et al. 2020). Given that the aim of probing studies is very
different from the usual machine learning goal of achieving the maximum
possible accuracy on test sets, there has been much discussion on the
suggested best practices and possible pitfalls when carrying out probing
studies (Zhang and Bowman 2018; Hewitt and Liang 2019; Voita and Titov 2020;
Pimentel et al. 2020c, a). We attempt to take on most of the suggestions in
our methodology, especially the control tasks and selectivity measure in
Hewitt and Liang (2019) and the complexity ranges in Hewitt and Manning
(2019a); Pimentel et al. (2020b).

## Experimental Setup

The experiments in this work are separated into two parts. The first part
evaluates the accuracy of distinct models on the task of grounding UI elements
for mobile devices, while the second part assesses the spatial reasoning
capabilities of the models trained during the first stage. All the datasets
generated, trained models and code used in this work are made available in
http://github.com/debymf/ipa˙probing.

The stages of the experiments are described in the following subsections.

### Interface Element Grounding

#### Datasets

For this work, we focused on datasets containing commands for grounding mobile
UI elements. This choice was due to the more extensive availability of
datasets, unlike desktop applications. However, the concepts and experiments
presented here can easily be transported to different interface environments,
given their similar structure. The datasets used for our experiments are
PixelHelp and RicoSCA (Li et al. 2020).

RicoSCA is a dataset containing commands with its respective matching
interface element, composed of textual content and bounding box. The dataset
contains a total of 329,411 instructions222The number of instructions is
different from the reported value in the original paper since only the
generation script is provided, and that does not ensure that the same dataset
is generated. In order to ensure reproducibility, we will make available our
version of the dataset with respective splits. which we split between
train/dev/set as shown in Table 1. RicoSCA contains three types of commands,
Name-Type, Absolute-Location and Relative-Location, which we map to
extractive, spatial absolute and spatial relative reasoning, respectively.

PixelHelp contains 187 multi-step instructions, where 88 are general tasks,
such as configuring accounts, 38 are e-mail tasks, 31 are browser tasks, and
30 photos related tasks. PixelHelp is only used for testing, given its smaller
size. In this work, we focus only on single-step commands; therefore,
PixelHelp cannot be used in its original format. To obtain single-step
commands from the multi-step ones found in PixelHelp, we used the action
phrase extraction model proposed by Li et al. (2020). We obtained a total of
780 single step commands. This dataset does not contain annotations on the
type of reasoning required for each command. To generate such data, two expert
human annotators enriched the dataset with the correct types, obtaining a .78
Kappa score, providing strong reliability. The details of this dataset are
also shown in Table 1.

Dataset | Number of Instructions
---|---
Extractive | Absolute | Relative | Total
RicoSCA - Train | 100,921 | 6,531 | 57,222 | 164,674
RicoSCA - Dev | 40,504 | 2,529 | 22,577 | 65,610
RicoSCA - Test | 60,922 | 3,897 | 34,308 | 99,127
PixelHelp | 673 | 100 | 7 | 780

Table 1: Number of instructions for each dataset, indicating the type of
reasoning required for grounding.

#### Models

For the grounding of mobile UI elements, we compare the performance of four
different models: BERT (base), RoBERTa (base), LayoutLM (base) and Seq2Act.

_BERT_ (Devlin et al. 2019) and _RoBERTa_ (Liu et al. 2019) are known to
obtain excellent results in tasks where direct semantic similarity is
required. However, there is still no conclusive evidence that this model can
reason spatially, especially for the task of grounding UI elements. _LayoutLM_
(Xu et al. 2020) is a ”Language” Model for the combination of text and
document layout, geared towards document image understanding tasks. This model
takes as input a bounding box that denotes the relative position of a token
within a document. This positional embedding can capture the relationship
among tokens within a document. LayoutLM was initially proposed as a pre-
trained model for physical documents, making this work a novel application for
such a model. This model can also take as input images representing a layout
structure; however, we only consider the interface elements’ positional
features as input in this work.

In order to apply such pre-trained models, we reformulate the interface
element grounding problem as a pairwise relevance classification problem.
Given a natural language command $c$ and interface elements
$U=\\{u_{1},\ldots,u_{n}\\}$, a function $f(c,u_{i})$ is defined, where
$f(c,u_{i})=1$ if $u_{i}$ is the target element in $c$ and $f(c,u_{i})=0$
otherwise.

BERT and RoBERTa take as input the command $c$ and the text $u_{i_{T}}$ from
the interface element being tested in the format $[c||u_{i_{T}}]$. These
models cannot receive the element’s position as input since they cannot
interpret such a structure. On the other hand, LayoutLM also takes as input
the bounding box $u_{i_{BB}}$ of the interface element, hence, it uses two
different inputs: the textual information $[c||u_{i_{T}}]$, in the same manner
as BERT, and the positional information $[u_{i_{BB}}]$.

These models are trained using the RicoSCA training and development set and
tested for the PixelHelp and RicoSCA testing sets. The supporting pipelines
for inferring the correct interface element using these models are illustrated
in Figure 2.

Figure 2: Inference pipeline for LayoutLM, BERT and RoBERTa. Both models
generate representations based on the instruction and interface elements. The
predicted interface element is inferred from the output probabilities for the
pair classification setting. Best seen in colour.

Both models are trained333The models are trained with a learning rate of
$1e$-$5$, batch size of $16$, a maximum sequence length of $256$ and $5$
epochs. Using $4$ Tesla V100s, both models take around $21$ hours to complete
training. with the objective to minimise Cross Entropy loss for the pair
classification task, so that the classifier is trained on the conditional
likelihood $p(u_{i}\mid c)$ and select the UI element
$\operatorname*{arg\,max}_{u_{i}\in U}~{}p(u_{i}\mid c)$

The last compared model is _Seq2Act_ (Li et al. 2020), composed of two
different parts, an action phrase-extraction step and a grounding step. The
first stage is a Transformer architecture which maps multi-step instructions
to single-step ones. The grounding step matches these single-step commands to
UI objects using another Transformer that contextually represents UI objects,
and grounds object descriptions. Given the focus of this work, we are only
interested in the results from the grounding stage. Seq2Act is trained using
the full RicoSCA dataset; therefore, it was necessary to retrain the model
using only the training split for RicoSCA. Given that the model was trained on
a smaller split of the RicoSCA dataset, the obtained results differed slightly
from the original paper.

### Probing Methodology

Following recent works on the developing best practices in probing studies
(Hewitt and Liang 2019; Hewitt and Manning 2019b; Pimentel et al. 2020c, a;
Voita et al. 2019), we have followed three key principles:

  1. 1.

Prioritising probe families with _simple structure_ ,

  2. 2.

Using a range of probing model complexities with in a family of probing
models, and

  3. 3.

Using randomised control tasks (Hewitt and Liang 2019) in order to ensure
_maximum selectivity_ for reported accuracies.

#### Probe Complexity Control

For each auxilliary task, an MLP probe architectures, training 50 probes of
varying complexities using the Probe-Ably framework of (Ferreira et al.
2021)444https://github.com/ai-systems/Probe-Ably with the default
configurations for the MLP model. We use the number of parameters as a naive
approximation of model complexity.

### Control Task and Selectivity Measure

For the a given set of probe hyperparameters, we train the probes on a
$30-20-50$ train-dev-test split of the auxiliary task data. For each fully
trained probe, we report both the test accuracy and the _selectivity_ measure
(Hewitt and Liang 2019) in its “entropic form”: namely, the difference between
the cross-entropy loss of the auxiliary task test set and the cross-entropy
loss of the randomised _control task_ training set. We use a simple control
task where input representation vectors have been assigned fixed random labels
from among the auxiliary task target classes. Tracking the selectivity ensures
that we are not using a probe that is complex enough to be _overly expressive_
to the point of having the capacity to overfit the randomised control training
set.

#### Auxiliary tasks

Towards probing the representation generated by LayoutLM, BERT and RoBERTa, we
define four different auxiliary tasks, two for each spatial reasoning type:

  * •

Absolute spatial reasoning probing (Figure 3a): Given the representation of a
command and an interface element, the first task is determining if the element
is located at the bottom or top of the screen (AT1) while the second task
focus on determining if the element is at the left or the right of the screen
(AT2).

  * •

Relative spatial reasoning probing (Figure 3b): Given the representation of a
command and an interface element, the third task requires positioning the
interface element at the top or bottom of the element targeted by the command
(AT3). Similarly, the last task indicates if the element is at the target’s
left or right (AT4).

(a) Determining the absolute position.

(b) Determining the relative position.

Figure 3: Illustration of the two types of auxiliary tasks, which requires
determining the relative position from the obtained representation.

## Results and Discussion

This section presents the results for both parts of this work, the interface
element grounding and the spatial reasoning probing.

### UI Grounding Performance

Table 2 presents the accuracy of all models for the task of interface element
grounding. The results for the RicoSCA dataset are separated by the type of
reasoning required: extractive reasoning (Ext), absolute spatial reasoning
(Abs) and relative spatial reasoning (Rel). We choose not to present the same
for PixelHelp, given the small representativity of instructions demanding
spatial reasoning in this dataset.

Model | Datasets
---|---
PixelHelp | RicoSCA Dev | RicoSCA Test
Ext | Abs | Rel | All | Ext | Abs | Rel | All
BERT-Base | 86.28 | 99.61 | 67.12 | 54.75 | 78.07 | 99.54 | 67.07 | 55.69 | 77.92
RoBERTa-Base | 87.17 | 99.60 | 67.03 | 56.31 | 78.12 | 99.53 | 68.03 | 56.47 | 77.98
LayoutLM | 71.41 | 98.51 | 86.75 | 61.40 | 77.62 | 98.40 | 90.80 | 60.53 | 77.51
Seq2Act | 75.86 | 96.64 | 67.14 | 33.23 | 73.95 | 96.75 | 65.89 | 31.75 | 73.78
Table 2: Accuracy for the compared models. For the RicoSCA dataset, we compare
the performance for different types of required reasoning for grounding. The
Seq2Act results presented here are obtained from partial matching, since we
are considering single-step commands.

As expected, BERT and RoBERTa obtains outstanding performance for instructions
requiring lexical overlap and semantic similarity. It easily outperforms the
state-of-the-art model, Seq2Act, raising the importance of pre-trained model
baselines in such studies: often, the basic similarity features captured by
out-of-the-box language models are sufficient for complex tasks without
needing to introduce new architectures. Even though such models do not have
access to the interface elements’ position, they seems to manage (partially)
the commands requiring spatial reasoning.

Similarly, LayoutLM achieves almost perfect accuracy for extractive reasoning
commands while also having a superior performance for absolute reasoning. This
performance is likely due to the fact that LayoutLM is integrated with BERT,
with the added capability of representing positional information.

This result confers evidence that the structure learned from documents layout
can also be transported to interface elements. LayoutLM achieves a lower
performance on the relative spatial reasoning but still outperforms BERT for
this task type. We hypothesise that such results could be improved by
modifying the pair classification task to a selection across elements task. In
this case, the model would be aware of all the screen elements when inferring
a decision. However, such models are still very computationally demanding, and
given that a screen can easily have up to $300$ UI elements, there is a need
for more scalable approaches.

Even though Seq2Act is designed with the understanding of spatial reasoning in
mind, we can notice that the model is outperformed in almost all aspects by
transformers that encode only text.

The overall obtained results highlight the need for more robust datasets for
testing UI element grounding. Future work proposing new datasets and
approaches capable of encoding positional information should initially ensure
that the dataset evaluates such properties. The training protocol present in
this work can be employed to remove trivial examples from the dataset.
Instances of the dataset that can be predicted with high certainty by models
that do not encode positions should be removed for testing specific spatial
reasoning.

### Probing Results

In Figures 4 (a-d) we present the _auxiliary task test accuracy_ and the
_selectivity_ of 50 trained MLP probes with varying complexity. 555Seq2Act
does not generate a representation; hence, it was not included in the probing
stage. Regions of maximum selectivity indicate that the accuracy scores are
more trustworthy: low selectivity indicates little difference between the
control task scores and the auxiliary task scores. It is important to ensure
that the selectivity doesn’t drop off (indicating an overly expressive probe),
which is why the selectivity plots are included.

(a) AT1 probing.

(b) AT2 probing.

(c) AT3 probing.

(d) AT4 probing.

Figure 4: Probing results for the both spatial reasoning task for MLP probes
with varying complexity (approximated here by the number of parameters).

As we can see from the MLP probes, LayoutLM outperform BERT and RoBERTa in the
auxiliary spatial reasoning tasks, which shows that the generated
representations are better able to discriminate between spatial labels. This
suggests its promising application for grounding UI elements and tasks with
similar requirements, not limited to the domain of scanned documents.

Overall, we can see that the Task AT2 was the easiest one for all models. In
this task, the model was required to decide if an element is to the right or
the left of the screen (considering a point in the middle). There is likely a
bias in the dataset that makes it easier to distinguish between elements on
the right or left of the screen.

Again, such bias can influence the interpretation of the results, given the
false interpretation that such models can understand positions such as left or
right. However, such a conclusion for BERT and RoBERTa is impracticable, given
that they are unable to encode positions. The probing framework provided here
can be applied to verify the quality of datasets used for grounding UI
elements.

## Conclusion

This paper presents an analysis of the UI grounding capabilities of three pre-
trained models: LayoutLM, BERT and RoBERTa. This analysis is performed in two
parts: the first is a traditional analysis of the task accuracy, while in the
second part, we perform a more profound analysis of the spatial reasoning
performed by such models using probing techniques.

The results presented in this work highlights the need for datasets that go
beyond lexical matching, focusing more on challenging spatial reasoning. Even
though RicoSCA contains a substantial amount of spatially focused commands, it
is still a synthetic dataset with limited demonstration of the kinds of
complex descriptions that would occur in natural language instructions. There
is a need for human-generated datasets of this kind, but such datasets are
still challenging to obtain, especially those of a more natural variety (which
is critical for future applications such as accessibility tools).

Overall, We conclude that the greatest challenge in this area is the
interpretation of instructions which require relative spatial reasoning that
complicates the grounding task, binding it more tightly to a visual screen
state. While there is insufficient data to create strong models specifically
for UI grounding of natural language instructions that include spatial
descriptors, we have shown that document-based models such as LayoutLM learn a
reasonable amount of spatially-relevant features (supported by the probing
findings) that make them transferable to the UI grounding task.

## References

  * Alain and Bengio (2018) Alain, G.; and Bengio, Y. 2018.  Understanding intermediate layers using linear classifier probes.  arXiv:1610.01644.
  * Branavan, Silver, and Barzilay (2012) Branavan, S.; Silver, D.; and Barzilay, R. 2012.  Learning to win by reading manuals in a monte-carlo framework.  _Journal of Artificial Intelligence Research_ , 43: 661–704.
  * Branavan, Zettlemoyer, and Barzilay (2010) Branavan, S.; Zettlemoyer, L. S.; and Barzilay, R. 2010.  Reading between the lines: Learning to map high-level instructions to commands.  In _Proceedings of the 48th annual meeting of the association for computational linguistics_ , 1268–1277. Association for Computational Linguistics.
  * Deka et al. (2017) Deka, B.; Huang, Z.; Franzen, C.; Hibschman, J.; Afergan, D.; Li, Y.; Nichols, J.; and Kumar, R. 2017.  Rico: A Mobile App Dataset for Building Data-Driven Design Applications.  In _Proceedings of the 30th Annual Symposium on User Interface Software and Technology_ , UIST ’17.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 4171–4186. Minneapolis, Minnesota: Association for Computational Linguistics.
  * Ferreira et al. (2020) Ferreira, D.; Rozanova, J.; Dubba, K.; Zhang, D.; and Freitas, A. 2020.  On the Evaluation of Intelligent Process Automation.  _arXiv preprint arXiv:2001.02639_.
  * Ferreira et al. (2021) Ferreira, D.; Rozanova, J.; Thayaparan, M.; Valentino, M.; and Freitas, A. 2021\.  Does My Representation Capture X? Probe-Ably.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing: System Demonstrations_ , 194–201. Online: Association for Computational Linguistics.
  * Goldwasser and Roth (2011) Goldwasser, D.; and Roth, D. 2011.  Learning from natural instructions.  In _22nd International Joint Conference on Artificial Intelligence, IJCAI 2011_ , 1794–1800.
  * Hewitt and Liang (2019) Hewitt, J.; and Liang, P. 2019.  Designing and Interpreting Probes with Control Tasks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 2733–2743. Hong Kong, China: Association for Computational Linguistics.
  * Hewitt and Manning (2019a) Hewitt, J.; and Manning, C. D. 2019a.  A Structural Probe for Finding Syntax in Word Representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 4129–4138. Minneapolis, Minnesota: Association for Computational Linguistics.
  * Hewitt and Manning (2019b) Hewitt, J.; and Manning, C. D. 2019b.  A Structural Probe for Finding Syntax in Word Representations.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 4129–4138. Minneapolis, Minnesota: Association for Computational Linguistics.
  * Li et al. (2020) Li, Y.; He, J.; Zhou, X.; Zhang, Y.; and Baldridge, J. 2020.  Mapping Natural Language Instructions to Mobile UI Action Sequences.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 8198–8210.
  * Liu et al. (2019) Liu, Y.; Ott, M.; Goyal, N.; Du, J.; Joshi, M.; Chen, D.; Levy, O.; Lewis, M.; Zettlemoyer, L.; and Stoyanov, V. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * MacGlashan et al. (2014) MacGlashan, J.; Littman, M.; Loftin, R.; Peng, B.; Roberts, D.; and Taylor, M. 2014\.  Training an agent to ground commands with reward and punishment.  In _Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence_.
  * Pasupat et al. (2018) Pasupat, P.; Jiang, T.-S.; Liu, E.; Guu, K.; and Liang, P. 2018.  Mapping natural language commands to web elements.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , 4970–4976.
  * Pimentel et al. (2020a) Pimentel, T.; Saphra, N.; Williams, A.; and Cotterell, R. 2020a.  Pareto Probing: Trading Off Accuracy for Complexity.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 3138–3153. Online: Association for Computational Linguistics.
  * Pimentel et al. (2020b) Pimentel, T.; Saphra, N.; Williams, A.; and Cotterell, R. 2020b.  Pareto Probing: Trading Off Accuracy for Complexity.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 3138–3153. Online: Association for Computational Linguistics.
  * Pimentel et al. (2020c) Pimentel, T.; Valvoda, J.; Hall Maudslay, R.; Zmigrod, R.; Williams, A.; and Cotterell, R. 2020c.  Information-Theoretic Probing for Linguistic Structure.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 4609–4622. Online: Association for Computational Linguistics.
  * Voita et al. (2019) Voita, E.; Talbot, D.; Moiseev, F.; Sennrich, R.; and Titov, I. 2019.  Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Pruned.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , 5797–5808. Florence, Italy: Association for Computational Linguistics.
  * Voita and Titov (2020) Voita, E.; and Titov, I. 2020.  Information-Theoretic Probing with Minimum Description Length.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 183–196. Online: Association for Computational Linguistics.
  * Volkova et al. (2013) Volkova, S.; Choudhury, P.; Quirk, C.; Dolan, B.; and Zettlemoyer, L. 2013.  Lightly supervised learning of procedural dialog systems.  In _Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 1669–1679.
  * Vulić et al. (2020) Vulić, I.; Ponti, E. M.; Litschko, R.; Glavaš, G.; and Korhonen, A. 2020\.  Probing Pretrained Language Models for Lexical Semantics.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 7222–7240. Online: Association for Computational Linguistics.
  * Xu et al. (2020) Xu, Y.; Li, M.; Cui, L.; Huang, S.; Wei, F.; and Zhou, M. 2020.  Layoutlm: Pre-training of text and layout for document image understanding.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 1192–1200.
  * Zhang and Bowman (2018) Zhang, K.; and Bowman, S. 2018.  Language Modeling Teaches You More than Translation Does: Lessons Learned Through Auxiliary Syntactic Task Analysis.  In _Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , 359–361. Brussels, Belgium: Association for Computational Linguistics.