# The Complexity of Distance-$r$ Dominating Set Reconfiguration

Niranka Banerjee1 Duc A. Hoang2

( 1 Research Institute of Mathematical Sciences, Kyoto University, Japan
<EMAIL_ADDRESS>
2 VNU University of Science, Vietnam National University, Hanoi, Vietnam
<EMAIL_ADDRESS>)

###### Abstract

For a fixed integer $r\geq 1$, a distance-$r$ dominating set of a graph
$G=(V,E)$ is a vertex subset $D\subseteq V$ such that every vertex in $V$ is
within distance $r$ from some member of $D$. Given two distance-$r$ dominating
sets $D_{s},D_{t}$ of $G$, the Distance-$r$ Dominating Set Reconfiguration
(D$r$DSR) problem asks if there is a sequence of distance-$r$ dominating sets
that transforms $D_{s}$ into $D_{t}$ (or vice versa) such that each
intermediate member is obtained from its predecessor by applying a given
reconfiguration rule exactly once. The problem for $r=1$ has been well-studied
in the literature. We consider D$r$DSR for $r\geq 2$ under two well-known
reconfiguration rules: Token Jumping ($\mathsf{TJ}$, which involves replacing
a member of the current D$r$DS by a non-member) and Token Sliding
($\mathsf{TS}$, which involves replacing a member of the current D$r$DS by an
adjacent non-member). We show that D$r$DSR ($r\geq 2$) is
$\mathtt{PSPACE}$-complete under both $\mathsf{TJ}$ and $\mathsf{TS}$ on
bipartite graphs, planar graphs of maximum degree six and bounded bandwidth,
and chordal graphs. On the positive side, we show that D$r$DSR ($r\geq 2$) can
be solved in polynomial time on split graphs and cographs under both
$\mathsf{TS}$ and $\mathsf{TJ}$ and on trees and interval graphs under
$\mathsf{TJ}$. Along the way, we observe some properties of a shortest
reconfiguration sequence in split graphs when $r=2$, which may be of
independent interest.

Keywords: distance-$r$ dominating set, reconfiguration problem, computational
complexity, PSPACE-completeness, polynomial-time algorithm

2020 MSC: 05C85

##  1 Introduction

For the last few decades, reconfiguration problems have independently emerged
in different areas of computer science, including recreational mathematics
(e.g., games and puzzles), computational geometry (e.g., flip graphs of
triangulations), constraint satisfaction (e.g., solution space of Boolean
formulas), and even quantum complexity theory (e.g., ground state
connectivity), and so on [17, 10, 8, 3]. In a reconfiguration variant of a
computational problem (e.g., Satisfiability, Independent Set, Dominating Set,
Vertex-Coloring, etc.), two feasible solutions (e.g., satisfying truth
assignments, independent sets, dominating sets, proper vertex-colorings, etc.)
$S$ and $T$ are given along with a reconfiguration rule that describes how to
slightly modify one feasible solution to obtain a new one. The question is
whether one can transform/reconfigure $S$ into $T$ via a sequence of feasible
solutions such that each intermediate member is obtained from its predecessor
by applying the given rule exactly once. Such a sequence, if exists, is called
a reconfiguration sequence.

In 1975, Meir and Moon [24] combined the concepts of “distance” and
“domination” in graphs and introduced the so-called distance-$r$ dominating
set of a graph (which they called a “$r$-covering”), where $r\geq 1$ is some
fixed integer. For a fixed positive integer $r$ and a graph $G$, a
distance-$r$ dominating set (D$r$DS) (also known as $r$-hop dominating set or
$r$-basis) of $G$ is a vertex subset $D$ where each vertex of $G$ is within
distance $r$ from some member of $D$. In particular, a D$1$DS is nothing but a
dominating set of $G$. Given a graph $G$ and some positive integer $k$, the
Distance-$r$ Dominating Set problem asks if there is a D$r$DS of $G$ of size
at most $k$. Distance-$r$ Dominating Set remains ${\mathtt{NP}}$-complete even
on bipartite graphs or chordal graphs of diameter $2r+1$ [22]. Since the work
of Meir and Moon, this notion of distance domination in graphs has been
extensively studied from different perspectives. We refer readers to the
survey of Henning [7] for more details.

Reconfiguration of dominating sets has been well-studied in the literature
from both algorithmic and graph-theoretic viewpoints. We briefly mention here
some well-known algorithmic results and refer readers to [8] for recent
developments from the graph-theoretic perspective. Imagine that a token is
placed on each vertex of a dominating set of a graph $G$ and no vertex has
more than one token. In a reconfiguration setting for dominating sets, the
following reconfiguration rules have been considered.

  * •

Token Sliding (${\mathsf{TS}}$): one can move a token to one of its unoccupied
neighbors as long as the resulting token-set forms a dominating set.

  * •

Token Jumping (${\mathsf{TJ}}$): one can move a token to any unoccupied vertex
as long as the resulting token-set forms a dominating set.

  * •

Token Addition/Removal (${\mathsf{TAR}}(k)$): one can either add or remove a
token as long as the resulting token-set forms a dominating set of size at
most some threshold $k\geq 0$.

Haddadan et al. [14] first studied the computational complexity of Dominating
Set Reconfiguration (DSR) under ${\mathsf{TAR}}$ and showed that the problem
is ${\mathtt{PSPACE}}$-complete on planar graphs of maximum degree six,
bounded bandwidth graphs, split graphs and bipartite graphs. On the positive
side, they designed polynomial-time algorithms for solving DSR under
${\mathsf{TAR}}$ on cographs, forests, and interval graphs. Bonamy et al. [4]
observed that the ${\mathsf{TJ}}$ and ${\mathsf{TAR}}$ rules are equivalent
under some constraints, and therefore the above-mentioned results indeed hold
for DSR under ${\mathsf{TJ}}$. Bonamy et al. [4] first studied the
computational complexity of DSR under ${\mathsf{TS}}$ and showed that the
hardness results of Haddadan et al. [14] hold even under ${\mathsf{TS}}$. On
the positive side, Bonamy et al. [4] designed polynomial-time algorithms for
solving DSR under ${\mathsf{TS}}$ on cographs and dually chordal graphs (which
contains trees and interval graphs). Bousquet and Joffard [5] later showed
that DSR under ${\mathsf{TS}}$ is ${\mathtt{PSPACE}}$-complete on circle
graphs and can be solved in polynomial time on circular-arc graphs, answering
some open questions previously asked by Bonamy et al. [4]. Recently, Křišt’an
and Svoboda [1] improved the positive results of Bonamy et al. [4] by showing
polynomial-time algorithms to find a shortest reconfiguration sequence, if
exists, between two given dominating sets under ${\mathsf{TS}}$ when the input
graph is either a tree or an interval graph. However, their techniques cannot
be extended to dually chordal graphs.

A systematic study on the parameterized complexity of several reconfiguration
problems, including DSR, was initiated by Mouawad et al. [13]. There are two
natural parameterizations: the number of tokens $k$ and the length of a
reconfiguration sequence $\ell$. In [13], Mouawad et al. showed that DSR under
${\mathsf{TAR}}$ on general graphs is $\mathtt{W[1]}$-hard parameterized by
$k$ and $\mathtt{W[2]}$-hard parameterized by $k+\ell$. When parameterized by
$k$ on graphs excluding $K_{d,d}$ as a subgraph for any constant $d$
(including bounded degeneracy and nowhere dense graphs), Lokshtanov et al. [9]
designed an $\mathtt{FPT}$ algorithm for solving the problem. When
parameterized by $\ell$ alone, it was mentioned in [3] that the problem is
fixed-parameter tractable on any class where first-order model-checking is
fixed-parameter tractable. We refer readers to [9, 3] and the references
therein for more details.

To the best of our knowledge, for some fixed integer $r\geq 2$, the
computational complexity of Distance-$r$ Dominating Set Reconfiguration
(D$r$DSR) has not yet been studied. On the other hand, from the parameterized
complexity viewpoint, Siebertz [11] studied D$r$DSR under ${\mathsf{TAR}}$
parameterized by $k$ and proved that there exists a constant $r$ such that the
problem is $\mathtt{W[2]}$-hard on somewhere dense graphs which are close
under taking subgraphs. On the positive side, Siebertz showed that the problem
is in $\mathtt{FPT}$ on nowhere dense graphs. From the graph-theoretic
viewpoint, DeVos et al. [6] introduced the $\gamma_{r}$-graph of a graph $G$—a
(reconfiguration) graph whose nodes are minimum distance-$r$ dominating sets
of $G$ and two nodes are adjacent if one can be obtained from the other by
applying a single ${\mathsf{TJ}}$-move—and proved a number of results on its
realizability. In this paper, to obtain a better understanding of the
separating line between “hard” and “easy” instances of D$r$DSR ($r\geq 2$) on
different graphs, we study the problem under ${\mathsf{TS}}$ and
${\mathsf{TJ}}$ from the computational complexity viewpoint. (The definitions
of these rules are similar to those for DSR.)

### Our Results

In Section 3, we prove hardness results of D$r$DSR in different graph classes.
We show that most of the hardness results of Haddadan et al. [14] and Bonamy
et al. [4] for $r=1$ can be extended for fixed integer $r\geq 2$ under both
${\mathsf{TS}}$ and ${\mathsf{TJ}}$. In Section 3.1, we show that D$r$DSR
($r\geq 2$) is ${\mathtt{PSPACE}}$-complete on bipartite graphs (Theorem 1).
In Section 3.2 we show that D$r$DSR ($r\geq 2$) on planar graphs of maximum
degree six and bounded bandwidth is ${\mathtt{PSPACE}}$-complete. (Theorem 2).
Recall that Haddadan et al. [14] proved the ${\mathtt{PSPACE}}$-completeness
of D$r$DSR under ${\mathsf{TAR}}$ on split graphs (and therefore on chordal
graphs) for $r=1$. In Section 3.3, we show that for fixed integer $r\geq 2$,
D$r$DSR remains ${\mathtt{PSPACE}}$-complete on chordal graphs (Theorem 3)
under ${\mathsf{TS}}$ and ${\mathsf{TJ}}$. Note that all of our hardness
results also hold even when considering minimum D$r$DSs.

In Section 4, we prove some upper bound results of D$r$DSR in different graph
classes. In Sections 4.1 and 4.2, we prove some simple observations which then
imply that D$r$DSR can be solved in polynomial time under ${\mathsf{TJ}}$ on
interval graphs (Corollary 5) and under both ${\mathsf{TS}}$ and
${\mathsf{TJ}}$ on cographs (Corollary 7). In Section 4.3, we show that for
fixed integer $r\geq 2$, D$r$DSR can be solved in polynomial time on split
graphs under both ${\mathsf{TS}}$ and ${\mathsf{TJ}}$ (Theorem 9 and Corollary
10). This result provides a surprising dichotomy to the lower bound result on
split graphs of Haddadan et al. [14]. We also provide examples showing that
the natural lower bounds on the lengths of a shortest reconfiguration sequence
are sometimes not achievable on split graphs under both ${\mathsf{TS}}$ and
${\mathsf{TJ}}$ when $r=2$ (Theorems 11 and 12). In Section 4.4, we prove that
D$r$DSR under ${\mathsf{TJ}}$ on trees (and forests) can be solved in
polynomial time (Theorem 13). In short, we show that the positive results of
Haddadan et al. [14] for $r=1$ under ${\mathsf{TAR}}$ on cographs, forests,
and interval graphs also hold for fixed $r\geq 2$ under ${\mathsf{TJ}}$.

##  2 Preliminaries

For the concepts and notations not defined here, we refer readers to [12].
Unless otherwise mentioned, throughout this paper, we always consider simple,
connected, undirected graphs $G$ with vertex-set $V(G)$ and edge-set $E(G)$.
For any pair of vertices $u,v$, the distance between $u$ and $v$ in $G$,
denoted by $\mathsf{dist}_{G}(u,v)$, is the length of a shortest path between
them. For two vertex subsets $X,Y$, we use $X-Y$ and $X+Y$ to indicate
$X\setminus Y$ and $X\cup Y$, respectively. If $Y$ contains a single vertex
$u$, we write $X-u$ and $X+u$ instead of $X-\\{u\\}$ and $X+\\{u\\}$,
respectively. We denote by $X\Delta Y$ their symmetric difference, i.e.,
$X\Delta Y=(X-Y)+(Y-X)$. For a subgraph $H$ of $G$, we denote by $G-H$ the
graph obtained from $G$ by deleting all vertices of $H$ and their incident
edges in $G$.

A dominating set (DS) of $G$ is a vertex subset $D$ such that for every $u\in
V(G)$, there exists $v\in D$ such that $\mathsf{dist}_{G}(u,v)\leq 1$. For a
fixed positive integer $r$, a distance-$r$ dominating set (D$r$DS) of $G$ is a
vertex subset $D$ such that for every $v\in V(G)$, there exists $v\in D$ such
that $\mathsf{dist}_{G}(u,v)\leq r$. In particular, any D$1$DS is also a DS
and vice versa. Let $N^{r}_{G}[u]$ be the set of all vertices of distance at
most $r$ from $u$ in $G$. We say that a vertex $v$ is $r$-dominated by $u$ (or
$u$ $r$-dominates $v$) if $v\in N^{r}_{G}[u]$. We say that a vertex subset $X$
is $r$-dominated by some vertex subset $Y$ if each vertex in $X$ is
$r$-dominated by some vertex in $Y$. A D$r$DS is nothing but a vertex subset
$D$ that $r$-dominates $V(G)$. We denote by $\gamma_{r}(G)$ the size of a
minimum D$r$DS of $G$.

We say that $u$ covers the edge $e\in E(G)$ if $u$ is an endpoint of $e$. A
vertex cover (VC) of $G$ is a vertex subset $C$ such that for every edge
$uv\in E(G)$, either $u\in C$ or $v\in C$. Intuitively, vertices in $C$ cover
all edges of $G$. Observe that in a connected graph $G$, any VC is also a DS.
We denote by $\tau(G)$ the size of a minimum VC of $G$.

Throughout this paper, we write “$(G,D_{s},D_{t})$ under ${\mathsf{R}}$” to
indicate an instance of D$r$DSR where $D_{s}$ and $D_{t}$ are two given
D$r$DSs of a graph $G$ and the reconfiguration rule is
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$. Imagine that a token is
placed on each vertex in a D$r$DS of a graph $G$. A ${\mathsf{TS}}$-sequence
in $G$ between two D$r$DSs $D_{s}$ and $D_{t}$ is the sequence
$\mathcal{S}=\langle D_{s}=D_{0},D_{1},\dots,D_{q}=D_{t}\rangle$ such that for
$i\in\\{0,\dots,q-1\\}$, the set $D_{i}$ is a D$r$DS of $G$ and there exists a
pair $x_{i},y_{i}\in V(G)$ such that $D_{i}-D_{i+1}=\\{x_{i}\\}$,
$D_{i+1}-D_{i}=\\{y_{i}\\}$, and $x_{i}y_{i}\in E(G)$. A
${\mathsf{TJ}}$-sequence in $G$ can be defined similarly without the
restriction $x_{i}y_{i}\in E(G)$. Depending on the considered rule
${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$, we can also say that
$D_{i+1}$ is obtained from $D_{i}$ by immediately sliding/jumping a token from
$x_{i}$ to $y_{i}$ and write
$x_{i}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{i}$. Thus, we can also
write $\mathcal{S}=\langle
x_{0}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{0},\dots,x_{q-1}\overset{G}{\longrightarrow}_{{\mathsf{R}}}y_{q-1}\rangle$.
In short, $\mathcal{S}$ can be viewed as a (ordered) sequence of either
D$r$DSs or token-moves. (Recall that we defined $\mathcal{S}$ as a sequence
between $D_{s}$ and $D_{t}$. As a result, when regarding $\mathcal{S}$ as a
sequence of token-moves, we implicitly assume that the initial D$r$DS is
$D_{s}$.) With respect to the latter viewpoint, we say that $\mathcal{S}$
slides/jumps a token $t$ from $u$ to $v$ in $G$ if $t$ is originally placed on
$u\in D_{0}$ and finally on $v\in D_{q}$ after performing $\mathcal{S}$. The
length of a ${\mathsf{R}}$-sequence is simply the number of times the rule
${\mathsf{R}}$ is applied. Additionally, the length of a shortest
${\mathsf{R}}$-sequence in $G$ between two D$r$DSs $D_{s}$ and $D_{t}$ is
denoted by $\mathsf{OPT}_{{\mathsf{R}}}(G,D_{s},D_{t})$.

##  3 Hardness Results

We begin this section with the following simple observation. It is well-known
that for any computational problem in ${\mathtt{NP}}$, any of its
reconfiguration variants is in ${\mathtt{PSPACE}}$ [18][Theorem 1]. As a
result, when proving the ${\mathtt{PSPACE}}$-completeness of D$r$DSR on a
certain graph class, it suffices to show a polynomial-time reduction.

###  3.1 Bipartite Graphs

######  Theorem 1.

D$r$DSR under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ on bipartite
graphs is ${\mathtt{PSPACE}}$-complete for any $r\geq 2$.

###### Proof.

We give a polynomial-time reduction from Minimum Vertex Cover Reconfiguration
(M-VCR) on general graphs, which was showed to be ${\mathtt{PSPACE}}$-complete
by Ito et al. [18]. Our reduction extends the one given by Bonamy et al. [4]
for the case $r=1$. Let $(G,C_{s},C_{t})$ be an instance of M-VCR under
${\mathsf{R}}$ where $C_{s},C_{t}$ are two minimum VCs of a graph $G$. We will
construct an instance $(G^{\prime},D_{s},D_{t})$ of D$r$DSR under
${\mathsf{R}}$ where $D_{s}$ and $D_{t}$ are two D$r$DSs of a bipartite graph
$G^{\prime}$.

Suppose that $V(G)=\\{v_{1},\dots,v_{n}\\}$. We construct $G^{\prime}$ from
$G$ as follows.

  1. (a)

Replace each edge $v_{i}v_{j}$ by a path $P_{ij}=x_{ij}^{0}x_{ij}^{1}\dots
x_{ij}^{2r}$ of length $2r$ ($1\leq i,j\leq n$) with $x_{ij}^{0}=v_{i}$ and
$x_{ij}^{2r}=v_{j}$. Observe that $x_{ij}^{p}=x_{ji}^{2r-p}$ for $0\leq p\leq
2r$.

  2. (b)

Add a new vertex $x$ and join it to every vertex in $V(G)$.

  3. (c)

Attach a new path $P_{x}$ of length $r$ to $x$.

We define $D_{s}=C_{s}+x$ and $D_{t}=C_{t}+x$. Clearly, this construction can
be done in polynomial time. (See Figure 1.)

Figure 1: An example of constructing a bipartite graph $G^{\prime}$ from a
graph $G$ when $r=2$ in the proof of Theorem 1.

In the next two claims, we prove that our construction results in an instance
of D$r$DSR on bipartite graphs: Claim 1.1 shows that $G^{\prime}$ is bipartite
and Claim 1.2 implies that both $D_{s}$ and $D_{t}$ are minimum D$r$DSs of
$G^{\prime}$.

######  Claim 1.1.

$G^{\prime}$ is a bipartite graph.

###### Proof.

We show that any cycle $\mathcal{C}^{\prime}$ in $G^{\prime}$ has even length
and therefore $G^{\prime}$ is bipartite. Observe that no cycle of $G^{\prime}$
contains a vertex from $V(P_{x})-x$. From the construction, if
$\mathcal{C}^{\prime}$ does not contain $x$, it follows that
$V(\mathcal{C}^{\prime})\cap V(G)$ must form a cycle $\mathcal{C}$ of $G$.
Therefore, $\mathcal{C}^{\prime}$ is of length $2r|E(\mathcal{C})|$, which is
even. On the other hand, if $\mathcal{C^{\prime}}$ contains $x$, it follows
that $V(\mathcal{C}^{\prime})\cap V(G)$ must form a path $\mathcal{P}$ of $G$.
Therefore, $\mathcal{C}^{\prime}$ is of length $2+2r|E(\mathcal{P})|$, which
again is even. ∎

######  Claim 1.2.

Any set of the form $C+x$, where $C$ is a minimum VC of $G$, is a minimum
D$r$DS of $G^{\prime}$.

###### Proof.

To see this, note that, by construction, $x$ $r$-dominates every vertex in
$V(G^{\prime})-\bigcup_{v_{i}v_{j}\in E(G)}\\{x_{ij}^{r}\\}$. Additionally,
since each $x_{ij}^{r}$ belongs to exactly one path $P_{ij}$ and $C$ is a
minimum VC of $G$, it follows that $C$ $r$-dominates $\bigcup_{v_{i}v_{j}\in
E(G)}\\{x_{ij}^{r}\\}$. Thus, $C+x$ $r$-dominates $V(G^{\prime})$, i.e., $C+x$
is a D$r$DS of $G^{\prime}$.

It remains to show that $C+x$ is minimum. Indeed, it is sufficient to show
that $\tau(G)+1=\gamma_{r}(G^{\prime})$ where $\tau(G)$ and
$\gamma_{r}(G^{\prime})$ are respectively the size of a minimum VC of $G$ and
a minimum D$r$DS of $G^{\prime}$. Since $C+x$ is a D$r$DS of $G^{\prime}$, we
have $\tau(G)+1=|C|+x\geq\gamma_{r}(G^{\prime})$. On the other hand, note that
any minimum D$r$DS $D^{\prime}$ of $G^{\prime}$ must $r$-dominate $V(P_{x})$
and therefore contains a vertex of $P_{x}$ (which, by the construction, does
not belong to $G$). Moreover, from the construction of $G^{\prime}$, each path
$P_{ij}$ ($1\leq i,j\leq n$ and $v_{i}v_{j}\in E(G)$) is of length $2r$. Thus,
in order to $r$-dominate all $V(P_{ij})$, $D^{\prime}$ needs to contain at
least one vertex from each path $P_{ij}$. Therefore,
$\gamma_{r}(G^{\prime})=|D^{\prime}|\geq 1+\tau(G)$. Our proof is complete. ∎

Before proving the correctness of our reduction, we prove some useful
observations.

######  Claim 1.3.

Let $D=C+x$ be a D$r$DS of $G^{\prime}$ where $C$ is a minimum VC of $G$.
Then,

  1. (a)

$D-u+y$ is not a D$r$DS of $G^{\prime}$, for any $u\in C$ and $y\in
V(P_{x})-x$.

  2. (b)

$D-x+v$ is not a D$r$DS of $G^{\prime}$, for any $v\in V(G^{\prime})-x$.

  3. (c)

$D-u+z$ is not a D$r$DS of $G^{\prime}$, for $u=v_{i}\in C$ and
$z\notin\bigcup_{\\{j\mid v_{j}\in N_{G}(v_{i})-C\\}}V(P_{ij})$.

###### Proof.

  1. (a)

Suppose to the contrary there exists $u\in C$ and $y\in V(P_{x})-x$ such that
$D^{\prime}=D-u+y$ is a D$r$DS of $G^{\prime}$. Since
$|D^{\prime}|=|D|=\tau(G)+1$, Claim 1.2 implies that $D^{\prime}$ is a minimum
D$r$DS of $G^{\prime}$. On the other hand, from the construction of
$G^{\prime}$, any vertex $r$-dominated by $y$ must also be $r$-dominated by
$x$. Thus, $D^{\prime}-y$ is also a D$r$DS of $G^{\prime}$, which is a
contradiction.

  2. (b)

Suppose to the contrary there exists $v\in V(G^{\prime})-x$ such that
$D^{\prime}=D-x+v$ is a D$r$DS of $G^{\prime}$. From (a), it follows that
$v\in V(P_{x})-x$; otherwise some vertex of $P_{x}$ would not be $r$-dominated
by any member of $D^{\prime}$. Since $C$ is a minimum VC of $G$, it follows
that there exists a pair $i,j\in\\{1,\dots,n\\}$ such that $v_{i}v_{j}\in
E(G)$ and $C\cap\\{v_{i},v_{j}\\}=\\{v_{i}\\}$; otherwise every vertex of $G$
would contain a token in $C$ and therefore $C$ would not be minimum—a
contradiction. From the construction of $G^{\prime}$, $x$ is the unique vertex
in $V(P_{x})$ that $r$-dominates $x_{ij}^{r+1}$. Thus, $x_{ij}^{r+1}$ is not
$r$-dominated by any vertex in $D^{\prime}=D-x+v$ for $v\in V(P_{x})-x$, which
is a contradiction.

  3. (c)

Let $j\in\\{1,\dots,n\\}$ be such that $v_{j}\in N_{G}(u)-C=N_{G}(v_{i})-C$.
Since $C$ is a minimum VC of $G$, such a vertex $v_{j}$ must exist. From the
construction of $G^{\prime}$, the vertex $u=v_{i}$ is the unique vertex in $D$
that $r$-dominates $x_{ij}^{r}$. Thus, in order to keep $x_{ij}^{r}$ being
$r$-dominated, a token on $u$ can only be moved to some vertex in
$\bigcup_{\\{j\mid v_{j}\in N_{G}(v_{i})-C\\}}V(P_{ij})$.

∎

Intuitively, starting from a token-set of the form $C+x$ for some minimum VC
$C$ of $G$, Claim 1.3(a) means that as long as $x$ has a token, no other token
can be moved in $G^{\prime}$ to a vertex in $P_{x}-x$, Claim 1.3(b) implies
that if $x$ has a token, it will never be moved in $G^{\prime}$, and Claim
1.3(c) says that a token cannot be moved in $G^{\prime}$ “too far” from its
original position.

We are now ready to show the correctness of our reduction. (Claims 1.4 and
1.5.)

######  Claim 1.4.

Under ${\mathsf{TS}}$, $(G,C_{s},C_{t})$ is a yes-instance if and only if
$(G^{\prime},D_{s},D_{t})$ is a yes-instance.

###### Proof.

  * ($\Rightarrow$)

Suppose that ${\mathcal{S}}$ is a ${\mathsf{TS}}$-sequence in $G$ between
$C_{s}$ and $C_{t}$. We construct a sequence ${\mathcal{S}}^{\prime}$ of
token-slides in $G^{\prime}$ between $D_{s}$ and $D_{t}$ by replacing each
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ in ${\mathcal{S}}$
with the sequence ${\mathcal{S}}_{ij}=\langle
v_{i}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}x_{ij}^{1},x_{ij}^{1}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}x_{ij}^{2},\dots,x_{ij}^{2r-1}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}x_{ij}^{2r}\rangle$,
where $i,j\in\\{1,\dots,n\\}$ and $v_{i}v_{j}\in E(G)$. Intuitively, sliding a
token $t_{ij}$ from $v_{i}$ to its neighbor $v_{j}$ in $G$ corresponds to
sliding $t_{ij}$ from $v_{i}$ to $v_{j}$ in $G^{\prime}$ along the path
$P_{ij}$. Since $x$ always $r$-dominates $V(G^{\prime})-\bigcup_{v_{i}v_{j}\in
E(G)}\\{x_{ij}^{r}\\}$ and after each move in ${\mathcal{S}}_{ij}$ the token
$t_{ij}$ always $r$-dominates $x_{ij}^{r}$, it follows that
${\mathcal{S}}_{ij}$ is indeed a ${\mathsf{TS}}$-sequence in $G^{\prime}$.
Thus, ${\mathcal{S}}^{\prime}$ is our desired ${\mathsf{TS}}$-sequence.

  * ($\Leftarrow$)

Let ${\mathcal{S}}^{\prime}$ be a ${\mathsf{TS}}$-sequence in $G^{\prime}$
between $D_{s}$ and $D_{t}$. We describe how to construct a
${\mathsf{TS}}$-sequence ${\mathcal{S}}$ in $G$ between $C_{s}$ and $C_{t}$.
Initially, ${\mathcal{S}}=\emptyset$. For each move
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}v$ ($u\neq v$) in
${\mathcal{S}}^{\prime}$, we consider the following cases:

    1. Case 1:

Either $u\in V(P_{x})$ or $v\in V(P_{x})$. Since ${\mathcal{S}}^{\prime}$
starts with $D_{s}=C_{s}+x$, Claim 1.3 ensures that no token can be placed on
some vertex in $P_{x}-x$ and $x$ always contains a token. As a result, this
case does not happen.

    2. Case 2:

$u=x_{ij}^{p}$ and $v=x_{ij}^{p+1}$ for $0\leq p\leq 2r$. Recall that
$x_{ij}^{0}=v_{i}$ and $x_{ij}^{2r}=v_{j}$. Additionally, from our
construction, since $x_{ij}^{p}$ has a token, so does $v_{i}$. If $p=2r-1$,
append the move $v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ to
${\mathcal{S}}$. Otherwise, do nothing.

To see that ${\mathcal{S}}$ is indeed a ${\mathsf{TS}}$-sequence in $G$, it
suffices to show that if $C$ is the minimum VC obtained right before the move
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ then
$C^{\prime}=C-v_{i}+v_{j}$ is also a minimum VC of $G$. Suppose to the
contrary that $C^{\prime}$ is not a vertex cover of $G$. It follows that there
exists $k\in\\{1,\dots,n\\}$ such that $v_{i}v_{k}\in E(G)$, $v_{k}\neq
v_{j}$, and $v_{k}\notin C$. Intuitively, the edge $v_{i}v_{k}$ is not covered
by any vertex in $C^{\prime}$. On the other hand, let $D$ be the D$r$DS of
$G^{\prime}$ obtained right before the move
$x_{ij}^{2r-1}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}x_{ij}^{2r}=v_{j}$.
Since $D^{\prime}=D-x_{ij}^{2r-1}+x_{ij}^{2r}$ is also a D$r$DS of
$G^{\prime}$, there must be some vertex in $D^{\prime}$ that $r$-dominates
$x_{ik}^{r}$, which implies $V(P_{ik})\cap D^{\prime}\neq\emptyset$. However,
from the construction of ${\mathcal{S}}$, it follows that $v_{k}\in C$, which
is a contradiction. Thus, $C^{\prime}$ is a vertex cover of $G$. Since
$|C^{\prime}|=|C|$, it is also minimum.

∎

######  Claim 1.5.

Under ${\mathsf{TJ}}$, $(G,C_{s},C_{t})$ is a yes-instance if and only if
$(G^{\prime},D_{s},D_{t})$ is a yes-instance.

###### Proof.

  * ($\Rightarrow$)

Suppose that ${\mathcal{S}}$ is a ${\mathsf{TJ}}$-sequence in $G$ between
$C_{s}$ and $C_{t}$. It follows from Claim 1.2 that the sequence
${\mathcal{S}}^{\prime}$ of token-jumps obtained from ${\mathcal{S}}$ by
replacing each move $u\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}v$ in
${\mathcal{S}}$ by $u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}v$
is a ${\mathsf{TJ}}$-sequence between $D_{s}=C_{s}+x$ and $D_{t}=C_{t}+x$.

  * ($\Leftarrow$)

On the other hand, let ${\mathcal{S}}^{\prime}$ be a ${\mathsf{TJ}}$-sequence
in $G^{\prime}$ between $D_{s}$ and $D_{t}$. We describe how to construct a
${\mathsf{TJ}}$-sequence ${\mathcal{S}}$ in $G$ between $C_{s}$ and $C_{t}$.
Initially, ${\mathcal{S}}=\emptyset$. For each move
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}v$ ($u\neq v$) in
${\mathcal{S}}^{\prime}$, we consider the following cases:

    1. Case 1:

Either $u\in V(P_{x})$ or $v\in V(P_{x})$. As before, it follows from Claim
1.3 that this case does not happen.

    2. Case 2:

$u=x_{ij}^{p}$ and $v=x_{ij}^{q}$ for $0\leq p,q\leq 2r$. Recall that
$x_{ij}^{0}=v_{i}$ and $x_{ij}^{2r}=v_{j}$. If $q=2r$, append the move
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}v_{j}$ to ${\mathcal{S}}$.
Otherwise, do nothing.

    3. Case 3:

$u=x_{ij}^{p}$ and $v=x_{k\ell}^{q}$ for two edges $v_{i}v_{j}$ and
$v_{k}v_{\ell}$ in $G$ and $0\leq p,q\leq 2r$. Note that if ($\star$)
$v_{i}v_{j}$ and $v_{k}v_{\ell}$ are adjacent edges in $G$ and either $u$ or
$v$ is their common endpoint, we are back to Case 2. Thus, let’s assume
($\star$) does not happen and consider the first move of this type. From Claim
1.3, it must happen that before the move
$x_{ij}^{p}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}x_{k\ell}^{q}$,
some move in ${\mathcal{S}}$ places a token on $u=x_{ij}^{p}$ and moreover
such a token must come from either $v_{i}$ or $v_{j}$. Additionally, again by
Claim 1.3, if the token comes from $v_{i}$ then $v_{j}$ contains no other
token, and vice versa. Let $D$ be the D$r$DS obtained right before the move
$x_{ij}^{p}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}x_{k\ell}^{q}$.
Now, since
$x_{ij}^{p}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}x_{k\ell}^{q}$
is the first move of its type, it follows that the path $P_{ij}$ contains
exactly one token from $D$ which is placed on $x_{ij}^{p}$. However, this
means we cannot perform
$x_{ij}^{p}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}x_{k\ell}^{q}$,
otherwise $x_{ij}^{r}$ would not be $r$-dominated by the resulting token-set.
Thus, this case does not happen unless ($\star$) is satisfied.

To see that ${\mathcal{S}}$ is indeed a ${\mathsf{TJ}}$-sequence in $G$, it
suffices to show that if $C$ is the minimum VC obtained right before the move
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}v_{j}$ then
$C^{\prime}=C-v_{i}+v_{j}$ is also a minimum VC of $G$. Suppose to the
contrary that $C^{\prime}$ is not a vertex cover of $G$. It follows that there
exists $k\in\\{1,\dots,n\\}$ such that $v_{i}v_{k}\in E(G)$, $v_{k}\neq
v_{j}$, and $v_{k}\notin C$. Intuitively, the edge $v_{i}v_{k}$ is not covered
by any vertex in $C^{\prime}$. On the other hand, let $D$ be the D$r$DS of
$G^{\prime}$ obtained right before the move
$x_{ij}^{p}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}x_{ij}^{2r}=v_{j}$.
Since $D^{\prime}=D-x_{ij}^{p}+x_{ij}^{2r}$ is also a D$r$DS of $G^{\prime}$,
there must be some vertex in $D^{\prime}$ that $r$-dominates $x_{ik}^{r}$,
which implies $V(P_{ik})\cap D^{\prime}\neq\emptyset$. However, from the
construction of ${\mathcal{S}}$, it follows that $v_{k}\in C$, which is a
contradiction. Thus, $C^{\prime}$ is a vertex cover of $G$. Since
$|C^{\prime}|=|C|$, it is also minimum.

∎

Our proof is complete. ∎

###  3.2 Planar Graphs

######  Theorem 2.

D$r$DSR under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ on planar
graphs of maximum degree six and bounded bandwidth is
${\mathtt{PSPACE}}$-complete for any $r\geq 2$.

###### Proof.

We give a polynomial-time reduction from Minimum Vertex Cover Reconfiguration
(M-VCR) on planar graphs of maximum degree three and bounded bandwidth, which
was (implicitly) showed to be ${\mathtt{PSPACE}}$-complete in the works of
Hearn and Demaine [19] and van der Zanden [16]111Hearn and Demaine [19] proved
that Independent Set Reconfiguration is ${\mathtt{PSPACE}}$-complete on planar
graphs of maximum degree three and later van der Zanden extended their results
for those graphs with the additional “bounded bandwidth” restriction. Since
their proofs only involve maximum independent sets, the same results hold for
minimum vertex covers.. Our reduction extends the classic reduction from
Vertex Cover to Dominating Set [23]. This reduction has also been modified for
showing the hardness of the problem for $r=1$ (i.e., Dominating Set
Reconfiguration) by Haddadan et al. [14] under ${\mathsf{TAR}}$ and later by
Bonamy et al. [4] under ${\mathsf{TS}}$. Let $(G,C_{s},C_{t})$ be an instance
of M-VCR under ${\mathsf{R}}$ where $C_{s},C_{t}$ are two minimum VCs of a
planar graph $G$ of maximum degree three and bounded bandwidth. We will
construct an instance $(G^{\prime},D_{s},D_{t})$ of D$r$DSR under
${\mathsf{R}}$ where $D_{s}$ and $D_{t}$ are two D$r$DSs of a planar graph
$G^{\prime}$ of maximum degree three and bounded bandwidth.

Suppose that $V(G)=\\{v_{1},\dots,v_{n}\\}$. We construct $G^{\prime}$ from
$G$ as follows. For each edge $v_{i}v_{j}\in E(G)$, add a new path
$P_{ij}=x_{ij}^{0}x_{ij}^{1}\dots,x_{ij}^{2r}$ of length $2r$ ($1\leq i,j\leq
n$) with $x_{ij}^{0}=v_{i}$ and $x_{ij}^{2r}=v_{j}$. Observe that
$x_{ij}^{p}=x_{ji}^{2r-p}$ for $0\leq p\leq 2r$. Intuitively, $G^{\prime}$ is
obtained from $G$ by replacing each edge of $G$ by a cycle $\mathcal{C}_{ij}$
of length $2r+1$ formed by the path $P_{ij}$ and the edge $uv=v_{i}v_{j}$. We
define $D_{s}=C_{s}$ and $D_{t}=C_{t}$. Clearly, this construction can be done
in polynomial time. (See Figure 2.)

Figure 2: An example of constructing $G^{\prime}$ from a planar, subcubic, and
bounded bandwidth graph $G$ in the proof of Theorem 2. Vertices in
$V(G^{\prime})-V(G)$ are marked with the gray color. Each dotted path is of
length $r-1$.

It follows directly from the construction that $G^{\prime}$ is planar and has
maximum degree six and both $D_{s}$ and $D_{t}$ are D$r$DSs of $G^{\prime}$
(and so is any minimum VC of $G$). Moreover, $D_{s}$ and $D_{t}$, and in
general all minimum VCs of $G$, are also minimum D$r$DSs of $G^{\prime}$. To
see this, it suffices to prove that $\tau(G)=\gamma_{r}(G^{\prime})$ where
$\tau(G)$ and $\gamma_{r}(G^{\prime})$ are respectively the size of a minimum
VC of $G$ and a minimum D$r$DS of $G^{\prime}$. Since any minimum VC of $G$ is
also a D$r$DS of $G^{\prime}$, we have $\tau(G)\geq\gamma_{r}(G^{\prime})$. On
the other hand, from the construction of $G^{\prime}$, observe that for any
pair $i,j\in\\{1,\dots,n\\}$ with $v_{i}v_{j}\in E(G)$, the vertex
$x_{ij}^{r}$ (whose distance from both $v_{i}$ and $v_{j}$ is exactly $r$) can
only be $r$-dominated by some vertex in $V(\mathcal{C}_{ij})$, which implies
that one needs at least $\tau(G)$ tokens to $r$-dominate $V(G^{\prime})$.
Therefore, $\gamma_{r}(G^{\prime})\geq\tau(G)$.

Since the number of edges of $G^{\prime}$ is exactly $(2r+1)$ times the number
of edges of $G$, the bandwidth of $G^{\prime}$ increases (comparing to that of
$G$) only by a constant multiplicative factor, which implies that $G^{\prime}$
is a bounded bandwidth graph.

We are now ready to show the correctness of our reduction.

######  Claim 2.1.

Under ${\mathsf{TS}}$, $(G,C_{s},C_{t})$ is a yes-instance if and only if
$(G^{\prime},D_{s},D_{t})$ is a yes-instance.

###### Proof.

  * ($\Rightarrow$)

Let ${\mathcal{S}}$ be a ${\mathsf{TS}}$-sequence in $G$ between $C_{s}$ and
$C_{t}$. Since any minimum VC of $G$ is also a minimum D$r$DS of $G^{\prime}$,
the sequence ${\mathcal{S}}^{\prime}$ obtained by replacing each move
$u\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v$ in ${\mathcal{S}}$ by
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}v$ is also a
${\mathsf{TS}}$-sequence in $G^{\prime}$ between $D_{s}=C_{s}$ and
$D_{t}=C_{t}$.

  * ($\Leftarrow$)

Let ${\mathcal{S}}^{\prime}$ be a ${\mathsf{TS}}$-sequence in $G^{\prime}$
between $D_{s}$ and $D_{t}$. We construct a sequence of token-slides
${\mathcal{S}}$ in $G$ between $C_{s}=D_{s}$ and $C_{t}=D_{t}$ as follows.
Initially, ${\mathcal{S}}=\emptyset$. For each move
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}v$ in
${\mathcal{S}}^{\prime}$, we consider the following cases.

    1. Case 1:

$u\in V(G)$ and $v\in V(G)$. It must happen that $u=v_{i}$ and $v=v_{j}$ for
some $i,j\in\\{1,\dots,n\\}$ such that $v_{i}v_{j}\in E(G)$. We append
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ to ${\mathcal{S}}$.

    2. Case 2:

$u\in V(G)$ and $v\in V(G^{\prime})-V(G)$. Do nothing.

    3. Case 3:

$u\in V(G^{\prime})-V(G)$ and $v\in V(G)$. It must happen that
$u=x_{ij}^{2r-1}$ and $v=x_{ij}^{2r}=v_{j}$ for some $i,j\in\\{1,\dots,n\\}$
such that $v_{i}v_{j}\in E(G)$. We append
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ to ${\mathcal{S}}$.

    4. Case 4:

$u\in V(G^{\prime})-V(G)$ and $v\in V(G^{\prime})-V(G)$. Do nothing.

To see that ${\mathcal{S}}$ is indeed a ${\mathsf{TS}}$-sequence in $G$, it
suffices to show that if $C$ is the minimum VC obtained right before the move
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ in $G$ then
$C^{\prime}=C-v_{i}+v_{j}$ is also a minimum VC of $G$. If Case 1 happens,
this is trivial. Thus, it remains to consider the case Case 3 happens. In this
case, suppose to the contrary that $C^{\prime}$ is not a VC of $G$. It follows
that there exists $k\in\\{1,\dots,n\\}$ such that $v_{i}v_{k}\in E(G)$,
$v_{k}\neq v_{j}$, and $v_{k}\notin C$. Intuitively, the edge $v_{i}v_{k}$ is
not covered by any vertex in $C^{\prime}$. On the other hand, let $D$ be the
D$r$DS of $G^{\prime}$ obtained right before the move
$x_{ij}^{2r-1}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TS}}}x_{ij}^{2r}=v_{j}$.
Since $D^{\prime}=D-x_{ij}^{2r-1}+x_{ij}^{2r}$ is also a D$r$DS of
$G^{\prime}$, there must be some vertex in $D^{\prime}$ that $r$-dominates
$x_{ik}^{r}$, which implies $V(P_{ik})\cap D^{\prime}\neq\emptyset$. However,
from the construction of ${\mathcal{S}}$, it follows that $v_{k}\in C$, which
is a contradiction. Thus, $C^{\prime}$ is a vertex cover of $G$. Since
$|C^{\prime}|=|C|$, it is also minimum.

∎

######  Claim 2.2.

Under ${\mathsf{TJ}}$, $(G,C_{s},C_{t})$ is a yes-instance if and only if
$(G^{\prime},D_{s},D_{t})$ is a yes-instance.

###### Proof.

  * ($\Rightarrow$)

Let ${\mathcal{S}}$ be a ${\mathsf{TJ}}$-sequence in $G$ between $C_{s}$ and
$C_{t}$. Since any minimum VC of $G$ is also a minimum D$r$DS of $G^{\prime}$,
the sequence ${\mathcal{S}}^{\prime}$ obtained by replacing each move
$u\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}v$ in ${\mathcal{S}}$ by
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}v$ is also a
${\mathsf{TS}}$-sequence in $G^{\prime}$ between $D_{s}=C_{s}$ and
$D_{t}=C_{t}$.

  * ($\Leftarrow$)

Let ${\mathcal{S}}^{\prime}$ be a ${\mathsf{TJ}}$-sequence in $G^{\prime}$
between $D_{s}$ and $D_{t}$. We construct a sequence of token-jumps
${\mathcal{S}}$ in $G$ between $C_{s}=D_{s}$ and $C_{t}=D_{t}$ as follows.
Initially, ${\mathcal{S}}=\emptyset$. For each move
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}v$ in
${\mathcal{S}}^{\prime}$, we consider the following cases.

    1. Case 1:

$u\in V(G)$ and $v\in V(G)$. It must happen that $u=v_{i}$ and $v=v_{j}$ for
some $i,j\in\\{1,\dots,n\\}$. We append
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}v_{j}$ to ${\mathcal{S}}$.

    2. Case 2:

$u\in V(G)$ and $v\in V(G^{\prime})-V(G)$. Do nothing.

    3. Case 3:

$u\in V(G^{\prime})-V(G)$ and $v\in V(G)$. From the construction of
$G^{\prime}$, for each pair $i,j\in\\{1,\dots,n\\}$ such that $v_{i}v_{j}\in
E(G)$, the vertex $x_{ij}^{r}$ must be $r$-dominated by at least one vertex of
$\mathcal{C}_{ij}$. Additionally, note that any token-set resulting from a
move in ${\mathcal{S}}^{\prime}$ must be a minimum D$r$DS of $G^{\prime}$.
Thus, we must have $u=x_{ij}^{p}$ and $v=x_{ij}^{2r}=v_{j}$ for some
$i,j\in\\{1,\dots,n\\}$ such that $v_{i}v_{j}\in E(G)$ and $1\leq p\leq 2r-1$.
Now, we append $v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TS}}}v_{j}$ to
${\mathcal{S}}$.

    4. Case 4:

$u\in V(G^{\prime})-V(G)$ and $v\in V(G^{\prime})-V(G)$. Do nothing.

To see that ${\mathcal{S}}$ is indeed a ${\mathsf{TJ}}$-sequence in $G$, it
suffices to show that if $C$ is the minimum VC obtained right before the move
$v_{i}\overset{G}{\longrightarrow}_{{\mathsf{TJ}}}v_{j}$ in $G$ then
$C^{\prime}=C-v_{i}+v_{j}$ is also a minimum VC of $G$. If Case 1 happens,
this is trivial. Thus, it remains to consider the case Case 3 happens. In this
case, suppose to the contrary that $C^{\prime}$ is not a VC of $G$. It follows
that there exists $k\in\\{1,\dots,n\\}$ such that $v_{i}v_{k}\in E(G)$,
$v_{k}\neq v_{j}$, and $v_{k}\notin C$. Intuitively, the edge $v_{i}v_{k}$ is
not covered by any vertex in $C^{\prime}$. On the other hand, let $D$ be the
D$r$DS of $G^{\prime}$ obtained right before the move
$x_{ij}^{p}\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{TJ}}}x_{ij}^{2r}=v_{j}$,
for $1\leq p\leq 2r-1$. Since $D^{\prime}=D-x_{ij}^{p}+x_{ij}^{2r}$ is also a
D$r$DS of $G^{\prime}$, there must be some vertex in $D^{\prime}$ that
$r$-dominates $x_{ik}^{r}$, which implies $V(P_{ik})\cap
D^{\prime}\neq\emptyset$. However, from the construction of ${\mathcal{S}}$,
it follows that $v_{k}\in C$, which is a contradiction. Thus, $C^{\prime}$ is
a vertex cover of $G$. Since $|C^{\prime}|=|C|$, it is also minimum.

∎

Our proof is complete. ∎

###  3.3 Chordal Graphs

######  Theorem 3.

D$r$DSR under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ on chordal
graphs is ${\mathtt{PSPACE}}$-complete for any $r\geq 2$.

###### Proof.

We give a polynomial-time reduction from Minimum Vertex Cover Reconfiguration
(M-VCR) on general graphs, which was showed to be ${\mathtt{PSPACE}}$-complete
by Ito et al. [18]. Let $(G,C_{s},C_{t})$ be an instance of M-VCR under
${\mathsf{R}}$ where $C_{s},C_{t}$ are two minimum VCs of a graph $G$. We will
construct an instance $(G^{\prime},D_{s},D_{t})$ of D$r$DSR under
${\mathsf{R}}$ where $D_{s}$ and $D_{t}$ are two D$r$DSs of a chordal graph
$G^{\prime}$.

Suppose that $V(G)=\\{v_{1},\dots,v_{n}\\}$. We construct $G^{\prime}$ from
$G$ as follows.

  * •

Form a clique in $G^{\prime}$ having all vertices $v_{1},\dots,v_{n}$ of $G$

  * •

For each edge $v_{i}v_{j}\in E(G)$, add a corresponding new vertex $x_{ij}$ to
$G^{\prime}$ and join it to both $v_{i}$ and $v_{j}$, where
$i,j\in\\{1,\dots,n\\}$. Observe that $x_{ij}=x_{ji}$. Furthermore, attach to
each $x_{ij}$ a new path $P_{ij}$ of length exactly $r-1$.

  * •

For each vertex $v_{i}\in V(G)$, add a corresponding new vertex
$v^{\prime}_{i}$ to $G^{\prime}$ and join it to any $v_{j}$ satisfying that
$\mathsf{dist}_{G}(v_{i},v_{j})\leq 1$. Furthermore, attach to each
$v_{i}^{\prime}$ a new path $Q_{i}$ of length exactly $r-1$.

We define $D_{s}=C_{s}$ and $D_{t}=C_{t}$. Clearly, this construction can be
done in polynomial time. (See Figure 3.)

Figure 3: An example of constructing $G^{\prime}$ from a graph $G$ in the
proof of Theorem 3. Vertices in $V(G^{\prime})-V(G)$ are marked with the gray
color. Vertices in the yellow box form a clique. Each red path is of length
exactly $r-1$.

It follows from the construction that $G^{\prime}$ is indeed a chordal graph.
More precisely, if we define $H=(K\uplus S,F)$ to be the split graph with
$K=\\{v_{1},\dots,v_{n}\\}$ forming a clique and $S=\bigcup_{\\{i,j\mid
v_{i}v_{j}\in E(G)\\}}\\{x_{ij}\\}\cup\bigcup_{i=1}^{n}\\{v^{\prime}_{i}\\}$
forming an independent set, then $G^{\prime}$ is obtained from $H$ by
attaching paths to each member of $S$, which clearly results a chordal graph.
Additionally, one can verify that any minimum vertex cover of $G$ is also a
minimum dominating set of $H$ and therefore a minimum D$r$DS of $G^{\prime}$.
(Recall that in a connected graph, any VC is also a DS.)

######  Claim 3.1.

Under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$, $(G,C_{s},C_{t})$ is
a yes-instance if and only if $(G^{\prime},D_{s},D_{t})$ is a yes-instance.

###### Proof.

  * ($\Rightarrow$)

Let ${\mathcal{S}}$ be a ${\mathsf{R}}$-sequence in $G$ between $C_{s}$ and
$C_{t}$. Since any minimum VC of $G$ is also a minimum D$r$DS of $G^{\prime}$,
the sequence ${\mathcal{S}}^{\prime}$ obtained by replacing each move
$u\overset{G}{\longrightarrow}_{{\mathsf{R}}}v$ in ${\mathcal{S}}$ by
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{R}}}v$ is also a
${\mathsf{R}}$-sequence in $G^{\prime}$ between $D_{s}=C_{s}$ and
$D_{t}=C_{t}$.

  * ($\Leftarrow$)

Let ${\mathcal{S}}^{\prime}$ be a ${\mathsf{R}}$-sequence in $G^{\prime}$
between $D_{s}$ and $D_{t}$. From the construction of $G^{\prime}$, observe
that no token can be moved to a vertex in $V(G^{\prime})-V(G)$; otherwise some
degree-$1$ endpoint of either a $P_{ij}$ or a $Q_{\ell}$ would not be
$r$-dominated by the resulting token-set. Therefore, any move
$u\overset{G^{\prime}}{\longrightarrow}_{{\mathsf{R}}}v$ in
${\mathcal{S}}^{\prime}$ satisfies that both $u$ and $v$ are in $V(G)$, and
thus can be replaced by the move
$u\overset{G}{\longrightarrow}_{{\mathsf{R}}}v$ to construct
${\mathcal{S}}$—our desired ${\mathsf{R}}$-sequence between $C_{s}=D_{s}$ and
$C_{t}=D_{t}$ in $G$.

∎

∎

##  4 Polynomial-Time Algorithms

###  4.1 Graphs and Their Powers

An extremely useful concept for studying distance-$r$ dominating sets is graph
power. For a graph $G$ and an integer $s\geq 1$, the $s^{th}$ power of $G$ is
the graph $G^{s}$ whose vertices are $V(G)$ and two vertices $u,v$ are
adjacent in $G^{s}$ if $\mathsf{dist}_{G}(u,v)\leq s$. Observe that $D$ is a
D$r$DS of $G$ if and only if $D$ is a DS of $G^{r}$. The following proposition
is straightforward.

######  Proposition 4.

Let ${\mathcal{G}}$ and ${\mathcal{H}}$ be two graph classes and suppose that
for every $G\in{\mathcal{G}}$ we have $G^{r}\in{\mathcal{H}}$ for some fixed
integer $r\geq 1$. If DSR under ${\mathsf{TJ}}$ on ${\mathcal{H}}$ can be
solved in polynomial time, so does D$r$DSR under ${\mathsf{TJ}}$ on
${\mathcal{G}}$.

###### Proof.

Since $D$ is a D$r$DS of $G$ if and only if $D$ is a DS of $G^{r}$, any
${\mathsf{TJ}}$-sequence in $G$ between two D$r$DSs can be converted to a
${\mathsf{TJ}}$-sequence in $G^{r}$ between two corresponding DSs and vice
versa. ∎

Recall that the power of any interval graph is also an interval graph [21, 20]
and DSR under ${\mathsf{TJ}}$ on interval graphs is in ${\mathtt{P}}$ [14].
Along with Proposition 4, we immediately obtain the following corollary.

######  Corollary 5.

D$r$DSR under ${\mathsf{TJ}}$ on interval graphs is in ${\mathtt{P}}$ for any
$r\geq 1$.

###  4.2 Graphs With Bounded Diameter Components

######  Proposition 6.

Let $G$ be any graph such that there is some constant $c>0$ satisfying
$\mathsf{diam}(C_{G})\leq c$ for any component $C_{G}$ of $G$. Then, D$r$DSR
on $G$ under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ is in
${\mathtt{P}}$ for every $r\geq c$.

###### Proof.

When $r\geq c$, any size-$1$ vertex subset of $G$ is a D$r$DS. In this case,
observe that any token-jump (and therefore token-slide) from one vertex to any
unoccupied vertex always results a new D$r$DS. The problem becomes trivial:
under ${\mathsf{TJ}}$, the answer is always “yes”; under ${\mathsf{TS}}$, the
answer depends on the number of tokens in each component. ∎

Since any connected cograph has diameter at most $2$, the following corollary
is straightforward.

######  Corollary 7.

D$r$DSR under ${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$ on cographs
is in ${\mathtt{P}}$ for any $r\geq 2$.

###  4.3 Split Graphs

In this section, we assume that for any split graph $G$, the set $V(G)$ is
partitioned into two subsets $K=\\{v_{1},\dots,v_{p}\\}$ and
$S=\\{v_{p+1},v_{p+2},\dots,v_{p+q}\\}$ which respectively induce a clique and
an independent set of $G$. For convenience, we write $G=(K\uplus S,E)$.

######  Lemma 8.

Let $D$ be a D$2$DS of a split graph $G=(K\uplus S,E)$.

  1. (a)

For every pair $u\in D\cap K$ and $v\in K-D$, the set $D-u+v$ is a D$2$DS of
$G$.

  2. (b)

For every pair $u\in D\cap S$ and $v\in K-D$, the set $D-u+v$ is a D$2$DS of
$G$.

  3. (c)

For every pair $u\in D\cap K$ and $v\in S-D$, the set $D-u+v$ is a D$2$DS of
$G$ if $(D\cap K)-u\neq\emptyset$.

###### Proof.

By definition, $\mathsf{dist}_{G}(v,w)\leq 2$ for any $w\in V(G)$.
Consequently, in both (a) and (b), $\\{v\\}$ is a D$2$DS of $G$, and therefore
so is $D-u+v\supseteq\\{v\\}$. In (c), since $(D\cap K)-u\neq\emptyset$, there
must be a vertex $x\in D\cap K$ such that $x\neq u$. Again, since $\\{x\\}$ is
a D$2$DS of $G$, so is $D-u+v\supseteq\\{x\\}$. ∎

######  Theorem 9.

D$r$DSR under ${\mathsf{TS}}$ on split graphs is in ${\mathtt{P}}$ for any
$r\geq 2$. In particular, when $r=2$, for any pair of size-$k$ D$2$DSs
$D_{s},D_{t}$ of a split graph $G=(K\uplus S,E)$, there is a
$\mathsf{TS}$-sequence in $G$ between $D_{s}$ and $D_{t}$.

###### Proof.

Proposition 6 settles the case $r\geq 3$. It remains to consider the case
$r=2$. We claim that for any pair of size-$k$ D$2$DSs $D_{s},D_{t}$ of a split
graph $G=(K\uplus S,E)$, there is a $\mathsf{TS}$-sequence in $G$ between
$D_{s}$ and $D_{t}$. Suppose that $p=|K|\geq 1$ and $q=|S|\geq 1$.

We first show how to construct a size-$k$ D$2$DS $D^{\star}$ and then claim
that for any size-$k$ D$2$DS $D$ of $G$, there exists a $\mathsf{TS}$-sequence
between $D$ and $D^{\star}$. Suppose that vertices of $G$ are arranged as
$v_{1},v_{2},\dots,v_{p},v_{p+1},v_{p+2},\dots,v_{p+q}$ where
$K=\\{v_{1},\dots,v_{p}\\}$ and $S=\\{v_{p+1},\dots,v_{p+q}\\}$. We take
$D^{\star}=\\{v_{1},\dots,v_{k}\\}$.

We describe how to construct a ${\mathsf{TS}}$-sequence between $D$ and
$D^{\star}$. Our construction is based on the observations described in Lemma
8. Intuitively, in each iteration $i\in\\{1,\dots,k\\}$ of our algorithm, we
will move a token in $D$ to $v_{i}$ and considered it as “settled”. We note
that once a vertex in $D$ is “settled” in some iteration, it always remains
“settled” after each next iteration. For each $i\in\\{1,\dots,k\\}$,

  * •

Assign $D^{\prime}\leftarrow D-\\{v_{1},\dots,v_{i-1}\\}$. Note that if $i=1$
then $D^{\prime}=D$. Intuitively, $D^{\prime}$ contains “unsettled” vertices
in $D$ at that time.

  * •

Let $v^{i}\in D^{\prime}$ be such that
$\mathsf{dist}_{G}(v^{i},v_{i})=\min_{x\in
D^{\prime}}\mathsf{dist}_{G}(x,v_{i})$.

    * –

If $v_{i}\in K$ and $v^{i}\in K$, by Lemma 8, we can directly slide the token
on $v^{i}$ to $v_{i}$ and update $D\leftarrow D-v^{i}+v_{i}$.

    * –

If $v_{i}\in K$ and $v^{i}\in S$, let $P_{i}$ be a shortest $v^{i}v_{i}$-path
in $G$. Observe that $V(P_{i})\cap D=\\{v^{i}\\}$ and $P_{i}$ is of length at
most $2$. If $P_{i}$ is of length $1$ (i.e., $P=v^{i}v_{i}$), again by Lemma
8, we can directly slide the token on $v^{i}$ to $v_{i}$ and update
$D\leftarrow D-v^{i}+v_{i}$. If $P_{i}$ is of length $2$, $v^{i}$ and $v_{i}$
must have a common neighbor $w\in K$. Since $V(P_{i})\cap D=\\{v^{i}\\}$, we
have $w\notin D$. By Lemma 8, we can immediately slide the token on $v^{i}$ to
$w$ and then from $w$ to $v_{i}$, and update $D\leftarrow(D-v^{i}+w)-w+v_{i}$.

    * –

If $v_{i}\in S$, we must have $i>p=|K|$ (i.e., all vertices in $K$ are already
filled with tokens) and therefore $v^{i}\in S$ (since all vertices in $K$ are
already “settled”). Thus, a shortest $v^{i}v_{i}$-path $P_{i}$ must be of
length either $2$ or $3$ and all of its vertices except $v_{i}$ contain tokens
(i.e., they are in $D$). If $P_{i}$ is of length $2$, $v^{i}$ and $v_{i}$ must
have a common neighbor $w\in K$ and since $i>p$ we also have $w\in D$. Thus,
by Lemma 8, we can directly slide the token on $w$ to $v_{i}$ and then from
$v^{i}$ to $w$ and update $D\leftarrow(D-w+v_{i})-v^{i}+w$. If $P_{i}$ is of
length $3$, let $P_{i}=v^{i}xyv_{i}$ and we must have $\\{x,y\\}\subseteq K$
and since $i>p$ we also have $\\{x,y\\}\subseteq D$. Again, by Lemma 8, we can
directly slide the token on $y$ to $v_{i}$, then the token on $x$ to $y$, and
then the token on $v^{i}$ to $x$, and update
$D\leftarrow((D-y+v_{i})-x+y)-v^{i}+x$.

∎

Since any ${\mathsf{TS}}$-sequence in $G$ is also a ${\mathsf{TJ}}$-sequence,
a direct consequence of Theorem 9 and Proposition 6 is as follows.

######  Corollary 10.

D$r$DSR under ${\mathsf{TJ}}$ on split graphs is in ${\mathtt{P}}$ for any
$r\geq 2$.

We now consider shortest reconfiguration sequences in split graphs when $r=2$.
Observe that each ${\mathsf{R}}$-sequence
(${\mathsf{R}}\in\\{{\mathsf{TS}},{\mathsf{TJ}}\\}$) between two D$r$DSs
$D_{s},D_{t}$ induces a bijection $f$ between them: the token on $u\in D_{s}$
must finally be placed on $f(u)\in D_{t}$ and vice versa.

######  Theorem 11.

Suppose that $D_{s}=\\{s_{1},\dots,s_{k}\\}$ and
$D_{t}=\\{t_{1},\dots,t_{k}\\}$ are two size-$k$ D$2$DSs of a split graph
$G=(K\uplus S,E)$. Let
$M^{*}_{{\mathsf{TS}}}=\min_{f}\sum_{i=1}^{k}\mathsf{dist}_{G}(s_{i},f(s_{i}))$
where $f$ is a bijection between vertices of $D_{s}$ and $D_{t}$. Then,

  1. (a)

$\mathsf{OPT}_{{\mathsf{TS}}}(G,D_{s},D_{t})\geq M^{*}_{{\mathsf{TS}}}$.

  2. (b)

There exists a graph $G$ and two size-$k$ D$2$DSs $D_{s},D_{t}$ of $G$ such
that
$\displaystyle\mathsf{OPT}_{{\mathsf{TS}}}(G,D_{s},D_{t})=M^{*}_{{\mathsf{TS}}}+1$.

###### Proof.

  1. (a)

In order to slide a token from $s_{i}\in D_{s}$ to $f(s_{i})\in D_{t}$ for
some $i\in\\{1,\dots,k\\}$, one cannot use less than
$\mathsf{dist}_{G}(s_{i},f(s_{i}))$ token-slides.

  2. (b)

We construct a split graph $G=(K\uplus S,E)$ as follows. (See Figure 4.)

     * •

$K$ contains $3$ vertices labelled $s_{1},a,b$. Vertices of $K$ form a clique
in $G$.

     * •

$S$ contains $2k+1$ vertices labelled
$s_{2},\dots,s_{k},t_{1},\dots,t_{k},c,d$. Vertices of $S$ form an independent
set in $G$.

     * •

Join $s_{1}$ to $s_{2},\dots,s_{k},t_{1},\dots,t_{k}$. Join $a$ to $c$ and
$t_{1}$. Join $b$ to $t_{2},\dots,t_{k}$ and $d$.

Let $D_{s}=\\{s_{1},\dots,s_{k}\\}$ and $D_{t}=\\{t_{1},\dots,t_{k}\\}$.

Figure 4: Construction of a split graph $G=(K\uplus S,E)$ satisfying Theorem
11(b).

One can readily verify that both $D_{s}$ and $D_{t}$ are D$2$DSs of $G$.
Observe that
$M^{\star}_{{\mathsf{TS}}}=\sum_{i=1}^{k}\mathsf{dist}_{G}(s_{i},t_{i})=2(k-1)+1=2k-1$.
Additionally, any ${\mathsf{TS}}$-sequence ${\mathcal{S}}$ in $G$ between
$D_{s}$ and $D_{t}$ must begin with sliding the token on $s_{1}$ to one of its
unoccupied neighbors. A ${\mathsf{TS}}$-sequence of length exactly
$M^{\star}_{{\mathsf{TS}}}$ must slide $s_{1}$ to one of $t_{1},\dots,t_{k}$
but that is not possible, otherwise either $c$ (if sliding to
$t_{2},\dots,t_{k}$) or $d$ (if sliding to $t_{1}$) would not be $2$-dominated
by the resulting token-set. Thus, such a sequence does not exist.

On the other hand, a ${\mathsf{TS}}$-sequence of length exactly
$M^{\star}_{{\mathsf{TS}}}+1$ can be constructed: first sliding the token on
$s_{1}$ to $a$, then sliding the token on $s_{i}$ to $t_{i}$ along the
$s_{i}t_{i}$-path for $2\leq i\leq k$, and finally sliding the token on $a$ to
$t_{1}$. Since a token is always placed on $a\in K$ (whose distance to any
other vertex is at most $2$) after the first token-slide and before the final
one, the above sequence of token-slides is indeed a ${\mathsf{TS}}$-sequence
in $G$.

∎

######  Theorem 12.

Suppose that $D_{s}=\\{s_{1},\dots,s_{k}\\}$ and
$D_{t}=\\{t_{1},\dots,t_{k}\\}$ are two size-$k$ D$2$DSs of a split graph
$G=(K\uplus S,E)$. Let $\displaystyle M^{*}_{{\mathsf{TJ}}}=\frac{|D_{s}\Delta
D_{t}|}{2}$. Then,

  1. (a)

$\mathsf{OPT}_{{\mathsf{TJ}}}(G,D_{s},D_{t})\geq M^{*}_{{\mathsf{TJ}}}$.

  2. (b)

There exists a graph $G$ and two size-$k$ D$2$DSs $D_{s},D_{t}$ of $G$ such
that
$\displaystyle\mathsf{OPT}_{{\mathsf{TS}}}(G,D_{s},D_{t})=M^{*}_{{\mathsf{TJ}}}+1$.

###### Proof.

  1. (a)

Trivial.

  2. (b)

We construct a split graph $G=(K\uplus S,E)$ as follows.

     * •

$K$ contains $2k$ vertices labelled $v_{1},\dots,v_{k},w_{1},\dots,w_{k}$.
Vertices in $K$ form a clique in $G$.

     * •

$S$ contains $k^{2}+k$ vertices labelled
$v_{11},\dots,v_{1k},v_{21},\dots,v_{2k},\dots,v_{k1},\dots,v_{kk},w_{11},\dots,w_{k1}$.
Vertices in $S$ form an independent set in $G$.

     * •

For each fixed $i\in\\{1,\dots,k\\}$,

       * –

for $j\in\\{1,\dots,k\\}$,

         * *

join $v_{i}$ to every $v_{ij}$,

         * *

join $w_{i}$ to every $v_{ji}$,

       * –

join $w_{i}$ to $w_{i1}$.

Let $D_{s}=\bigcup_{i=1}^{k}\\{v_{ii}\\}$ and
$D_{t}=\bigcup_{i=1}^{k}\\{w_{i1}\\}$.

Figure 5: Construction of a split graph $G=(K\uplus S,E)$ satisfying Theorem
12(b). Vertices in the yellow box are in $K$.

To see that $D_{s}$ is a D$2$DS of $G$, note that each $v_{ii}$ $2$-dominates
every vertex in $K\cup\bigcup_{j=1}^{k}\\{v_{ij}\\}\cup\\{w_{ii}\\}$. To see
that $D_{t}$ is a D$2$DS of $G$, note that each $w_{i1}$ $2$-dominates every
vertex in $K\cup\bigcup_{j=1}^{k}\\{v_{ji}\\}$. Moreover, any
${\mathsf{TJ}}$-sequence of length exactly $M^{\star}_{{\mathsf{TJ}}}$ must
begin with a direct token-jump from some $v_{ii}$ to some $w_{j1}$ for some
$1\leq i,j\leq k$ but that is not possible, otherwise no vertices in
$\bigcup_{\ell=1}^{k}\\{v_{i\ell}\\}-v_{ij}$ are $2$-dominated by the
resulting token-set.

On the other hand, a ${\mathsf{TJ}}$-sequence of length exactly
$M^{\star}_{{\mathsf{TJ}}}+1$ can be constructed: first jumping the token on
$v_{11}$ to $v_{1}$, then for $2\leq i\leq k$, directly jumping the token on
$v_{ii}$ to $w_{i1}$, and finally jumping the token on $v_{1}$ to $w_{11}$. As
before, since a token is always placed at $v_{1}\in K$ after the first token-
jump and before the final one, the above sequence of token-jumps is indeed a
${\mathsf{TJ}}$-sequence in $G$.

∎

###  4.4 Trees

######  Theorem 13.

D$r$DSR under ${\mathsf{TJ}}$ on trees is in ${\mathtt{P}}$ for any $r\geq 2$.

To prove this theorem, we extend the idea of Haddadan et al. [14] for $r=1$
under ${\mathsf{TAR}}$ and the linear-time algorithm of Kundu and Majumder
[15] for finding a minimum D$r$DS on trees. In particular, we employ a simpler
implementation of Kundu and Majumder’s algorithm presented by Abu-Affash,
Carmi, and Krasin [2]. More precisely, based on the minimum D$r$DS $D^{\star}$
obtained from the implementation of Abu-Affash, Carmi, and Krasin, we
construct a partition $\mathbb{P}(T)$ of $T$ consisting of $\gamma_{r}(T)$
vertex-disjoint subtrees, each of which contains exactly one vertex of
$D^{\star}$. (Haddadan et al. called such a set $D^{\star}$ a canonical
dominating set.) For convenience, we denote by $C_{x}$ the member of
$\mathbb{P}(T)$ whose intersection with $D^{\star}$ is the vertex $x$. We
claim that $\mathbb{P}(T)$ satisfies the following property: for any D$r$DS
$D$ of $G$, each member of $\mathbb{P}(T)$ contains at least one vertex in
$D$. Using this property, it is not hard to design a linear-time algorithm for
constructing a ${\mathsf{TJ}}$-sequence between any pair of size-$k$ D$r$DSs
$D_{s},D_{t}$ of $G$. The key idea is one can transform both $D_{s}$ and
$D_{t}$ into some D$r$DS $D$ that contains $D^{\star}$. For instance, to
transform $D_{s}$ into $D$, for each subtree $C_{x}\in\mathbb{P}(T)$ for $x\in
D^{\star}$, we move any token in $D_{s}\cap V(C_{x})$ to $x$. If we handle
each subtree $C_{x}$ based on the order of subtrees added to $\mathbb{P}(T)$
in our modified implementation, such a transformation will form a
${\mathsf{TJ}}$-sequence in $T$. After this procedure, we obtain a set of
tokens $D^{\prime}$ that contains $D^{\star}$ and since $D^{\star}$ is a
minimum D$r$DS of $G$, transforming $D^{\prime}$ into $D$ under
${\mathsf{TJ}}$ can now be done easily: until there are no tokens to move,
repeatedly take a token in $D^{\prime}-D$, move it to some vertex in
$D-D^{\prime}$, and update both $D$ and $D^{\prime}$.

We now define some notations and, for the sake of completeness, describe the
algorithm of Abu-Affash, Carmi, and Krasin [2]. In a graph $G$, for a vertex
subset $D\subseteq V(G)$ and a vertex $u\in V(G)$, we define
$\delta_{D}(u)=\min_{v\in D}\mathsf{dist}_{G}(u,v)$ and call it the distance
between $u$ and $D$. Observe that a vertex $u$ is $r$-dominated by $D$ if
$\delta_{D}(u)\leq r$ and therefore $D$ is a D$r$DS of $G$ if for every $u\in
V(G)$ we have $\delta_{D}(u)\leq r$. For a $n$-vertex tree $T$, let $T_{u}$ be
the rooted form of $T$ when regarding the vertex $u\in V(T)$ as the root. For
each $v\in V(T_{u})$, we denote by $T_{v}$ the subtree of $T_{u}$ rooted at
$v$. In other words, $T_{v}$ is the subtree of $T_{u}$ induced by $v$ and its
descendants. We also define $h(T_{v})=\max_{w\in
V(T_{v})}\mathsf{dist}_{T_{u}}(v,w)$ and call it the height of $T_{v}$. In
other words, $h(T_{v})$ is the largest distance from $v$ to a vertex in
$T_{v}$. The set of children of $v$ in $T_{u}$ is denoted by
$\textit{child}(v)$.

The algorithm is described in Algorithm 1. In short, in each iteration, it
finds a subtree $T_{v}$ of height exactly $r$, adds $v$ to $D^{\star}$, and
removes all the leaves of $T_{u}$ that are in $N^{r}_{T_{u}}[v]$. To implement
the algorithm in $O(n)$ time, a modified version of the depth-first search
(DFS) algorithm was used in [2] (Function $\mathtt{ModifiedDFS}$ in Algorithm
1). The procedure $\mathtt{ModifiedDFS}$ visits the vertices of $T_{u}$
starting from the root $u$ and recursively visits each of its children, which
means vertices in $D^{\star}$ would be added in a “bottom-up” fashion. In each
recursive call $\mathtt{ModifiedDFS}(v)$, if $h(T_{v})=r$ then $v$ is added to
$D^{\star}$ and since all vertices in $T_{v}$ is $r$-dominated by $v$, we
remove them from $T_{u}$ and return $\delta_{D^{\star}}(v)=0$. Otherwise
($h(T_{v})\neq r$), we call $\mathtt{ModifiedDFS}(w)$ for each child $w$ of
$v$, and we update $\delta_{D^{\star}}(v)$ and $h(T_{v})$ according to these
calls. When these calls return, we have $h(T_{v})\leq r$. Then we check
whether $\delta_{D^{\star}}(v)+h(T_{v})\leq r$. If so (which means the current
$D^{\star}$ $r$-dominates $v$ and all its descendants in the original rooted
tree $T_{u}$), we remove all the vertices of $T_{v}$ from $T_{r}$ and return
$\delta_{D^{\star}}(v)$. Otherwise ($\delta_{D^{\star}}(v)+h(T_{v})>r$), we
check again whether $h(T_{v})=r$ (in case the descendants reduced the height
of $T_{v}$ to $r$). If so, we add $v$ to $D^{\star}$, remove all the vertices
of $T_{v}$ from $T_{u}$, and return $\delta_{D^{\star}}(v)=0$. Otherwise
($h(T_{v})<r$), we return $\infty$. Finally, when
$\delta_{D^{\star}}(u)=\infty$, we add $u$ to $D^{\star}$.

Input: A tree $T_{u}$ rooted at $u$.

Output: A minimum distance-$r$ dominating set $D^{\star}$ of $T_{u}$.

1

2$D^{\star}\leftarrow\emptyset$

3 for each $v\in V(T_{u})$ do

4 compute $h(T_{v})$

5 $\delta_{D^{\star}}(v)\leftarrow\infty$

6

7$\delta_{D^{\star}}(u)\leftarrow\mathtt{ModifiedDFS}(u)$

8 if $\delta_{D^{\star}}(u)=\infty$ then

9 $D^{\star}\leftarrow D^{\star}+u$

10

11return $D^{\star}$

12

13Function  _ModifiedDFS(_$v$_)_:

14 if $h(T_{v})=r$ then

15 $D^{\star}\leftarrow D^{\star}+v$

16 $T_{u}\leftarrow T_{u}-T_{v}$

17 $h(T_{v})\leftarrow-1$

18 $\delta_{D^{\star}}(v)\leftarrow 0$

19

20 else // $h(T_{v})>r$

21 for each $w\in\textit{child}(v)$ do

22 if $h(T_{w})\geq r$ then

23
$\delta_{D^{\star}}(v)\leftarrow\min\\{\delta_{D^{\star}}(v),\mathtt{ModifiedDFS}(w)+1\\}$

24

25 $h(T_{v})\leftarrow\max\\{h(T_{w})+1:w\in\textit{child}(v)\\}$

26 // updating $h(T_{v})$

27 if $h(T_{v})+\delta_{D^{\star}}(v)\leq r$ then

28 $T_{u}\leftarrow T_{u}-T_{v}$

29 $h(T_{v})\leftarrow-1$

30

31 if $h(T_{v})=r$ then

32 $D^{\star}\leftarrow D^{\star}+v$

33 $T_{u}\leftarrow T_{u}-T_{v}$

34 $h(T_{v})\leftarrow-1$

35 $\delta_{D^{\star}}(v)\leftarrow 0$

36

37 else

38 $\delta_{D^{\star}}(v)\leftarrow\infty$

39

40

41

42 return $\delta_{D^{\star}}(v)$

43

Algorithm 1 $\mathtt{MinDrDSTree}(T_{u})$

To illustrate Algorithm 1, we consider the example from [2] for $r=2$ with the
tree $T_{u}$ rooted at $u=1$ as described in Figure 6. The first vertex added
to $D^{\star}$ is $7$ in $\mathtt{ModifiedDFS}(7)$, since $h(T_{7})=2$. In
this call, we remove $T_{7}$ from $T_{u}$, update $h(T_{7})=-1$ and return
$\delta_{D^{\star}}(7)=0$ to $\mathtt{ModifiedDFS}(4)$. In
$\mathtt{ModifiedDFS}(4)$, we update $\delta_{D^{\star}}(4)=1$ and, after
traversing vertices $6$ and $8$, $h(T_{4})=1$, and since
$h(T_{4})+\delta_{D^{\star}}(4)=2=r$ and $7$ is the latest vertex added to
$D^{\star}$, we remove $T_{4}$ from $T_{u}$ and return
$\delta_{D^{\star}}(4)=1$ to $\mathtt{ModifiedDFS}(2)$. In
$\mathtt{ModifiedDFS}(2)$, since $h(T_{2})=3>r$, we call
$\mathtt{ModifiedDFS}(5)$ which adds $5$ to $D^{\star}$, removes $T_{5}$ from
$T_{u}$, and returns $\delta_{D^{\star}}(5)=0$. Then, we update
$\delta_{D^{\star}}(2)=1$ and $h(T_{2})=0$, and since
$h(T_{2})+\delta_{D^{\star}}(2)=1<r$ and $5$ is the latest vertex added to
$D^{\star}$, we remove $T_{2}$ from $T_{u}$, and return
$\delta_{D^{\star}}(2)=1$ to $\mathtt{ModifiedDFS}(1)$. In
$\mathtt{ModifiedDFS}(1)$, since $\delta_{D^{\star}}(1)=2$ and, after
traversing $3$, $h(T_{1})=1$, we return $\delta_{D^{\star}}(1)=\infty$ to
Algorithm 1, and therefore, we add $1$ to $D^{\star}$.

Figure 6: A tree $T_{u}$ rooted at $u=1$. For $r=2$, Algorithm 1 returns
$D^{\star}=\\{7,5,1\\}$. A partition
$\mathbb{P}(T_{u})=\\{C_{7},C_{5},C_{1}\\}$ of $T_{u}$ is also constructed.

We now describe how to construct our desired partition $\mathbb{P}(T_{u})$.
Recall that $\mathbb{P}(T_{u})$ is nothing but a collection of vertex-disjoint
subtrees whose union is the original tree $T_{u}$. Suppose that $D^{\star}$ is
the minimum D$r$DS of $T_{u}$ obtained from Algorithm 1 and furthermore assume
that vertices of $D^{\star}$ are ordered by the time they were added to
$D^{\star}$. For each $v\in D^{\star}$, we define $C_{v}$ (the unique member
of $\mathbb{P}(T_{u})$ containing $v$) as $T_{v}$ (the subtree of $T_{u}$
rooted at $v$) and then delete $T_{v}$ from $T_{u}$. Figure 6 illustrates how
to construct $\mathbb{P}(T_{u})$ in the above example. From the construction,
it is clear that each member of $\mathbb{P}(T_{u})$ contains exactly one
vertex from $D^{\star}$. We say that two subtrees $C_{x},C_{y}$ in
$\mathbb{P}(T_{u})$ are adjacent if there exists $v\in V(C_{x})$ and $w\in
V(C_{y})$ such that $vw\in E(T_{u})$. If a subtree contains the root $u$ then
we call it the root subtree. Otherwise, if a subtree has exactly one adjacent
subtree then we call it a leaf subtree and otherwise an internal subtree.

We now claim that the constructed partition $\mathbb{P}(T_{u})$ satisfies the
following property.

######  Lemma 14.

Let $D$ be any D$r$DS of $T_{u}$. Then, $D\cap V(C_{v})\neq\emptyset$ holds
for every $v\in D^{\star}$.

###### Proof.

We claim that for each $v\in D^{\star}$, one can find a vertex $v^{\prime}\in
V(C_{v})$ such that $N^{r}_{T}[v^{\prime}]\subseteq V(C_{v})$. For each $v\in
D^{\star}$, let $D^{\star}_{v}$ be the set of all vertices added to
$D^{\star}$ before $v$.

If $C_{v}$ is a leaf subtree, we take any leaf in $C_{v}$ of distance exactly
$r$ from $v$ and regard it as $v^{\prime}$. Clearly, $v^{\prime}$ is also a
leaf of $T_{u}$ and is not $r$-dominated by any vertex outside $C_{v}$, i.e.,
$N^{r}_{T}[v^{\prime}]\subseteq V(C_{v})$.

If $C_{v}$ is an internal subtree, we describe how to find our desired
$v^{\prime}$. From Algorithm 1, since $v$ is the next vertex added to
$D^{\star}_{v}$, it follows that there must be some vertex in $V(C_{v})$ not
$r$-dominated by any member of $D^{\star}_{v}$; we take $v^{\prime}$ to be the
one having maximum distance from $v$ among all those vertices. By definition,
$v^{\prime}$ is clearly not $r$-dominated by any vertex in a $C_{w}$ where
$w\in D^{\star}_{v}$. Since $C_{v}$ is an internal subtree, by Algorithm 1,
the distance between $v$ and $v^{\prime}$ must be exactly $r$ and therefore no
vertex in a $C_{w}$, where $w\in D^{\star}-D^{\star}_{v}-v$, $r$-dominates
$v$. (Recall that by Algorithm 1, since $v$ is added to $D^{\star}_{v}$, the
current subtree $T_{v}$ must have height exactly $r$.) Thus,
$N_{T}^{r}[v^{\prime}]\subseteq V(C_{v})$.

If $C_{v}$ is the root subtree, again we can choose $v^{\prime}$ using exactly
the same strategy as in the case for internal subtrees. The main difference
here is that, by Algorithm 1, the distance between $v^{\prime}$ and $v$ may
not be exactly $r$. However, since $C_{v}$ contains the root $u$, $v$ is the
last vertex added to $D^{\star}$. (Intuitively, this means $C_{v}$ has no
“parent subtree” above it.) Therefore, in order to show that
$N_{T}^{r}[v^{\prime}]\subseteq V(C_{v})$, it suffices to show that no vertex
in a $C_{w}$, where $w\in D^{\star}_{v}$, $r$-dominates $v^{\prime}$. Indeed,
this clearly holds by definition of $v^{\prime}$.

We are now ready to prove the lemma. Suppose to the contrary that there exists
$v\in D^{\star}$ such that $D\cap V(C_{v})=\emptyset$. Then, $D$ does not
$r$-dominate $v^{\prime}$—a vertex in $C_{v}$ with
$N_{T}^{r}[v^{\prime}]\subseteq V(C_{v})$. This contradicts the assumption
that $D$ is a D$r$DS. Our proof is complete. ∎

The following lemma is crucial in proving Theorem 13.

######  Lemma 15.

Let $D$ be an arbitrary D$r$DS of $T_{u}$. Let $D^{\prime}$ be any D$r$DS of
$T_{u}$ that contains $D^{\star}$, i.e., $D^{\star}\subseteq D^{\prime}$.
Then, in $O(n)$ time, one can construct a ${\mathsf{TJ}}$-sequence
${\mathcal{S}}$ in $T_{u}$ between $D$ and $D^{\prime}$.

###### Proof.

We construct ${\mathcal{S}}$ as follows. Initially, ${\mathcal{S}}=\emptyset$.

  1. Step 1:

For each $v\in D^{\star}$, let $x$ be any vertex in $D\cap V(C_{v})$. From
Lemma 14, such a vertex $x$ exists. We append
$x\overset{T_{u}}{\longrightarrow}_{{\mathsf{TJ}}}v$ to ${\mathcal{S}}$ and
assign $D\leftarrow D-x+v$. (After this step, clearly $D^{\star}\subseteq
D\cap D^{\prime}$.)

  2. Step 2:

Let $x\in D-D^{\prime}$ and $y\in D^{\prime}-D$. We append
$x\overset{T_{u}}{\longrightarrow}_{{\mathsf{TJ}}}y$ to ${\mathcal{S}}$ and
assign $D\leftarrow D-x+y$. Repeat this step until $D=D^{\prime}$.

For each $v\in D^{\star}$, let $D^{\star}_{v}$ be the set of all vertices
added to $D^{\star}$ before $v$. Since any vertex $r$-dominated by $x$ and not
in $C_{v}$ is $r$-dominated by either $v$ or a member of $D^{\star}_{v}$, any
move performed in Step 1 results a new D$r$DS of $T_{u}$. Note that after Step
1, $D^{\star}\subseteq D\cap D^{\prime}$. Thus, any move performed in Step 2
results a new D$r$DS of $T_{u}$. In short, ${\mathcal{S}}$ is indeed a
${\mathsf{TJ}}$-sequence in $T_{u}$. In the above construction, as we “touch”
each vertex in $D$ at most once, the running time is indeed $O(n)$. ∎

Using Lemma 15, it is not hard to prove Theorem 13. More precisely, let
$(T,D_{s},D_{t})$ be an instance of D$r$DSR under ${\mathsf{TJ}}$ where
$D_{s}$ and $D_{t}$ are two D$r$DSs of a tree $T$. By Lemma 15, one can
immediately decide if $(T,D_{s},D_{t})$ is a yes-instance by comparing the
sizes of $D_{s}$ and $D_{t}$: if they are of the same size then the answer is
“yes” and otherwise it is “no”. Moreover, in a yes-instance, Lemma 15 allows
us to construct in linear time a ${\mathsf{TJ}}$-sequence (which is not
necessarily a shortest one) between $D_{s}$ and $D_{t}$.

##  5 Concluding Remarks

In this paper, we provide an initial picture of the computational complexity
of D$r$DSR ($r\geq 2$) under ${\mathsf{TS}}$ and ${\mathsf{TJ}}$ on different
graph classes. We extended several known results for $r=1$ and provided a
complexity dichotomy of D$r$DSR on split graphs: the problem is
${\mathtt{PSPACE}}$-complete for $r=1$ but can be solved in polynomial time
for $r\geq 2$. The following questions remain unsolved:

  1. Question 1:

What is the complexity of D$r$DSR ($r\geq 2$) under ${\mathsf{TS}}$ on trees?

  2. Question 2:

What is the complexity of D$r$DSR ($r\geq 2$) under ${\mathsf{TS}}$ on
interval graphs?

## Acknowledgment

Niranka Banerjee is funded by JSPS KAKENHI Grant Number JP20H05967 and Duc A.
Hoang is funded by University of Science, Vietnam National University, Hanoi
under project number TN.23.04.

## References

  * [1] Jan Matyáš Křišt’an and Jakub Svoboda  “Shortest Dominating Set Reconfiguration under Token Sliding”  In _Proceedings of FCT 2023_ 14292, LNCS  Springer, 2023, pp. 333–347  DOI: 10.1007/978-3-031-43587-4˙24
  * [2] A. Abu-Affash, Paz Carmi and Adi Krasin  “A linear-time algorithm for minimum $k$-hop dominating set of a cactus graph”  In _Discrete Applied Mathematics_ 320 Elsevier, 2022, pp. 488–499  DOI: 10.1016/j.dam.2022.06.006
  * [3] Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura and Sebastian Siebertz  “A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems”  In _arXiv preprint_ , 2022  arXiv:2204.10526
  * [4] Marthe Bonamy, Paul Dorbec and Paul Ouvrard  “Dominating sets reconfiguration under token sliding”  In _Discrete Applied Mathematics_ 301, 2021, pp. 6–18  DOI: 10.1016/j.dam.2021.05.014
  * [5] Nicolas Bousquet and Alice Joffard  “TS-Reconfiguration of Dominating Sets in circle and circular-arc graphs”  In _Proceedings of FCT 2021_ 12867, LNCS  Springer, 2021  DOI: 10.1007/978-3-030-86593-1˙8
  * [6] Matt DeVos, Adam Dyck, Jonathan Jedwab and Samuel Simon  “Which graphs occur as $\gamma$-graphs?”  In _Graphs and Combinatorics_ 36.4, 2020, pp. 1219–1246  DOI: 10.1007/s00373-020-02174-9
  * [7] Michael A. Henning  “Distance Domination in Graphs”  In _Topics in Domination in Graphs_ 64, Developments in Mathematics  Springer, 2020, pp. 205–250  DOI: 10.1007/978-3-030-51117-3˙7
  * [8] C.M. Mynhardt and S. Nasserasr  “Reconfiguration of colourings and dominating sets in graphs”  In _50 years of Combinatorics, Graph Theory, and Computing_ CRC Press, 2019, pp. 171–191  DOI: 10.1201/9780429280092-10
  * [9] Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, M.. Ramanujan and Saket Saurabh  “Reconfiguration on Sparse Graphs”  In _Journal of Computer and System Sciences_ 95, 2018, pp. 122–131  DOI: 10.1016/j.jcss.2018.02.004
  * [10] Naomi Nishimura  “Introduction to Reconfiguration”  In _Algorithms_ 11.4, 2018, pp. 52  DOI: 10.3390/a11040052
  * [11] Sebastian Siebertz  “Reconfiguration on Nowhere Dense Graph Classes”  In _The Electronic Journal of Combinatorics_ 25.3, 2018, pp. P3.24  DOI: 10.37236/7458
  * [12] Reinhard Diestel  “Graph Theory” 173, Graduate Texts in Mathematics  Springer, 2017  DOI: 10.1007/978-3-662-53622-3
  * [13] Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour and Akira Suzuki  “On the Parameterized Complexity of Reconfiguration Problems”  In _Algorithmica_ 78.1, 2017, pp. 274–297  DOI: 10.1007/s00453-016-0159-2
  * [14] Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki and Youcef Tebbal  “The Complexity of Dominating Set Reconfiguration”  In _Theoretical Computer Science_ 651, 2016, pp. 37–49  DOI: 10.1016/j.tcs.2016.08.016
  * [15] Sukhamay Kundu and Subhashis Majumder  “A linear time algorithm for optimal $k$-hop dominating set of a tree”  In _Information Processing Letters_ 116.2 Elsevier, 2016, pp. 197–202  DOI: 10.1016/j.ipl.2015.07.014
  * [16] Tom C. van der Zanden  “Parameterized Complexity of Graph Constraint Logic”  In _Proceedings of IPEC 2015_ 43, LIPIcs  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015, pp. 282–293  DOI: 10.4230/LIPIcs.IPEC.2015.282
  * [17] Jan Heuvel  “The Complexity of Change”  In _Surveys in Combinatorics_ 409, London Mathematical Society Lecture Note Series  Cambridge University Press, 2013, pp. 127–160  DOI: 10.1017/cbo9781139506748.005
  * [18] Takehiro Ito, Erik D. Demaine, Nicholas J.. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno  “On the Complexity of Reconfiguration Problems”  In _Theoretical Computer Science_ 412.12-14, 2011, pp. 1054–1065  DOI: 10.1016/j.tcs.2010.12.005
  * [19] Robert A. Hearn and Erik D. Demaine  “PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation”  In _Theoretical Computer Science_ 343.1-2, 2005, pp. 72–96  DOI: 10.1016/j.tcs.2005.05.008
  * [20] Mingjang Chen and Gerard J. Chang  “Families of graphs closed under taking powers”  In _Graphs and Combinatorics_ 17.2 Springer, 2001, pp. 207–212  DOI: 10.1007/PL00007241
  * [21] Geir Agnarsson, Raymond Greenlaw and Magnús M. Halldórsson  “On powers of chordal graphs and their colorings”  In _Congressus Numerantium_ 144, 2000, pp. 41–65
  * [22] Gerard J. Chang and George L. Nemhauser  “The $k$-domination and $k$-stability problems on sun-free chordal graphs”  In _SIAM Journal on Algebraic Discrete Methods_ 5.3 SIAM, 1984, pp. 332–345  DOI: 10.1137/0605034
  * [23] Michael R. Garey and David S. Johnson  “Computers and intractability: A guide to the theory of NP-completeness”  WH FreemanCompany, 1979
  * [24] A. Meir and John Moon  “Relations between packing and covering numbers of a tree”  In _Pacific Journal of Mathematics_ 61.1 Mathematical Sciences Publishers, 1975, pp. 225–233  DOI: 10.2140/pjm.1975.61.225


# Shell Language Processing:
Unix command parsing for Machine Learning

Dmitrijs Trizna
<EMAIL_ADDRESS>
University of Helsinki
Avast Software

###### Abstract

In this article, we present a Shell Language Preprocessing (SLP) library,
which implements tokenization and encoding directed on parsing of Unix and
Linux shell commands. We describe the rationale behind the need for a new
approach with specific examples when conventional Natural Language Processing
(NLP) pipelines fail. Furthermore, we evaluate our methodology on a security
classification task against widely accepted information and communications
technology (ICT) tokenization techniques and achieve significant improvement
of an F1-score from 0.392 to 0.874.

##  1 Introduction

One of the most common interfaces that system engineers and administrators use
to manage computers is the command line. Numerous interpreters called _shells_
allow applying the same operational logic across various sets of operating
systems. Bourne Shell (abbreviated _sh_), Debian Almquist shell (_dash_), Z
shell (_zsh_), and Bourne Again Shell (_bash_) are ubiquitous interfaces to
operate Unix systems, known for speed, efficiency, ability to automate and
integrate the diversity of tasks.

Contemporary enterprises rely on auditd telemetry from Unix servers, including
execve syscall data describing executed shell commands. Generally, this data
is analyzed using static, manually defined signatures for needs like intrusion
detection. There is sparse evidence of the ability to use this information
source efficiently by modern data analysis techniques, like machine learning
or statistical inference. Leading ICT companies underline the relevance of the
aforementioned problem and perform internal research to address this issue
[5].

Complexity and malleability are key challenges in pre-processing shell
commands. The structure has many intricate details, like aliases, different
prefixes, and order and values of the text, which make commands condensed and
fast to input, but time-consuming when reading and interpreting them.

In this paper, we present a _Shell Language Processing (SLP)_
111https://github.com/dtrizna/slp library, showing how it performs feature
extraction from raw shell commands and successfully use it as input for
different machine learning models. The shell command-specific syntax and
challenges are discussed in Section 2, inner working, and features of our
pipeline are covered in Section 3. Sections 4 and 5 discuss a specific
application case and provides performance evaluation of different encoding
techniques.

##  2 Shell specific challenges

The syntax of shell commands depends on different Linux binary implementations
and the way they handle input parameters. Standard techniques like the
tokenize method from the _nltk_ package would result in wrong tokens since
shell language heavily deviates from natural language. To start with, spaces
do not always separate different parts of the command. Some commands like sed
take a raw regular expression as a parameter, space (and any other special
character) will not necessarily mean the start of a next token:

      sed ’s/^chr//;s/\..* / /’ filename

On the contrary, java takes flags without spaces at all, knowing where its
parameter name ends:

      java -Xms256m -Xmx2048m -jar remoting.jar

Such malleability in syntactic patterns possess a significant challenge for
the successful parsing of shell command lines. We know two libraries that
attempt to address such specifics for bash - _bashlex_
222https://github.com/idank/bashlex and _bashlint_
333https://github.com/skudriashev/bashlint, however none of them does its job
perfectly. We utilize bashlex for our needs as a primary parsing source since
it provides heuristics for tokenization of the most general patterns of shell
commands. Still, there are multiple problems in the bashlex library’s original
syntax analysis process, for example in the "command within a command" case
(known by shell syntax $(cmd) or c̀md`) like in:

      export IP=$(dig +short example.com)

Such syntax is not handled by bashlex, where an embedded command is treated as
a single element. Therefore we implement additional syntactic logic wrapped
around bashlex’s object classes to handle this and other problematic cases.

##  3 Encoding

Subsequently, we decided to look forward to different ways of representing
data numerically. To produce arrays out of textual data we implement (a)
label, (b) one-hot, and (c) term frequency-inverse document frequency (TF-IDF)
encodings. Label encoding is built on top of the scikit-learn [1], whereas the
one-hot and TF-IDF encodings are implemented natively.

Having the tokenization and encoding now as operational functionalities, we
were ready to provide a user-friendly interface to utilize the underlying
code. Therefore, we created dedicated Python classes that formed the core of
our interface library. The tokenization interface is available via
ShellTokenizer() class. Besides _bashlex_ , we utilized a _Counter_ object
from the collections package to store unique tokens and their appearance
count. The Counter allows working conveniently with the data concerning
various visualizations. Further encoding is available by ShellEncoder(), which
class allows to generate different encoding methods and returns a _scipy_
sparse array. Substantially, all preprocessing pipeline can be achieved within
four lines of code:

    st = ShellTokenizer()
    corpus, counter = st.tokenize(shell_commands)

    se = ShellEncoder(corpus=corpus,
                      token_counter=counter,
                      top_tokens=100)
    X_enc = se.tfidf()

At this stage X_enc can be supplied to fit() method of API-interface supported
by machine learning (ML) models in libraries like scikit-learn [1] or even
AutoML realizations like TPOT [3]. As a result, every administrator, security
analyst, or even non-technical manager working with a Unix-like system may
parse shell data for ML-based analytics using our library. Only basic Python
coding skills and no knowledge of conventional Natural Language Processing
(NLP) pipelines are needed.

##  4 Experimental setup

Assessment of tokenization and encoding quality is done on the security
classification problem, where we train an ML model to distinguish malicious
command samples from benign activity. Legitimate commands consist from
_nl2bash_ dataset [4], which represents a shell commands collected from
question-answering forums like stackoverflow.com or administratively focused
cheat-sheets.

We perform the collection of malicious samples by ourselves, accumulating
harmful examples across penetration testing and hacking resources that
describe how to perform enumeration of Linux targets and acquire reverse shell
connections from Unix hosts444For example
https://blog.g0tmi1k.com/2011/08/basic-linux-privilege-escalation/. All
commands within the dataset are normalized. Domain names are replaced by
example.com and all IP addresses with 1.1.1.1, since in our evaluation we want
to focus on the command interpretability. We advice to perform a similar
normalization even in production applications, otherwise ML model will overfit
training data.

For classification, we train a gradient boosting ensemble of decision trees,
with the specific realization from XGBoost library [2]. During the analysis of
tokenization we do not implement a validation, ergo use full dataset for
training and compute metrics on the same data. Conversely, during the
evaluation of encoding techniques, we implement a 10 fold cross-validation, so
the resulting metrics are the mean across all validation passes.

##  5 Evaluation

First experiments were conducted to assess the quality of our tokenization. We
have tokenized aforementioned dataset using our ShellTokenizer, with
alternatives from NLTK WordPunctTokenizer, and WhiteSpaceTokenizer which are
known to be used in ICT industry for log parsing. Then all the three corpora
are encoded using the same term frequency-inverse document frequency (TF-IDF)
realization.

Tokenizer | AUC | F1 | Precision | Recall
---|---|---|---|---
SLP (ours) | 0.994 | 0.874 | 0.980 | 0.789
WordPunct | 0.988 | 0.392 | 1.0 | 0.244
WhiteSpace | 0.942 | 0.164 | 1.0 | 0.089
Table 1: Comparison of tokenization tecnhiques on security classification
task: SLP, WordPunctTokenizer, WhiteSpaceTokenizer.

Security classification results are available in Table 1. We see that
conventional tokenization techniques fail to distinguish crucial syntactic
patterns of commands, therefore both cases are biased towards the majority
class of benign samples (with high precision and low recall). This situation
is unacceptable for tasks like security classification - a model that fails to
detect malicious samples at all (false-negatives) cannot be deployed in a
production environment. On the contrary, our tokenizer achieves
_significantly_ higher recall values, and, consequently, F1-score (0.874
versus 0.392 from the closest alternative).

We consider on the evaluation of different encoding techniques. Tests with our
tokenization implementation are done against three encoding schemes - TF-IDF,
one hot, and label encoding. Empirical evidence shows that none of the
encoding techniques has a clear preference over the others, therefore, all
three encoding types are implemented within the library since even basic logic
like label encoding can yield the best results on specific data types and
problem statements. We encourage analysts to experiment with various shell
preprocessing techniques to understand which way benefits their pipelines.

##  6 Conclusions

In this article, we presented custom tokenization and encoding techniques
focused on Unix shell commands. We describe the rationale of the dedicated
tokenization approach, with specific shell command examples where conventional
NLP techniques fail, and briefly cover the inner working of our library. To
distinguish this technique from known existing pipelines we evaluate the
security classification task, with a custom dataset collected from real-world
samples across the web and an efficient ensemble model. According to acquired
metrics, our model achieves a significant improvement of the F1-score.

## References

  * Buitinck et al. [2013] L. Buitinck, G. Louppe, M. Blondel, F. Pedregosa, A. Mueller, O. Grisel, V. Niculae, P. Prettenhofer, A. Gramfort, J. Grobler, R. Layton, J. VanderPlas, A. Joly, B. Holt, and G. Varoquaux.  API design for machine learning software: experiences from the scikit-learn project.  In _ECML PKDD Workshop: Languages for Data Mining and Machine Learning_ , pages 108–122, 2013.
  * Chen and Guestrin [2016] T. Chen and C. Guestrin.  Xgboost.  _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , Aug 2016.  doi: 10.1145/2939672.2939785.  URL http://dx.doi.org/10.1145/2939672.2939785.
  * Le et al. [2020] T. T. Le, W. Fu, and J. H. Moore.  Scaling tree-based automated machine learning to biomedical big data with a feature set selector.  _Bioinformatics_ , 36(1):250–256, 2020.
  * Lin et al. [2018] X. V. Lin, C. Wang, L. Zettlemoyer, and M. D. Ernst.  Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system, 2018.
  * Patel et al. [2020] A. Patel, Z. Kunik, Z. Kocur, J. Bedziechowska, B. Nawrotek, P. Piasecki, and M. Kowiel.  Detecting adversarial behaviour by applying nlp techniques to command lines.  https://blog.f-secure.com/command-lines/, 2020.