# Minimum Separator Reconfiguration

Guilherme C. M. Gomes  Department of Computer Science, Federal University of
Minas Gerais, Belo Horizonte, Brazil††thanks:
<EMAIL_ADDRESS>Clément Legrand-Duchesne  LaBRI, CNRS,
Université de Bordeaux, Bordeaux, France.††thanks<EMAIL_ADDRESS>Reem Mahmoud  Virginia Commonwealth University, Richmond, VA, USA††thanks:
<EMAIL_ADDRESS>Amer E. Mouawad  Department of Computer Science, American
University of Beirut, Beirut, Lebanon††thanks<EMAIL_ADDRESS>Yoshio Okamoto
Graduate School of Informatics and Engineering, The University of Electro-
Communications, Chofu, Japan††thanks<EMAIL_ADDRESS>Vinicius F. dos
Santos  Department of Computer Science, Federal University of Minas Gerais,
Belo Horizonte, Brazil††thanks<EMAIL_ADDRESS>Tom C.
van der Zanden  Department of Data Analytics and Digitalisation, Maastricht
University, Maastricht, The Netherlands††thanks:
<EMAIL_ADDRESS>
###### Abstract

We study the problem of reconfiguring one minimum $s$-$t$-separator $A$ into
another minimum $s$-$t$-separator $B$ in some $n$-vertex graph $G$ containing
two non-adjacent vertices $s$ and $t$. We consider several variants of the
problem as we focus on both the token sliding and token jumping models. Our
first contribution is a polynomial-time algorithm that computes (if one
exists) a minimum-length sequence of slides transforming $A$ into $B$. We
additionally establish that the existence of a sequence of jumps (which need
not be of minimum length) can be decided in polynomial time (by an algorithm
that also outputs a witnessing sequence when one exists). In contrast, and
somewhat surprisingly, we show that deciding if a sequence of at most $\ell$
jumps can transform $A$ into $B$ is an NP-complete problem. To complement this
negative result, we investigate the parameterized complexity of what we
believe to be the two most natural parameterized counterparts of the latter
problem; in particular, we study the problem of computing a minimum-length
sequence of jumps when parameterized by the size $k$ of the minimum
$s$-$t$-separators and when parameterized by the number of jumps $\ell$. For
the first parameterization, we show that the problem is fixed-parameter
tractable, but does not admit a polynomial kernel unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$. We complete the picture by designing
a kernel with $\mathcal{O}(\ell^{2})$ vertices and edges for the length $\ell$
of the sequence as a parameter.

##  1 Introduction

We study the problem of computing reconfiguration sequences between minimum
$s$-$t$-separators. A set $S$ of vertices in a graph $G$ is an _$s$
-$t$-separator_ if vertices $s$ and $t$ are separated in $G-S$, i.e, $s$ and
$t$ belong to different components of $G-S$. A _minimum $s$-$t$-separator_ is
an $s$-$t$-separator of minimum size. We always let $k$ denote the size of a
minimum $s$-$t$-separator in $G$. The token jumping (TJ-) (resp. token sliding
(TS-)) Minimum Separator Reconfiguration (MSR) problem is defined as follows.
Given a graph $G$ and minimum $s$-$t$-separators $A$ and $B$, the goal is to
determine if there exists a sequence of sets $A=S_{1},S_{2},\dots,S_{r}=B$,
such that $S_{i}$ is a minimum $s$-$t$-separator,
$S_{i}:=(S_{i-1}\setminus\\{v\\})\cup\\{u\\}$ for some $v\in S_{i-1}$, and
$u\in V(G)\setminus S_{i-1}$ (resp. $u\in N_{G-S_{i-1}}(v)$) for every
$i\in[r]\setminus\\{1\\}$.

### Motivation.

Reconfiguration problems arise in various applications and, as a result, have
gained considerable attention in recent literature [1, 2, 11, 21]. They appear
in power supply problems, such as operating switches in a network to transform
between different arrangements of power supply from stations to homes without
causing a blackout [20]. They also show up in evolutionary biology, such as in
the transformation of genomes via mutations [27]. Moreover, reconfiguration
problems contribute to numerous fields of study, such as computational
geometry with polygon reconfiguration [6], or statistical physics with the
transformation of a particle’s spin system [8]. At the same time, vertex
separators are useful in the factorization of sparse matrices [31], as well
as, partitioning hypergraphs [22]. They also lend themselves to problems in
cyber security and telecommunication [23], bioinformatics and computational
biology [17], and many divide-and-conquer graph algorithms [14]. Given the
importance of vertex separators, we believe that it is a natural question to
study the problem of reconfiguration between different vertex separators.

### Related work.

Gomes, Nogueira, and dos Santos [18] initiated the study of the problem of
computing reconfiguration sequences between $s$-$t$-separators, $A$ and $B$,
without restricting the size of the separators (to minimum). We call the
corresponding problem Vertex Separator Reconfiguration (VSR). They show that
for token sliding, checking if $A$ can be transformed to $B$, i.e., Vertex
Separator Reconfiguration, is a PSPACE-complete problem even on bipartite
graphs. In contrast, under the token jumping model the problem becomes NP-
complete for bipartite graphs.

### Our results.

Unlike the VSR problem, the requirement in the MSR problem that the separators
in the reconfiguration sequence must be minimum introduces a lot of structure.
In particular, we can rely on the duality between minimum separators and
disjoint paths, observing that tokens are always constrained to move on a set
of disjoint $s$-$t$-paths, which we call canonical paths. Using this property,
we prove that, in an (optimal) solution, tokens always move “forward” towards
their target locations and we never need to take a step back. This immediately
prevents the problems from being PSPACE-complete since this gives a
(polynomial) bound on the length of a solution. In fact, the “always-forward”
property immediately implies a greedy algorithm that decides whether we can
reconfigure one $s$-$t$-separator into another or not for both the token
sliding and token jumping models. We then turn our attention to finding
shortests reconfiguration sequences. While TS-MSR is still solvable in
polynomial-time, finding an optimal solution for the TJ-MSR problem is shown
to be -complete by a reduction from Vertex Cover; finding the largest set of
vertices that can be “skipped” by jumping over them is “similar” to finding a
minimum vertex cover.

We give a complete characterization of the (parameterized) complexity of the
TJ-MSR problem for its natural parameterizations. In particular, we complement
our -hardness result by showing that the problem of finding a shortest
sequence of token jumps is fixed-parameter tractable when parameterized by
$k$, the size of a minimum separator; this is accomplished by further
exploiting the structure imposed by the separators’ minimality as yes-
instances have pathwidth bounded by $\mathcal{O}{k}$. Unfortunately, unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$, the problem admits no polynomial
kernel under this parameterization. Finally, we show that if we parameterize
the problem by the length of the reconfiguration sequence, $\ell$, then we
obtain a kernel with $\mathcal{O}(\ell^{2})$ vertices and edges.

### Open problems.

It remains an interesting open question whether the jumping variant of the VSR
problem is always in NP or whether the problem is PSPACE-complete on general
graphs. Recall that, when restricted to bipartite graphs, TS-VSR is PSPACE-
complete while TJ-VSR is NP-complete [18]. We note that this rather intriguing
disparity in complexity between the two models is an artifact of the
complexity of the Vertex Cover Reconfiguration problem on bipartite graphs
[24]; vertex covers in a bipartite graph $G=(L\cup R,E)$ correspond (one-to-
one) to $s$-$t$-separators in the graph $G^{\prime}$ obtained from $G$ by
adding a vertex $s$ adjacent to every vertex in $L$ and a vertex $t$ adjacent
to every vertex in $R$.

######  Open Problem 1.

Is the Vertex Separator Reconfiguration problem under the token jumping model
in NP?

From the viewpoint of parameterized complexity, it is known that the Vertex
Cover Reconfiguration problem (under both the jumping and sliding models) is
fixed-parameter tractable when parameterized by the vertex cover size [29].
Unfortunately, this does not imply any positive result for the reconfiguration
problem of (non-minimum) $s$-$t$-separators. However, it was shown in [28]
that Vertex Cover Reconfiguration is W[1]-hard when parameterized by $\ell$,
the length of a reconfiguration sequence, even when restricted to bipartite
graphs. The model that the reduction is based on is the so-called token
addition/removal model but the reduction can be adapted for the jumping and
sliding models. We provide such adaptations in the appendix, which imply
W[1]-hardness (of Vertex Cover Reconfiguration parameterized by $\ell$ and
restricted to bipartite graphs) under the token jumping and token sliding
models111There are two variants of the problem that one can consider under
token sliding, i.e., either we allow multiple tokens to occupy the same vertex
or not. (Appendix A). Therefore, the reconfiguration problem for non-minimum
$s$-$t$-separators, i.e., Vertex Separator Reconfiguration, is also W[1]-hard
when parameterized by $\ell$ (under both models). We conclude this section
with what we believe is the most relevant open question in this direction.

######  Open Problem 2.

Is the Vertex Separator Reconfiguration problem (under either the token
jumping or token sliding model) fixed-parameter tractable when parameterized
by the size of the separators?

We note that if we parameterize by both the size of the separators and the
length of a reconfiguration sequence then, if we additionally assume that $A$
and $B$ are minimal, the problem of computing a sequence of minimal separators
transforming $A$ to $B$ is fixed-parameter tractable (for both token jumps and
token slides). The algorithm consists of first applying the treewidth
reduction theorem of [25] followed by a reduction to the model checking
problem in order to exploit Courcelle’s dynamic programming machinery for
graphs of bounded treewidth [7]. We omit all the details and simply observe
that the treewidth reduction theorem outputs a graph (of bounded treewidth)
that preserves both the vertices participating in minimal $s$-$t$-separators
as well as the structure of the graph induced by those vertices (which is
required for token sliding). Once we obtain the aforementioned graph, we can
convert the reconfiguration problem into a model checking problem by creating
a monadic second-order formula that existentially quantifies over the required
number of $s$-$t$-separators and verifies that all the necessary conditions
(e.g., jumping, sliding, separation) are satisfied by the sequence of sets.

##  2 Preliminaries

We denote the set of natural numbers by $\mathbb{N}$ and, for
$n\in\mathbb{N}$, we let $[n]=\\{1,2,\dots,n\\}$.

### Graphs.

We assume that each graph $G$ is finite, simple, and undirected. We let $V(G)$
and $E(G)$ denote the vertex set and edge set of $G$, respectively. The _open
neighborhood_ of a vertex $v$ is denoted by $N_{G}(v)=\\{u\in
V(G)\mid\\{u,v\\}\in E(G)\\}$ and the _closed neighborhood_ by
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For a set $S\subseteq V(G)$ of vertices, we
define $N_{G}(S)=\bigcup_{v\in S}N_{G}(v)\setminus S$ and
$N_{G}[S]=N_{G}(S)\cup S$. The subgraph of $G$ _induced_ by $S$ is denoted by
$G[S]$, where $G[S]$ has vertex set $S$ and edge set $\\{\\{u,v\\}\in E(G)\mid
u,v\in S\\}$. We let $G-S=G[V(G)\setminus S]$.

A _walk_ of length $q$ from $v_{0}$ to $v_{q}$ in $G$ is a vertex sequence
$v_{0},\dots,v_{q}$ such that $\\{v_{i},v_{i+1}\\}\in E(G)$ for all
$i\in\\{0,\dots,q-1\\}$. It is a _path_ if all vertices are distinct. An _$s$
-$t$-path_ is one with endpoints $s$ and $t$. Two $s$-$t$-paths $P_{1}$ and
$P_{2}$ are _(internally) disjoint_ if $V(P_{1})\cap V(P_{2})=\\{s,t\\}$. The
following is a celebrated theorem attributed to Menger [26] and later
generalized and made algorithmic by Ford and Fulkerson [15].

######  Theorem 1.

The size of a minimum $s$-$t$-separator is equal to the maximum number of
pairwise internally disjoint $s$-$t$-paths. Moreover, a maximum set of
pairwise internally disjoint $s$-$t$-paths can be computed in polynomial time.

### Parameterized complexity.

A _parameterized problem_ $Q$ is a subset of $\Sigma^{*}\times\mathbb{N}$,
where the second component denotes the _parameter_. A parameterized problem is
_fixed-parameter tractable_ with respect to a parameter $\kappa$, FPT for
short, if there exists an algorithm to decide whether $(x,\kappa)\in Q$ in
time $f(\kappa)\cdot|x|^{\mathcal{O}(1)}$, where $f$ is a computable function.

We say that two instances are _equivalent_ if they are both yes-instances or
both no-instances. A _kernelization algorithm_ , or a _kernelization_ for
short, is a polynomial-time algorithm that reduces an input instance
$(x,\kappa)$ into an equivalent instance $(x^{\prime},\kappa^{\prime})$ such
that $|x^{\prime}|,\kappa^{\prime}\leq f(\kappa)$, for some computable
function $f$. Such $x^{\prime}$ is called a _kernel_. Every fixed-parameter
tractable problem admits a kernel, however, possibly of exponential or worse
size. For efficient algorithms it is therefore most desirable to obtain
kernels of polynomial, or even linear size.

The _W -hierarchy_ is a collection of parameterized complexity classes
$\textsf{FPT}\subseteq\textsf{W[1]}\subseteq\ldots\subseteq\textsf{W[t]}$. The
conjecture $\textsf{FPT}\subsetneq\textsf{W[1]}$ can be seen as an analogue of
the conjecture that $\textsf{P}\subsetneq\textsf{NP}$. Therefore, showing
hardness in the parameterized setting is usually accomplished by establishing
an FPT-reduction from a W-hard problem. We refer to the textbooks [9, 12] for
extensive background on parameterized complexity.

##  3 Preprocessing and general observations

We let $(G,s,t,A,B)$ denote an instance of the  Minimum Separator
Reconfiguration problem, where $A$ and $B$ are minimum $s$-$t$-separators of
size $k$. The model, i.e., jumping vs. sliding, will be clear from the
context. We begin by making some general observations (that hold for both the
jumping and sliding models) about the structure of sequences of minimum
$s$-$t$-separators which we make extensive use of. We also describe some
preprocessing operations: we assume they have been applied on any instance in
the rest of the paper. We begin by introducing the notion of canonical paths,
which describe the possible locations for each token.

######  Definition 2 (Canonical paths).

Let $A$ and $B$ denote the starting and target separators, respectively. We
begin by fixing a maximum set of pairwise internally disjoint $s$-$t$-paths,
which has size $k=|A|$ (since $A$ is a minimum separator). We may assume that
all paths are _chordless_ , i.e., if two vertices of the same path are
adjacent the edge connecting them is part of the path; if a path is not
chordless we can decrease the length of the path by shortcutting along the
chord. We repeat this procedure until all paths are chordless; this terminates
since in each iteration the total number of vertices involved in the paths
decreases. We call these $k$ chordless pairwise internally disjoint
$s$-$t$-paths $P_{1},\ldots,P_{k}$ the _canonical paths_.

Note that canonical paths might not be uniquely defined; there may be multiple
ways to choose $k$ chordless pairwise internally disjoint $s$-$t$-paths. It
suffices to fix any set of such paths as canonical.

######  Lemma 3.

Let $S$ be a minimum $s$-$t$-separator. Then, $S$ contains exactly one vertex
of each canonical path.

###### Proof.

The set $S$ has to contain at least one vertex of each path, since otherwise
there would be an $s$-$t$-path in $G-S$. Since the number of paths is equal to
the size of a minimum separator and the paths are vertex disjoint, it has to
be exactly one of each. ∎

The next observation follows immediately from Lemma 3.

######  Observation 4.

For both token sliding and token jumping, each token is confined to its
respective canonical path and in the case of sliding, a token can only slide
to either one of its two neighbors along its canonical path.

Thus, our view of the problem is that we are sliding (resp. jumping) tokens
along a set of $k$ paths and that each token is confined to its respective
path. We now show that we can always slide (resp. jump) a token in the
direction of the target separator $B$ and never have to do a “backward” move.

Let $L(i)$ denote the number of vertices on the canonical path $P_{i}$,
including $s$ and $t$. Let $u_{i,1},\dots u_{i,L(i)}$ denote the vertices on
the canonical path $P_{i}$ in the order in which they appear on it, with
$u_{i,1}=s$ and $u_{i,L(i)}=t$. Let $a_{i}$ and $b_{i}$ denote the indices
such that $V(P_{i})\cap A=\\{u_{i,a_{i}}\\}$ and $V(P_{i})\cap
B=\\{u_{i,b_{i}}\\}$, i.e., $a_{i}$ is the index of the starting vertex of the
token on $P_{i}$ and $b_{i}$ the index of the goal vertex for this token. Let
$l_{i}=\min(a_{i},b_{i})$ and $r_{i}=\max(a_{i},b_{i})$. We first show that,
in any (shortest) reconfiguration sequence, we only need to consider
configurations of tokens in which, for all $i$, the token on the path $P_{i}$
remains between (or on) $u_{i,l_{i}}$ and $u_{i,r_{i}}$.

$s$$t$$u_{i,a}$$u_{i,\phi(x_{i})}$$u_{j,\phi(x_{j})}$$u_{j,b}$ Figure 1: $P$
is in blue and $P^{\prime}$ is highlighted in orange.

######  Lemma 5.

For all $i\in[k]$, let $\phi_{i}$ be the function such that for all
$1<a<L(i)$,

$\phi_{i}(a):=\left\\{\begin{array}[]{ll}l_{i}&\text{if }a<l_{i},\\\
r_{i}&\text{if }a>r_{i},\\\ a&\text{otherwise}.\end{array}\right.$

Let $f(u_{i,a}):=u_{i,\phi_{i}(a)}$. The image by $f$ of a minimum
$s$-$t$-separator is a minimum $s$-$t$-separator.

###### Proof.

Given a set $X=\\{u_{i,x_{i}}\mid i\in[k]\\}$, let
$\operatorname{Left}(X)=\bigcup_{i}\\{u_{i,a}\mid a<x_{i}\\}$.

Let $X=\\{u_{i,x_{i}}\mid i\in[k]\\}$ be an $s$-$t$-separator. Assume that
$Y=f(X)$ is not an $s$-$t$-separator. Let $P$ be an $s$-$t$-path in $G-Y$.

Let $u_{i,a}$ be the last vertex of $P$ belonging to $\operatorname{Left}(Y)$.
Let $u_{j,b}$ be the first vertex of $P$ lying on a canonical path after
$u_{i,a}$. We have $u_{j,b}\notin\operatorname{Left}(Y)$ and thus
$b>\phi_{j}(x_{j})$. Note that $a\neq\phi_{i}(x_{i})$ and
$b\neq\phi_{j}(x_{j})$ by definition of $P$. Let $P^{\prime}$ be the path in
$G$ going from $s$ to $u_{i,a}$ via $P_{i}$, then to $u_{j,b}$ via $P$ and
finally to $t$ via $P_{j}$; see Figure 1.

We have $i\neq j$ since otherwise $P^{\prime}$ would be an $s$-$t$-path in
$G-A$ (respectively $G-B$ or $G-X$) if $\phi_{i}(x_{i})=a_{i}$ (respectively
$\phi_{i}(x_{i})=b_{i}$ or $\phi_{i}(x_{i})=x_{i}$).

We cannot have $a<x_{i}$ and $x_{j}<b$ at the same time since otherwise
$P^{\prime}$ would be an $s$-$t$-path in $G-X$. Without loss of generality,
assume that $x_{i}\leq a$. As a result, $x_{i}\leq a<\phi_{i}(x_{i})=l_{i}$.
We must have $b<l_{j}$ since otherwise $P^{\prime}$ would be an $s$-$t$-path
in $G-A$ or $G-B$. Thus, $b<l_{j}\leq\phi_{j}(x_{j})$ which contradicts the
aformentioned property that $b>\phi_{j}(x_{j})$ and proves that $f(X)$ is an
$s$-$t$-separator. ∎

######  Corollary 6.

In both the token jumping and token sliding models, if there exists a
reconfiguration sequence from $A$ to $B$, then there exists a shortest
sequence such that, for any $i$, the $i^{\textrm{th}}$ token remains between
$l_{i}$ and $r_{i}$ at all times. As a result, deleting all vertices on
canonical paths that are not beteween $l_{i}$ and $r_{i}$ and replacing them
by the edges $\\{\\{s,l_{i}\\}\mid 1\leq i\leq k\\}\cup\\{\\{r_{i},t\\}\mid
1\leq i\leq k\\}$ yields an equivalent instance.

###### Proof.

Two $s$-$t$-separators differing only by a token jump (resp. slide) are mapped
by $f$ to two $s$-$t$-separators that are either equal or differing by only a
token jump (resp. slide). Thus, applying $f$ to all separators in the
reconfiguration sequence, we get a reconfiguration sequence with the claimed
property. ∎

Given a vertex $u_{i,x}$ on a canonical path $P_{i}$, we define the set
$F(u_{i,x})$ as the set of vertices of $P_{i}$ between $u_{i,x}$ and
$u_{i,b_{i}}$ (see Fig. 2). We say that a jump (resp. slide) from $u_{i,a}$ to
$u_{i,b}$ is _forward_ if $u_{i,b}\in F(u_{i,a})$. Intuitively, this means
that a jump (resp. slide) is forward if it moves the token closer to its
target location (along the canonical path) without going past it.

$s$$t$$u_{i,a_{i}}$$u_{i,x}$$u_{i,b_{i}}$$u_{j,b_{j}}$$u_{j,y}$$u_{j,a_{j}}$
Figure 2: $F(u_{i,x})$ is highlighted in orange and $F(u_{j,y})$ in blue.

######  Lemma 7 (Forward-moving lemma).

If there exists a reconfiguration sequence from $A$ to $B$, then there exists
a shortest sequence $\mathcal{S}$ of jumps (resp. slides) going from $A$ to
$B$ containing only forward jumps (resp. slides).

###### Proof.

We proceed by induction on the length of a shortest sequence. We prove the
case of jumps only, and the case of slides is similar.

If $A=B$, there is nothing to prove. Otherwise, let $\mathcal{S}$ be a
shortest sequence of jumps going from $A$ to $B$. By Corollary 6, we can
assume that the first jump of $\mathcal{S}$ is a forward jump. Let
$A^{\prime}$ be the separator obtained after this jump. The tail of
$\mathcal{S}$ is a shortest sequence of jumps between $A^{\prime}$ and $B$ and
by induction, it may be replaced with a shortest sequence that only contains
forward jumps. ∎

##  4 Polynomial-time algorithms

The forward-moving lemma immediately implies that several problems can be
solved in polynomial time by a greedy algorithm.

######  Theorem 8.

A minimum-length sequence of token slides reconfiguring one minimum
$s$-$t$-separator to another can be computed in polynomial time.

###### Proof.

Since slides are reversible, doing any slide can never turn a yes-instance
into a no-instance. Thus, we can greedily apply moves that slide a token
forward. Since we never need to do a backward slide, this always finds a
solution if one exists. Moreover, this is optimal: the paths are chordless, so
any slide can only advance a token one step towards its target position, and
since there are no backward slides, the solution is optimal. ∎

######  Theorem 9.

A (feasible, but not necessarily minimum-length) sequence of token jumps
reconfiguring one minimum $s$-$t$-separator to another can be computed in
polynomial time.

###### Proof.

Jumps are also reversible, so doing a jump can never turn a yes-instance into
a no-instance. Again, we can greedily apply forward jumps. Since a solution
never needs to contain a backwards jump, this yields a feasible solution if
one exists. ∎

In the case of token jumping, the solution produced by the greedy algorithm is
not necessarily optimal (not guaranteed to be a shortest sequence of jumps);
by choosing a different order for the jumps, it might be possible to make
“longer” jumps, i.e., jumping over more vertices. In fact, we show that
deciding whether a sequence of at most $\ell$ jumps can tranform one minimum
$s$-$t$-separator into another is an NP-complete problem.

##  5 Hardness of finding short sequences of jumps

First, we note that the problem of deciding whether a sequence of at most
$\ell$ jumps between two minimum $s$-$t$-separators exists is in NP. Indeed,
Lemma 7 implies that the length of a reconfiguration sequence cannot exceed
$|V(G)|$; we can therefore directly use a reconfiguration sequence as a
certificate.

We show NP-hardness by reducing the Vertex Cover problem. Given a graph
$G=(V,E)$ and the size $\kappa$ of a desired vertex cover, we construct our
instance $(G^{\prime},s,t,A,B)$ as follows. We first create a copy of the
graph $G$, and for every $v\in V(G)$ we add two additional vertices
$s_{v},t_{v}$ and edges $\\{s_{v},v\\},\\{v,t_{v}\\}$. We further add vertices
$s,t$ and for all $v\in V(G)$, edges $\\{s,s_{v}\\},\\{t_{v},t\\}$; see Figure
3. We ask whether we can reconfigure the $s$-$t$-separator $A=\\{s_{v}\mid
v\in V(G)\\}$ to the separator $B=\\{t_{v}\mid v\in V(G)\\}$ using at most
$|V(G)|+\kappa$ token jumps.

Note that the canonical paths are of the form $\\{s,s_{v},v,s_{t},t\mid v\in
V(G)\\}$.

$s$$t$$s_{v}$$v$$t_{v}$$\cdot$$\cdot$$\cdot$$G$$A$$B$ Figure 3: The graph
$G^{\prime}$ formed from $G$ (highlighted in orange), along with the initial
and target separators $A$ and $B$ (highlighted in blue), respectively.

######  Lemma 10.

If there exists a reconfiguration sequence from $A$ to $B$ in $G^{\prime}$
consisting of at most $|V(G)|+\kappa$ token jumps, then $G$ has a vertex cover
of size at most $\kappa$.

###### Proof.

Since $A$ and $B$ are disjoint, every token must jump at least once, implying
that we must use at least $|V(G)|$ jumps if every token jumps directly to its
destination. Now let $\\{u,v\\}\in E(G)$. We claim that at some point during
the reconfiguration sequence there should be a token on either $u$ or $v$.
Otherwise, both tokens on $s_{v}$ and $s_{u}$ must jump directly to their
destinations (since they are confined to move along their respective canonical
paths). Without loss of generality, assume that the token on $s_{u}$ jumps to
$t_{u}$ first. Then, there is an $s$-$t$-path $s,s_{u},u,v,t_{v},v$; so, the
configuration of tokens is not a separator and we have a contradiction.
Therefore, for each edge in $G$, at least one of its endpoints requires that
its corresponding token in $A$ performs an extra jump to an intermediate
vertex in $G^{\prime}$, i.e., to that endpoint (before jumping to its final
destination). Since at most $\kappa$ tokens can jump twice, $G$ must have a
vertex cover of size at most $\kappa$. ∎

######  Lemma 11.

If $G$ has a vertex cover of size at most $\kappa$, then there exists a
reconfiguration sequence from $A$ to $B$ in $G^{\prime}$ consisting of at most
$|V(G)|+\kappa$ token jumps.

###### Proof.

Let $C$ be a vertex cover of $G$ of size at most $\kappa$. We first jump all
tokens on vertices $\\{s_{v}\mid v\in C\\}$ to their corresponding
intermediate vertices $\\{v\mid v\in C\\}$. Next, for all vertices $v\in
V(G)\setminus C$, the tokens at $s_{v}$ directly jump to their destinations,
followed by the remaining tokens jumping from the intermediate vertices to
their destinations. Since tokens always stay on their corresponding canonical
paths, any $s$-$t$-path must use at least the vertices $s,s_{v},v,u,t_{u},t$
for some $u,v\in V(G)$. Suppose (towards a contradiction) that at some point
there are no tokens on any of the vertices $s_{v},v,u,t_{u}$. This means that
there must be a token on $t_{v}$ (since there is no token on $s_{v},v$) and on
$s_{u}$ (since there is no token on $t_{u}$ nor on $u$). However, due to the
way the sequence of jumps was defined, whenever there is a token on some
vertex $t_{v}$ and a token on some vertex $s_{u}$, there are tokens forming a
vertex cover of the subgraph induced by $V(G)$. This implies that there is a
token on at least one of $u$ or $v$, which is a contradiction. ∎

######  Theorem 12.

Deciding whether a sequence of at most $\ell$ token jumps can tranform one
minimum $s$-$t$-separator into another is an NP-complete problem.

###### Proof.

The proof follows from the fact that the problem is both NP-hard (Lemmas 10
and 11) and in NP (Lemma 7). ∎

##  6 Preprocessing for token jumping

In this section, we describe some preprocessing rules that can be applied to
the token jumping variant of Minimum Separator Reconfiguration. In the
remainder of this paper, we assume that all instances are preprocessed
according to these rules. We first show that we can reduce the graph so that
it contains no vertices which are not on the canonical $s$-$t$-paths.

######  Lemma 13.

Given an instance $(G,s,t,A,B)$ of Minimum Separator Reconfiguration in the
token jumping model, it is possible to compute in polynomial time an
equivalent instance $(G^{\prime},s,t,A,B)$ in which all vertices are on the
(chordless) canonical paths and the minimum $s$-$t$-separator size is
preserved. Moreover, all vertices in $A\cup B$ are adjacent to either $s$ or
$t$.

###### Proof.

We define a graph $G^{\prime}$ on a subset of the vertex set of $G$; in the
new instance of Minimum Separator Reconfiguration that we construct $s$, $t$,
$A$, and $B$ stay the same.

By Corollary 6, we can assume that in an (optimal) solution, the token on
canonical path $P_{i}$ only moves between $u_{i,l_{i}}$ and $u_{i,r_{i}}$. We
build the graph $G^{\prime}$ as follows. We take vertices $s$ and $t$ and, for
each $i$, we take the vertices of the canonical path $P_{i}$ between (and
including) $u_{i,l_{i}}$ and $u_{i,r_{i}}$ and add them to $G^{\prime}$.Now,
whenever two non-adjacent vertices $u,v$ of $G^{\prime}$ are connected by a
path in $G$ and its internal vertices (i.e., the vertices which are not the
endpoints of the path) are disjoint from the vertices of $G^{\prime}$, we
connect $u$ and $v$ by an edge in $G^{\prime}$. Note that in particular this
implies that we add the edges of the canonical paths; see Figure 4.

$s$$t$$u_{1,l_{1}}$$u_{1,r_{1}}$$u_{2,l_{2}}$$u_{2,r_{2}}$$u_{k,l_{k}}$$u_{k,r_{k}}$$\cdot$$\cdot$$\cdot$
$s$$t$$u_{1,l_{1}}$$u_{1,r_{1}}$$u_{2,l_{2}}$$u_{2,r_{2}}$$u_{k,l_{k}}$$u_{k,r_{k}}$$\cdot$$\cdot$$\cdot$
Figure 4: Top: The graph $G$ (vertices and paths colored gray are deleted in
$G^{\prime}$). Bottom: The graph $G^{\prime}$ formed from $G$ (gray paths in
$G$ are replaced by edges in $G^{\prime}$).

We claim that a configuration of tokens in which all tokens are between
$u_{i,l_{i}}$ and $u_{i,r_{i}}$ on their respective canonical paths $P_{i}$ is
an $s$-$t$-separator in $G$ if and only if it is one in $G^{\prime}$. Consider
an $s$-$t$-path $P$ in $G$. This path corresponds to an $s$-$t$-path
$P^{\prime}$ in $G^{\prime}$: if we consider only those vertices on the path
that are in $G^{\prime}$, that sequence of vertices is an $s$-$t$-path in
$G^{\prime}$ since the consecutive vertices in that sequence are connected by
a path in $G$ whose internal vertices are disjoint from $G^{\prime}$ and thus
there exist edges containing the consecutive vertices in the sequence. Thus, a
configuration of tokens which is an $s$-$t$-separator in $G^{\prime}$ is also
an $s$-$t$-separator in $G$, since any configuration of tokens that hits
$P^{\prime}$ also hits $P$ since the vertices of $P^{\prime}$ are a subset of
the vertices of $P$.

Conversely, consider an $s$-$t$-path $P^{\prime}$ in $G^{\prime}$: recall that
the edges of $G^{\prime}$ (which are not in $G$) correspond to paths in $G$ so
the $s$-$t$-path $P^{\prime}$ corresponds to an $s$-$t$-walk $W$ of $G$. Any
configuration of tokens in which all tokens are between $u_{i,l_{i}}$ and
$u_{i,r_{i}}$ on their respective canonical paths that hits $W$ must do so in
a vertex that is also in $P^{\prime}$ since the vertices that are in
$G^{\prime}$ are precisely the vertices on canonical paths between
$u_{i,l_{i}}$ and $u_{i,r_{i}}$. Thus, any configuration of tokens (in which
all tokens are between $u_{i,l_{i}}$ and $u_{i,r_{i}}$ on their respective
canonical paths) that is an $s$-$t$-separator in $G$ is also an
$s$-$t$-separator in $G^{\prime}$.

Clearly, a token jump in $G$ (in which tokens remain between $u_{i,l_{i}}$ and
$u_{i,r_{i}}$ on their respective canonical paths) is also a token jump in
$G^{\prime}$ and vice versa. Note that this does not hold under the token
sliding model; adding an edge between two vertices of the same canonical path
that are non-adjacent in $G$ (but connected by some paths) will allow for a
slide in $G^{\prime}$ that is not possible in $G$. The minimum separator size
in $G^{\prime}$ has not decreased since we still have the same number of
disjoint paths (and also not increased since we have shown that the separators
of $G$ are also separators of $G^{\prime}$).

It is possible that this process creates chords on the canonical paths, making
them no longer canonical. In this case, we can shorcut the canonical paths
along the chords, and repeat the above process. Since the number of vertices
decreases in each iteration, this eventually terminates. We eventually end up
with the claimed, equivalent instance. This takes polynomial time. ∎

Going forward, we assume that all graphs are preprocessed according to these
rules. We next observe that to ensure that a configuration of tokens forms a
valid $s$-$t$-separator it suffices to check the existence of relatively
simple $s$-$t$-paths.

######  Lemma 14.

To check whether a configuration of tokens that assigns exactly one token to
each canonical path forms an $s$-$t$-separator, it suffices to check whether
there exists an $s$-$t$-path that from $s$, follows one of the canonical
paths, then follows one edge (a _crossing edge_) from that canonical path to
another, and then follows that canonical path to $t$.

###### Proof.

Suppose we have an $s$-$t$-path $P$ of the form

$s,\ldots,u_{i,l},u_{j,m},\dots,u_{j,n},u_{q,o},\dots,t$

where $i\neq j$, $j\neq q$, i.e., an $s$-$t$-path that has more than one
crossing edge. Let $P^{\prime}$ be the $s$-$t$-path that goes from $s$ along
the canonical path $P_{j}$ to $u_{j,m}$ and then follows $P$ to $t$. Let
$P^{\prime\prime}$ be the $s$-$t$-path that follows $P$ from $s$ to $u_{j,m}$
and then runs along the canonical path $P_{j}$ to $t$; see Figure 5 (left). If
some configuration of tokens (in which exactly one token is on each canonical
path) does not hit $P$, then it also does not hit either $P^{\prime}$ or
$P^{\prime\prime}$: there is only one token on the path $P_{j}$, so it must be
either before $u_{j,m}$ or after $u_{j,n}$. Therefore, it suffices to check
only $P^{\prime}$ and $P^{\prime\prime}$ and both $P^{\prime}$ and
$P^{\prime\prime}$ have fewer crossing edges than $P$. Repeatedly applying
this procedure, we see that it is sufficient to check only those $s$-$t$-paths
with at most one crossing edge. Since exactly one token is assigned to each
canonical path, $s$-$t$-paths with no crossing edges are automatically covered
and thus it suffices to check only those $s$-$t$-paths with exactly one
crossing edge. ∎

$s$$t$$u_{i,l}$$u_{j,m}$$u_{j,n}$$u_{q,o}$

$s$$t$$v$$u_{i,q}$$u_{i,l}$$u_{i,m}$

Figure 5: Left: An example of Lemma 14. The path $P$ is highlighted in orange,
$P^{\prime}$ is the dashed blue path, and $P^{\prime\prime}$ is the dashed
green path. Note that $P,P^{\prime},P^{\prime\prime}$ all overlap between
$u_{j,m}$ and $u_{j,n}$. Right: An example of Lemma 15. If the $s$-$t$-path
highlighted in orange (resp. blue) is not hit by a token, replacing the edge
$\\{v,u_{i,l}\\}$ with $\\{v,u_{i,m}\\}$ (resp. $\\{v,u_{i,q}\\}$) in that
path gives another $s$-$t$-path not hit by a token.

We now show that it suffices to consider instances in which all vertices have
degree at least $3$ and at most $2k$, where $k\geq 3$ is the size of the
minimum separator (for $k\leq 2$, the problem can be solved in polynomial time
by a simple algorithm that computes a shortest path in an auxiliary graph $H$
having one vertex for each of the at most $n^{2}$ $s$-$t$-separators and where
two vertices of $H$ share an edge whenever the corresponding
$s$-$t$-separators are one reconfiguration step away from each other).

######  Lemma 15.

Given an instance $(G,s,t,A,B)$ of Minimum Separator Reconfiguration in the
token jumping model, it is possible to compute in polynomial time an
equivalent instance $(G^{\prime},s,t,A,B)$ in which all vertices have degree
at least $3$ and at most $2k$, where $k=|A|=|B|$ (assuming $k\geq 3$). In
particular, every vertex can have at most two neighbors on each canonical
path.

###### Proof.

Consider a vertex $v$ that is adjacent to three distinct vertices
$u_{i,q},u_{i,l},u_{i,m}$ that belong to the same canonical path (different
from the canonical path of $v$) and where $q<l<m$. Then, the edge
$\\{v,u_{i,l}\\}$ can be deleted; if there is an $s$-$t$-path that uses
$\\{v,u_{i,l}\\}$ as a crossing edge and this path is not hit by some
configuration of tokens, then, depending on the location of the token on path
$P_{i}$, that configuration of tokens fails to hit either the $s$-$t$-path
that uses $\\{v,u_{i,q}\\}$ as a crossing edge or the $s$-$t$-path that uses
$\\{v,u_{i,m}\\}$ as a crossing edge; see Figure 5 (right). Thus, we can
assume that each vertex is adjacent to at most $2$ vertices on each canonical
path, and thus, each vertex has degree at most $2k$. We can also assume,
without loss of generality, that there are no vertices of degree $0$ or $1$
and that any vertex $v$ of degree exactly two is deleted and replaced by an
edge connecting the two neighbors of $v$ on its canonical path. ∎

We proceed by showing that we can always assume that the source and target
minimum $s$-$t$-separators, i.e., $A$ and $B$, are disjoint.

######  Lemma 16.

Given an instance $(G,s,t,A,B)$ of Minimum Separator Reconfiguration in the
token jumping model, it is possible to compute in polynomial time an
equivalent instance $(G^{\prime},s,t,A^{\prime},B^{\prime})$ in which
$A^{\prime}\cap B^{\prime}=\emptyset$.

###### Proof.

Let $v$ be a vertex in both $A$ and $B$. By the forward-moving lemma, i.e.,
Lemma 7, we know that in any shortest reconfiguration sequence from $A$ to $B$
the token on $v$ does not move. Hence, we can simply delete the vertex $v$
from the graph (reducing the minimum separator size by one) and we adjust $A$
and $B$ accordingly (by deleting $v$ from each) to obtain an equivalent
instance $(G-\\{v\\},s,t,A\setminus\\{v\\},B\setminus\\{v\\})$. We repeat this
procedure until the source and target $s$-$t$-separators are disjoint. Since
each iteration takes polynomial time and we can repeat the process at most $k$
times, the whole procedure takes polynomial time. ∎

We conclude this section by formalizing the notion of unskippable vertices; a
notion that will be useful in many of our subsequent results (and that was
already implicity used in Lemma 10). Given an instance $(G,s,t,A,B)$, we say
that $v\in V(G)\setminus(A\cup B\cup\\{s,t\\})$ is _unskippable_ if for every
sequence (if any exist) of minimum $s$-$t$-separators that transforms $A$ to
$B$, there exists at least one $s$-$t$-separator $S$ in the sequence such that
$v\in S$. In other words, there is no transformation from $A$ to $B$ that can
skip over $v$ and not jump a token onto $v$ at some point. Similarly, we say
that a set $U\subseteq V(G)\setminus(A\cup B\cup\\{s,t\\})$ of vertices is
_unskippable_ whenever there exists at least one $s$-$t$-separator $S$ in
every reconfiguration sequence (from $A$ to $B$) such that $|U\cap S|\geq 1$.

######  Lemma 17.

Let $(G,s,t,A,B)$ be an instance of Minimum Separator Reconfiguration in the
token jumping model. A vertex $v\in V(G)\setminus(A\cup B\cup\\{s,t\\})$
having two neighbors on a canonical path other than its own is unskippable. If
$u,v\in V(G)\setminus(A\cup B\cup\\{s,t\\})$, $u,v$ belong to two different
canonical paths, and $\\{u,v\\}\in E(G)$, then $\\{u,v\\}$ is unskippable.

###### Proof.

Let $v$ be a vertex on some canonical path $P$ having two neighbors on
canonical path $P^{\prime}\neq P$. Let $u_{1}$ and $u_{2}$ denote the
neighbors of $v$ on $P^{\prime}$ such that $u_{1}$ appears before $u_{2}$ on
$P^{\prime}$ ($u_{1}$ is closer to $s$ on $P^{\prime}$). Assume that there
exists a sequence of jumps transforming $A$ to $B$ such that the token on $P$
never jumps to vertex $v$. Consider the first separator $S$ of the sequence in
which the token on $P$ is after $v$ (on some vertex of $P$ that is closer to
$t$ along $P$). If the token on $P^{\prime}$ is before $u_{2}$ then we have an
$s$-$t$-path using the crossing edge $\\{v,u_{2}\\}$; see Figure 6(a). Hence,
the token on $P^{\prime}$ must be on or after $u_{2}$. But in that case,
consider the separator $S^{\prime}$ that occurs right before $S$ in the
sequence. In $S^{\prime}$, the token on $P$ is before $v$ and the token on
$P^{\prime}$ is on or after $u_{2}$. We again get a contradiction as we can
now construct an $s$-$t$-path using the crossing edge $\\{v,u_{1}\\}$. We
therefore conclude that $v$ is unskippable.

Now, consider $u,v\in V(G)\setminus(A\cup B\cup\\{s,t\\})$ such that $u$ and
$v$ belong to different canonical paths, say $P_{u}$ and $P_{v}$, and
$\\{u,v\\}\in E(G)$. Assume that there exists a sequence transforming $A$ to
$B$ such that no token ever jumps on neither $u$ nor $v$. Then, there must
exist a first $s$-$t$-separator in the transformation such that either the
token on $P_{u}$ is after $u$ and the token on $P_{v}$ is before $v$ or vice
versa. In either case, we get an $s$-$t$-path and the required contradiction;
see Figure 6(b). We then conclude that $\\{u,v\\}$ is unskippable. ∎

$s$$t$$v$$u_{1}$$u_{2}$$s$$t$$v$$u_{1}$$u_{2}$ (a)

$s$$t$$v$$u_{1}$$u_{2}$ (b)

Figure 6: (a) Black vertices represent tokens. Left: The position of tokens in
$S$. The bottom token must come after $u_{2}$ in $S$ to hit the $s$-$t$-path
highlighted in orange. Right: The position of tokens in $S^{\prime}$. The
$s$-$t$-path highlighted in orange is not hit by any token. (b) Orange
vertices represent one possible token configuration and blue vertices
represent another. For the orange (resp. blue) configuration, we get the
$s$-$t$-path in orange (resp. blue).

##  7 Fixed-parameter tractability for parameter $k$

In this section, we show that finding a shortest sequence for the token
jumping variant of Minimum Separator Reconfiguration is fixed-parameter
tractable with respect to the size $k$ of minimum $s$-$t$-separators. We do so
by constructing a path decomposition of the graph from a not necessarily
shortest sequence of token jumps, and then proceed by dynamic programming on
that path decomposition. We shall work towards proving the following.

######  Theorem 18.

The optimization version of Minimum Separator Reconfiguration in the token
jumping model is fixed-parameter tractable with respect to the size $k$ of a
minimum separator.

###### Proof.

Recall that, by Lemma 13, we can preprocess the graph so that all vertices are
on the canonical paths and the vertices in $A$ and $B$ are adjacent to (at
least one of) $s$ or $t$. By Lemma 15, each vertex in $G$ has degree at least
$3$ and at most $2k$ and, by Lemma 16, we know that $A\cap B=\emptyset$.

For simplicity, we remove the vertices $s$ and $t$ from the graph and in this
section view the problem as follows. Given two disjoint sets of vertices $A$
and $B$ which are connected by $k=|A|=|B|$ disjoint paths, the aim is to
reconfigure the tokens from $A$ to $B$ under the constraint that at no point
should a path from any vertex in $A$ to any vertex in $B$ open up (i.e., not
be hit by some token).

First observe that this is a sufficient condition. This is because, as $A$ and
$B$ are disjoint $s$-$t$-separators, any $s$-$t$-path must pass through both
$A$ and $B$ (and thus, includes a path from some vertex in $A$ to some vertex
in $B$ as a subpath).

To see that this is also necessary, suppose some configuration of tokens (that
is an $s$-$t$-separator) does not hit some path $P$ from some vertex $a\in A$
to some vertex $b\in B$. We can assume this path only intersects $A$ in $a$
and only intersects $B$ in $b$ since otherwise, we could take a subpath of
$P$. Then, without loss of generality, both $a$ and $b$ should be adjacent to
$s$ (they could also both be adjacent to $t$, but since the configuration of
tokens is an $s$-$t$-separator, it cannot be the case that one of them is
adjacent to $s$ while the other is to $t$). This implies $a$ and $b$ are on
different canonical paths (due to the preprocessing and the chordless nature
of the canonical paths, the vertices in $A$ and $B$ are the only vertices that
can connect to $s$ and $t$, so if $a\in A$ and $b\in B$ are on the same
canonical path, one of them must connect to $s$ and the other to $t$ since
otherwise, the canonical path would not be an $s$-$t$-path), and there is a
path $P^{\prime}$ (a subpath of $P$) connecting these canonical paths that
does not pass through any vertex of $A$ or $B$. Let $a^{\prime}$ be the vertex
on the canonical path of $a$ that is in $B$. We can now find an $s$-$t$-path
that will contradict the assumption that $A$ is an $s$-$t$-separator: $t$ is
adjacent to $a^{\prime}$; we walk along the canonical path of $a^{\prime}$
towards $a$ until we reach $P^{\prime}$ (which must happen before we reach the
token on $A$), then follow $P^{\prime}$ to the canonical path of $b$, then
walk along it towards $b$ and finally reach $s$. This $s$-$t$-path is not hit
by $A$ and we reach a contradiction: $A$ is not an $s$-$t$-separator.
Therefore, we can conclude that any configuration of tokens that is an
$s$-$t$-separator hits every path from any vertex in $A$ to any vertex in $B$.

Note that similarly to Lemma 14, it suffices to check for paths from some
vertex in $A$ to some vertex in $B$ with exactly one crossing edge.

Because we have gotten rid of $s$ and $t$, we can now pick one _consistent_
ordering of the vertices of the canonical paths. Previously, some vertices of
$A$ may have been adjacent to $t$ and some others adjacent to $s$, which means
that the order of vertices as they appear on the paths from $A$ to $B$ might
not have been the same order in which they appear from $s$ to $t$. Going
forward, we assume the vertices of the canonical paths are numbered from $A$
to $B$, i.e., $u_{i,j}$ is the $j^{\textrm{th}}$ vertex of the
$i^{\textrm{th}}$ canonical path from $A$ to $B$, in particular $u_{i,1}\in A$
is the first (leftmost) vertex of the path, $u_{i,L(i)}\in B$ the last
(rightmost) vertex of the path.

Since we only need to consider forward jumps, jumps are always from some
vertex $u_{i,j}$ to another vertex $u_{i,q}$ with $q>j$. We say a token on
vertex $u_{i,j}$ is before, on or after vertex $u_{i,q}$ if $j<q,j=q$, or
$j>q$, respectively.

### Path decomposition.

We now construct a path decomposition of $G$. We start by computing a (not
necessarily shortest) token jumping solution using Theorem 9. By Lemma 7, we
can assume this solution only contains forward jumps. The token jumping
solution directly gives a path decomposition of $G$: if $S_{i}$ and $S_{i+1}$
are consecutive separators in the reconfiguration sequence, then they differ
in the replacement of one vertex $u_{j,q}$ by one vertex $u_{j,l}$ which are
both from the same canonical path. That is,
$S_{i}=X\cup\\{u_{j,q}\\},S_{i+1}=X\cup\\{u_{j,l}\\}$ for some $X$. We replace
this jump by the sequence of bags
$X\cup\\{u_{j,q}\\},X\cup\\{u_{j,q},u_{j,q+1}\\},X\cup\\{u_{j,q+1},u_{j,q+2}\\},\ldots,X\cup\\{u_{j,l-1},u_{j,l}\\},X\cup\\{u_{j,l}\\}$.
The largest bag in this decomposition contains $k+1$ vertices, and hence the
width of this path decomposition is $k$.

Since the token jumping sequence moves all tokens from one endpoint of each
canonical path to the other, we see that the bags of the decomposition contain
all vertices of each path (and thus all vertices of the graph) and that (since
there are only forward jumps) the bags containing each specific vertex induce
a connected subpath of the decomposition. By construction, each edge of a
canonical path is contained in the decomposition. Note that the canonical
paths are chordless and therefore the only remaining edges we have to concern
ourselves with are the edges connecting vertices on distinct canonical paths.

For an edge $\\{u,v\\}$ that connects two vertices $u,v$ that are on different
canonical paths, recall that a token cannot move past $u$ before the other
token has moved at least onto $v$ or vice versa (Lemma 17). This implies that
either $u,v$ occur together in some separator of the reconfiguration sequence
(and hence $u,v$ appear together in some bag of the decomposition) or that at
some point in the reconfiguration sequence, either $u$ or $v$ appears in some
separator and then the other vertex is jumped over (we say a vertex $v$ is
_jumped over_ if a token jumps from vertex $x$ to vertex $y$ and the vertex
$v$ appears along the canonical path from $x$ to $y$). In this case, there is
also a bag containing both $u$ and $v$.

Note that the path decomposition is constructed in such a way that

  * •

The first bag is equal to $A$;

  * •

The last bag is equal to $B$;

  * •

Vertices are introduced in the order they appear on the canonical paths (in
particular, the jump from a previously introduced vertex to a newly introduced
one would be a forward jump).

### Dynamic programming.

As is customary for dynamic programming on path decompositions, we process the
bags of the decomposition in order, and for each bag $X$, we consider the
graph induced by the vertices in $X$ and all vertices in bags to the left of
$X$. We call this graph $G_{X}$. As usual, we assume the decomposition is
given in _nice_ form, i.e., each bag differs from the previous either by the
addition of one vertex (we say that such a vertex is _introduced_) or the
removal of one vertex (we say such a vertex is _forgotten_). We refer the
reader to [3, 19, 30] for an extensive background on pathwidth, (nice) path
decompositions, and their applications.

A _partial solution_ $\Pi$ is a sequence of configurations of tokens
$C_{1},\ldots,C_{l}$, starting with $A$, so that each configuration $C_{i}$ is
obtained from the previous one by one of the following operations:

  1. 1.

removing a token from a canonical path and replacing it by another token
further along the same canonical path (i.e., a forward jump);

  2. 2.

removing a token from a canonical path completely,

under the condition that if $v$ is the rightmost vertex of a canonical path in
$G_{X}$ (note that this implies $v\in X$), then $v$ may not be reachable from
any vertex of $A$ in the subgraph $G_{X}-C_{i}$ unless there is no token on
the canonical path of $v$ in $C_{i}$. Intuitively, $C_{i}$ should separate $A$
from $X$, except that vertices on canonical paths from which the token has
been removed may be reachable (and, in the case where the bag contains two
vertices from the same canonical path, only the rightmost one needs to be
unreachable).

The operation (1) is just a normal (forward) jump operation of reconfiguration
via token jumping, whereas the operation (2) is necessary to represent a
potential future jump to a vertex that has not yet been introduced.

We now define the _configuration characteristic_ of a configuration of tokens
$C$ with respect to $X$ as follows. For every vertex $v$ in the closed
neighborhood of $X$, we store its _state_ : whether the token on the canonical
path of $v$ is before, on, or after $v$.

Since by Lemma 15 every vertex has degree at most $2k$ there are at most
$3^{2k^{2}+2k}$ distinct characteristics of token configurations.222If for a
vertex $v\in X$ both of its neighbors on the canonical path are also present
in $X$, the state of $v$ itself is implied and so the bound is valid.

The _solution characteristic_ $\mathcal{C}$ of a partial solution $\Pi$ is now
defined as the sequence of characteristics of the token configurations
occurring in $\Pi$, with runs of consecutive duplicate configuration
characteristics removed and replaced with one occurence of the configuration
characteristic. Note that since tokens can only jump forward, we will never
repeat a characteristic. Thus, the number of distinct characteristics of
partial solutions is at most $(3^{2k^{2}+2k}+1)!$.

Our dynamic programming table will store for each solution characteristic the
minimum number of configurations of a partial solution having that
characteristic. We now show how to, given the dynamic programming table for
the previous bag, the corresponding table for the next bag (which may be
either an introduce or forget bag) may be computed.

### Introduce.

Let $X^{\prime}$ be the previous bag in the decomposition and let
$X=X^{\prime}\cup\\{v\\}$ be the next bag where vertex $v$ is being
introduced. Consider a partial solution $\Pi$ for $G_{X}$. If $\Pi$ does not
contain any jump to $v$, then $\Pi$ is also a partial solution for
$G_{X^{\prime}}$: $G_{X^{\prime}}$ differs from $G_{X}$ only by the deletion
of $v$; deleting $v$ cannot make any vertex reachable. Moreover, if $u$ is the
previous vertex on the canonical path of $v$, then $u$ cannot have been
reachable in any configuration in which the token on its canonical path had
not been removed since then we could have reached $v$ from $u$.

Otherwise, if $\Pi$ contains a jump to $v$, then, because all jumps are
forward, this is the last jump operation on vertex $v$ (though it may possibly
be followed by the removal of the token on $v$). Consider $\Pi^{\prime}$ that
is obtained from $\Pi$ by replacing the last jump of the token to $v$ with a
removal of the token (and ignoring the possible duplicate subsequent removal
of the token on $v$). We claim that $\Pi^{\prime}$ is a partial solution for
$G_{X^{\prime}}$: if in $\Pi^{\prime}$, at any time a path opens up (in
$G_{X^{\prime}}$) from some vertex in $A$ to some vertex in $X^{\prime}$
(excluding the canonical path of $v$), then, since $X^{\prime}\subseteq X$,
this path would also be an $A$-$X$-path in $\Pi$ (and $G_{X}$).

Thus, we can obtain all possible partial solutions for $G_{X}$ by considering
the partial solutions for $G_{X^{\prime}}$ and either

  1. 1.

doing nothing;

  2. 2.

replacing the removal of the token on the canonical path of $v$ with a jump to
$v$; or

  3. 3.

replacing the removal of the token on the canonical path of $v$ with a jump to
$v$ _and_ at some point in the future, adding a removal of (the token on) $v$.

Intuitively, (1) corresponds to jumping over $v$, (3) corresponds to jumping
onto it and later moving away and (2) is necessary to represent that the token
on $v$ has reached its target location (i.e., $v\in B$) and will not make
further jumps.

$A$$X^{\prime}$$u$$v$$G_{X^{\prime}}$Introduce$A$$X$$u$$v$$G_{X}$

$A$$X^{\prime}$$u$$v$$G_{X^{\prime}}$Forget$A$$X$$u$$v$$G_{X}$

Figure 7: An overview of the process of introducing and forgetting a vertex.

######  Lemma 19.

Let $\mathcal{C}^{\prime}$ be a characteristic of a partial solution
$\Pi^{\prime}$ with respect to $G_{X^{\prime}}$. Then, the characteristic
$\mathcal{C}=\mathcal{C}^{\prime}$ and the legality of the partial solution
$\Pi$ with respect to $G_{X}$ obtained from $\Pi^{\prime}$ by doing nothing
depends only on, and can be computed from, $\mathcal{C}^{\prime}$.

###### Proof.

Consider the characteristic for $\Pi^{\prime}$ (with respect to
$G_{X^{\prime}}$). Since (by the basic properties of path decompositions) $v$
only has neighbors in $X^{\prime}$, the only information in the characteristic
for $\Pi$ (w.r.t. $G_{X}=G_{X\cup\\{v\\}}$) that we are missing is the state
of $v$. However, the vertex preceding $v$ on its canonical path is also in $X$
(because the vertices are introduced in the order they appear on the canonical
paths) and we can infer the state of $v$ from it: if its state is “before” or
“on” then $v$ is “before”, otherwise the token has been removed and $v$ is
“after”.

To check whether the partial solution is legal when we extend it by doing
nothing, we have to check whether an $A$-$X$-path opens up at any point. We
only have to worry about paths that use $v$ since other paths are already
precluded by $\Pi^{\prime}$ being a (legal) partial solution. For this it
suffices to check that in no characteristic, $v$ gets state “after” while one
of its neighbors still has state “before.” ∎

$A$$X$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{4}$$v_{9}$

$A$$X$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{4}$$v_{9}$

$A$$X$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{4}$$v_{9}$

$A$$X$$v_{1}$$v_{2}$$v_{3}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{4}$$v_{9}$

Figure 8: The above sequence of token configurations (partial solution) has
the following solution characteristic. 1st (Top): $v_{2}=$ on, $v_{3}=$
before, $v_{4}=$ before, $v_{5}=$ at, $v_{8}=$ before, $v_{9}=$ before. 2nd &
3rd: $v_{2}=$ on, $v_{3}=$ before, $v_{4}=$ before, $v_{5}=$ after, $v_{8}=$
before, $v_{9}=$ before. 4th (Bottom): $v_{2}=$ on, $v_{3}=$ before, $v_{4}=$
before, $v_{5}=$ after, $v_{8}=$ after, $v_{9}=$ on. Since the 2nd and 3rd
configuration characteristic are the same, the solution characteristic will
consist of just three configuration characteristics. Note that this figure is
only intended to illustrate the notion of solution characteristic and does not
represent a legal partial solution, since $v_{4}$ becomes reachable when we
jump from $v_{5}$ to $v_{6}$.

######  Lemma 20.

Let $\mathcal{C}^{\prime}$ be a characteristic of a partial solution
$\Pi^{\prime}$ with respect to $G_{X^{\prime}}$ that contains the removal of
the token on the canonical path of $v$. Then, the characteristic
$\mathcal{C}$, and the legality of the partial solution $\Pi$ with respect to
$G_{X}$ obtained from $\Pi^{\prime}$ by replacing the removal with a jump to
$v$ depends only on, and can be computed from, $\mathcal{C}^{\prime}$.

###### Proof.

As we argued with the “do nothing” case, the only missing information is the
state of $v$ itself. The state of $v$ can again be inferred from the state of
its predecessor on the path (which is again in $X^{\prime}$): it starts out at
“before” and changes to “on” at the moment the state of its predecessor
changes to “after” (this corresponds to the moment of the removal, which is
replaced by a token jump to vertex $v$).

The characteristics again provide us with enough information that no
$A$-$X$-path is created: similarly to the “do nothing” case, it suffices to
check that no neighbor of $v$ gets state “after” before $v$ has gotten state
“on.” ∎

Note that doing this operation only makes sense if $v\in B$. Otherwise, it
will yield a partial solution that, although valid, can never be extended to a
complete solution to the problem since $v$ will never be able to move again.

######  Lemma 21.

Let $\mathcal{C}^{\prime}$ be a characteristic of a partial solution
$\Pi^{\prime}$ with respect to $G_{X^{\prime}}$ that contains the removal of
the token on the canonical path of $v$. Then, the characteristic $\mathcal{C}$
and the legality of a partial solution $\Pi$ with respect to $G_{X}$ obtained
from $\Pi^{\prime}$ by replacing the removal with a jump to $v$ and adding a
subsequent removal of $v$ depends only on, and can be computed from,
$\mathcal{C}^{\prime}$.

###### Proof.

Again, the only missing information is the state of $v$ itself, which we can
compute as we did before, with the exception that at any point after $v$ has
changed to “on,” we can insert a configuration characteristic into the
sequence in which it changes to “after” (and accordingly, change its state in
all configuration characteristics occuring later on in the sequence to “after”
as well).

To ensure that the newly created configuration is legal, we must (in addition
to the checks previously described) ensure that the state of $v$ does not
change to “after” while the state of one or more of its neighbors is still
“before.” ∎

Note that in the characteristic of $\Pi^{\prime}$, two sucessive configuration
characteristics can correspond to a sequence of multiple moves resulting in
token configurations having the same configuration characteristic. It does not
matter at what exact point in this sequence we insert the jump to $v$, since
this results in the same characteristic for $\Pi$.

This allows us to compute the dynamic programming table after $v$ is
introduced: we go over all solution characteristics in the previous table, try
all ways of extending them as described above, which yields new solution
characteristics together with the number of moves required to reach them (for
accounting purposes, we can charge the jump to the addition of a removal). The
same solution characteristic may be created in several ways (i.e., from
applying different operations to different solution characteristics), and in
this case, in the final table, we store the lowest number of moves required
for any of them.

The optimality of the solution is guaranteed as follows: if $\Pi$ is an
optimal partial solution for $G_{X}$ with characteristic $\mathcal{C}$, then
$\Pi^{\prime}$, which is obtained by replacing the jump to $v$ (if it is
present) with a removal, is optimal for $G_{X^{\prime}}$ with characteristic
$\mathcal{C^{\prime}}$. Otherwise, if some partial solution
$\Pi^{\prime\prime}$ for $G_{X^{\prime}}$ would also have characteristic
$\mathcal{C^{\prime}}$ but use fewer moves, it could be extended in the same
way as $\Pi^{\prime}$ can be extended to obtain a partial solution for $G_{X}$
with the same characteristic as $\Pi$, contradicting the optimality of $\Pi$.

### Forget.

The forget case can be implemented using a simple projection of the stored
information to the neighborhood of $X$, merging configuration characteristics
that occur repeatedly and taking the minimum among partial solutions that end
up getting the same characteristic when projected. Since $X\subseteq
X^{\prime}$, no vertex of $X$ that was not yet reachable in $X^{\prime}$
becomes reachable due to this projection, so all the partial solutions remain
valid.

### Final remarks.

Note that since a solution to the token jumping reconfiguration problem is
also a partial solution for the final bag of the decomposition, we can read
off the desired answer from the dynamic programming table for the final bag.

The table for the starting bag can be computed using brute force. In each
table, there are at most $(3^{2k^{2}+2k}+1)!$ distinct solution
characteristics, and we can compute the possible new characteristics that can
be reached from each in time $\mathcal{O}(3^{2k^{2}+2k}!n^{\mathcal{O}(1)})$,
since the path decomposition has $\mathcal{O}(n)$ bags, this results in an
$\mathcal{O}((3^{2k^{2}+2k}+2)!n^{\mathcal{O}(1)})$-time algorithm, which is
fixed-parameter tractable. ∎

##  8 No polynomial kernel for parameter $k$

We start with some definitions and a refresher on the machinery required for
proving kernelization lower bounds. We use the framework made possible by the
work of Drucker [13], Bodlaender et al. [4, 5], Dell and van Melkebeek [10],
and Fortnow and Santhanam [16].

######  Definition 22.

An equivalence relation $\mathcal{R}$ on $\Sigma^{*}$ is called a _polynomial
equivalence relation_ if the following two conditions hold.

  1. 1.

There is an algorithm that given two strings $x,y\in\Sigma^{*}$ decides
whether $x$ and $y$ belong to the same equivalence class in time polynomial in
$|x|+|y|$.

  2. 2.

For any finite set $S\subseteq\Sigma^{*}$ the equivalence relation
$\mathcal{R}$ partitions the elements of $S$ into at most $(\max_{x\in
S}{|x|})^{\mathcal{O}(1)}$ classes.

######  Definition 23.

Let $L\subseteq\Sigma^{*}$ be a set and let
$Q\subseteq\Sigma^{*}\times\mathbb{N}$ be a parameterized problem. We say that
$L$ _and-cross-composes_ into $Q$ if there is a polynomial equivalence
relation $\mathcal{R}$ and an algorithm that, given $r$ strings
$x_{1},x_{2},\dots,x_{r}$ belonging to the same equivalence class of
$\mathcal{R}$, computes an instance
$(x^{*},\kappa^{*})\in\Sigma^{*}\times\mathbb{N}$ in time polynomial in
$\sum_{i=1}^{r}{|x_{i}|}$ such that:

  1. 1.

$(x^{*},\kappa^{*})\in Q$ if and only if $x_{i}\in L$ for every $1\leq i\leq
r$, and

  2. 2.

$\kappa^{*}$ is bounded by a polynomial in $\max_{i=1}^{r}{|x_{i}|}+\log r$.

######  Theorem 24.

If some set $L\subseteq\Sigma^{*}$ is NP-hard under Karp reductions and $L$
and-cross-composes into the parameterized problem $Q$, then there is no
polynomial kernel for $Q$ unless $\textsf{NP}\subseteq\textsf{coNP/poly}$.

We are now ready to prove the main result of this section:

######  Theorem 25.

There exists an and-cross-composition from Vertex Cover into TJ Minimum
Separator Reconfiguration, parameterized by the minimum size $k$ of an
$s$-$t$-separator. Consequently, when parameterized by $k$, TJ Minimum
Separator Reconfiguration does not admit a polynomial kernel unless
$\textsf{NP}\subseteq\textsf{coNP/poly}$.

###### Proof.

By choosing an appropriate polynomial equivalence relation $\mathcal{R}$, we
may assume that we are given a family of $r$ Vertex Cover instances
$(G_{i},\kappa_{i})$, where $|V(G_{i})|=\mu$ and $\kappa_{i}=\kappa$ for all
$i$. Moreover, we assume, without loss of generality, that each instance of
Vertex Cover was obtained by reducing an instance of $3$-SAT having $N$
variables and $M$ clauses (using the standard reduction that converts
variables to edges and clauses to triangles). This implies that $\kappa=N+2M$
and no graph $G_{i}$ admits a vertex cover of size less than $\kappa$.

We now proceed to the construction of our Minimum Separator Reconfiguration
instance $(H,s,t,A,B)$, where $k=\mu+1$ will be the size of a minimum
separator. The graph $H$ consists of $k$ pairwise internally vertex-disjoint
paths from $s$ to $t$. The paths, i.e., $P_{1},P_{2},\dots,P_{\mu},P_{k}$,
consist of $4r+1$ vertices each (including $s$ and $t$) and correspond to the
canonical paths. Recall that we let $u_{i,1},\dots,u_{i,L(i)}$ denote the
vertices on the canonical path $P_{i}$ in the order in which they appear on
it, with $u_{i,1}=s$ and $u_{i,L(i)}=t$.

The $k$ vertices $\\{u_{1,2},u_{2,2},\ldots,u_{k,2}\\}$ (the vertices adjacent
to $s$) correspond to the starting configuration $A$ and the vertices
$\\{u_{1,L(1)-1},u_{2,L(2)-1},\ldots,u_{k,L(k)-1}\\}$ (the $k$ vertices
adjacent to $t$) correspond to the target configuration $B$. The $\mu$
vertices that come after $A$ (excluding the vertex $u_{k,3}$ in $P_{k}$)
correspond to the vertices of $G_{1}$ and we use them to embed the edges of
$G_{1}$. Note that the vertex $u_{k,3}$ will remain a vertex of degree two
that joins its two neighbors on the canonical path $P_{k}$. We now proceed
with the description of the synchronization gadget that will appear between
every pair of embeddings of graphs $G_{i}$ and $G_{i+1}$. The first
synchronization gadget consists of vertices
$\\{u_{1,5},u_{2,5},\ldots,u_{\mu,5}\\}\cup\\{u_{k,2},u_{k,4},u_{k,6}\\}$. We
add an edge from every vertex in $\\{u_{1,5},u_{2,5},\ldots,u_{\mu,5}\\}$ to
every vertex in $\\{u_{k,2},u_{k,4},u_{k,6}\\}$. Note that the vertices
$u_{1,4}$ to $u_{\mu,4}$ and $u_{1,6}$ to $u_{\mu,6}$ will remain vertices of
degree two. We let $q=7$.

We proceed with the construction as follows. For each graph $G_{i}$, we embed
the edges of the graph over the vertices
$\\{u_{1,q},u_{2,q},\ldots,u_{\mu,q}\\}$. We then add a synchronization gadget
(except when $i=r$) using vertices
$\\{u_{1,q+2},\ldots,u_{\mu,q+2}\\}\cup\\{u_{k,q-1},u_{k,q+1},u_{k,q+3}\\}$.
We add edges from every vertex in $\\{u_{1,q+2},\ldots,u_{\mu,q+2}\\}$ to
every vertex in $\\{u_{k,q-1},u_{k,q+1},u_{k,q+3}\\}$. We then set $q=q+4$ and
proceed to the next graph $G_{i+1}$. For the final synchronization gadget
which preceeds $G_{r}$, we add edge between the vertex $u_{k,q+3}$ and every
vertex in $B\setminus V(P_{k})$. This completes the construction of $H$. We
ask for a reconfiguration sequence of length $\ell=r(k+\kappa)$ (see Figure 9
for more details).

$s$$t$ Figure 9: An overview of the and-cross-composition with $r=3$ and
$k=5$. The orange blobs are $A$ and $B$, the blue blobs represent the graphs
$G_{i}$, and the green vertices and edges represent the synchronization
gadgets.

The intuition behind the construction is similar to the construction showing
NP-hardness in Theorem 12. The extra synchronization gadgets are required to
guarantee the order in which the tokens will cross the vertices corresponding
to each graph $G_{i}$.

We now prove that we have a reconfiguration sequence of (exactly) $\ell$ jumps
from $A$ to $B$ in $H$ if and only if each $G_{i}$ has a vertex cover $C_{i}$
of size (exactly) $\kappa$, $1\leq i\leq r$.

Assume that each $G_{i}$ has a vertex cover $C_{i}$ of size $\kappa$. Then, by
Lemma 11, we know that we can jump the tokens (over any $G_{i}$) from the
preceeding synchronization gadget (or $A$) to the next synchronization gadget
(or $B$) using $k+\kappa$ jumps (with the token on $P_{k}$ always jumping last
to vertex $u_{k,q+3}$, for some $q$). Since we have exactly $r$ graphs to jump
over it follows that we can reconfigure $A$ to $B$ via a sequence of
$\ell=r(k+\kappa)$ token jumps.

For the reverse direction, we know, from Lemma 10, that whenever we are able
to jump all tokens over a graph $G_{i}$ using at most $k+\kappa$ jumps,
$G_{i}$ must have a vertex cover of size at most $\kappa$. Assume that before
any token can jump to either a vertex belonging to some $G_{i}$ or to some
vertex beyond $G_{i}$, it must be the case that all the tokens have reached a
vertex beyond $G_{i-1}$ but before $G_{i}$. In other words, all the tokens
must be on the synchronization gadget between $G_{i-1}$ and $G_{i}$ before any
token can jump onto or beyond $G_{i}$. Combining this assumption with the fact
that no graph $G_{i}$ can have a vertex cover of size less than $\kappa$, we
know that exactly $k+\kappa$ jumps can be used to move the tokens from the
gadget preceeding $G_{i}$ (or from $A$) to the gadget succeeding $G_{i}$ (or
to $B$). Otherwise we need more than $\ell=r(k+\kappa)$ jumps to jump over all
$r$ graphs.

Hence, it remains to show that the synchronization gadgets behave as required
and force all the tokens to reach the same gadget before jumping onto or over
the next graph $G_{i+1}$. First, observe that a synchronization gadget
contains $k$ vertices each on a different canonical path and each having two
neighbors on some canonical path other than its own. This implies that each
such vertex must be occupied by a token at some point in any reconfiguration
sequence, i.e., these are unskippable vertices (Lemma 17). In addition, given
the edges between $\\{u_{1,q+2},\ldots,u_{\mu,q+2}\\}$ and $\\{u_{k,q-1}\\}$
we know that the token on $P_{k}$ must be the last to reach its vertex
$u_{k,q+3}$ on the synchronization gadget; otherwise one of the edges between
$\\{u_{1,q+2},\ldots,u_{\mu,q+2}\\}$ and $\\{u_{k,q-1}\\}$ can be used as a
crossing edge to obtain an $s$-$t$-path. So, assume some token on $P_{i}$
($i\neq k$) jumps forward beyond its corresponding vertex in the
synchronization gadget before the token on $P_{k}$ gets to $u_{k,q+3}$. We can
now construct a path from $t$ to $s$ by simply following $P_{k}$ to
$u_{k,q+3}$, then $u_{k,q+3}$ to $u_{i,q+2}$, and then following the path
$P_{i}$ to $s$; a contradiction. Putting it all together, we know that the
tokens on $P_{1},P_{2},\dots,P_{\mu}$ will each jump to the unskippable vertex
of a synchronization gadget (in some order and staying on their respective
canonical paths) before the token on $P_{k}$ ever reaches its unskippable
vertex in the gadget. Moreover, none of the tokens in the first $\mu$
canonical paths can further jump either backward or forward before the token
on $P_{k}$ reaches its unskippable vertex on the gadget. Hence, only when all
the tokens have reached a certain synchronization gadget, we can start jumping
over the next graph and exactly $k+\kappa$ jumps can be allocated to move the
tokens from the synchronization gadget preceeding $G_{i}$ to the
synchronization gadget succeeding $G_{i}$ (the same is true for jumping from
$A$ to the first synchronization gadget and for jumping from the last
synchronization gadget to $B$). ∎

##  9 Polynomial kernel for parameter $\ell$

In this section, we consider the minimum separator reconfiguration problem
parameterized by the number $\ell$ of allowed token jumps. Formally, given a
graph $G$, minimum $s$-$t$-separators $A$ and $B$ of size $k$, and an integer
$\ell$, the goal is to determine whether there exists a sequence of at most
$\ell$ token jumps transforming $A$ to $B$.

Recall that, by Lemma 13, we can preprocess the graph so that all vertices are
on the canonical paths and the vertices in $A$ and $B$ are adjacent to (at
least one of) $s$ or $t$. Similarly, by Lemma 15, each vertex in $G$ will have
degree at least $3$ and at most $2k$ (with at most two neighbors on each
canonical path) and, by Lemma 16, we know that $A\cap B=\emptyset$. We refer
to an instance satisfying all of the above as a reduced instance.

######  Lemma 26.

In a reduced yes-instance where $\ell$ is the parameter, all the following
properties must be satisfied:

  * •

$A\cap B=\emptyset$ and $|A|=|B|\leq\ell$;

  * •

all vertices are on the (at most $\ell$) canonical paths;

  * •

vertices in $A$ and $B$ are adjacent to (at least one of) $s$ or $t$; and

  * •

each vertex in $G$ has degree at least $3$, degree at most $2\ell$, and at
most two neighbors on each canonical path.

###### Proof.

The lemma follows immediately from the fact that if after obtaining a reduced
instance we have $|A|=|B|>\ell$ then we have a no-instance; as at least
$\ell+1$ jumps are needed. Consequently, the minimum separator size will be at
most $\ell$ and all the remaining properties follow from Lemma 13, Lemma 15,
and Lemma 16. ∎

######  Lemma 27.

Assume that in a reduced instance one of the canonical paths contains more
than $4(\ell+1)^{2}+4$ vertices. Then, the instance is a no-instance.

###### Proof.

Let $P$ denote such a canonical path. We claim that at least $\ell+1$ jumps
are required for the token on $P$. We assume otherwise, i.e, that $\ell$ jumps
or fewer are enough, and work towards a contradiction.

First, recall that if a vertex $v$ on a canonical path is adjacent to two
distinct vertices on another canonical path, then $v$ can never be jumped
over, i.e., $v$ is unskippable (Lemma 17). We decompose $P$ into $\ell+1$
subpaths each consisting of at least $4\ell+4$ vertices (excluding $s$, $t$,
and the initial and target vertices of $A$ and $B$). For the token on $P$ to
reach its final position in at most $\ell$ jumps, it must (at least once) jump
over $2\ell+1$ (consecutive) vertices of $P$ or more (landing on the vertex
$2\ell+2$ away or more). Let us denote those vertices that are jumped over by
$Q$. Moreover, let $S_{i}$ denote the $s$-$t$-separator preceeding the jump
and let $S_{i+1}$ denote the resulting $s$-$t$-separator after the jump.

If $Q$ contains a vertex having two distinct neighbors on another canonical
path, then the vertex is unskippable and we get a contradiction. Hence, every
vertex $v$ of $Q$ (which has degree $3$ or more) can have at most one neighbor
on every canonical path $P^{\prime}\neq P$ (and we know that $v$ must have at
least one neighbor not in $P$). Since $S_{i+1}$ is an $s$-$t$-separator, every
vertex $v\in Q$ can only be adjacent to vertices in $S_{i+1}\setminus V(P)$;
otherwise an $s$-$t$-path can be easily constructed, contradicting the fact
that $S_{i+1}$ is an $s$-$t$-separator. Now, given that $|Q|\geq 2\ell+1$, we
know that there exists at least $3$ distinct vertices in $Q$ all having the
same neighbor in $S_{i+1}\setminus V(P)$. This contradicts the fact that after
our reductions each vertex in $G$ can have at most two distinct neighbors on
any canonical path. ∎

######  Theorem 28.

The optimization version of TJ Minimum Separator Reconfiguration admits a
kernel with $\mathcal{O}(\ell^{2})$ vertices when parameterized by $\ell$, the
length of a reconfiguration sequence.

###### Proof.

First, note that Lemmas 26 and 27 imply a kernel with $\mathcal{O}(\ell^{3})$
vertices; a yes-instance consists of at most $\ell$ canonical paths each
having $\mathcal{O}(\ell^{2})$ vertices.

To obtain the improved bound, we have to refine our analysis slightly and
strengthen the result of Lemma 27. We do so as follows. We partition the
canonical paths into long paths and short paths, where a path is short if it
has at most $4\ell+4$ vertices and it is long otherwise. It is not hard to see
that the number of vertices belonging to short paths is in
$\mathcal{O}(\ell^{2})$.

Now, assume that the total number of vertices on all long canonical paths is
more than $2(2\ell+2)^{2}+2\ell+2$. Then, we can decompose the paths into
subpaths each consisting of $4\ell+4$ vertices except possibly the last
subpath of each long path (we exclude $s$, $t$, and the initial and target
vertices of $A$ and $B$). The number of subpaths with $4\ell+4$ vertices is
therefore at least $\ell+1$ and at least $\ell+1$ jumps are required for the
tokens on long paths to reach their destinations, which implies a no-instance
(the proof being identical to that of Lemma 27). Therefore, the total number
of vertices belonging to long paths is also in $\mathcal{O}(\ell^{2})$, which
concludes the proof.

We can further improve the bounds on the kernel size (for both the number of
vertices and the number of edges), by combining the use of unskippable
vertices with the use of unskippable edges. Let $H$ be the graph obtained from
$G$ by deleting all the edges belonging to the canonical paths, and let
$U_{G}$ denote the set of unskippable vertices in $V(G)\setminus(A\cup
B\cup\\{s,t\\})$. Now, let $M$ be a maximum matching in the graph
$\Gamma=H-(U_{G}\cup A\cup B)$. If $|M|>\ell$ we have a trivial no-instance,
since at least one endpoint of each edge in $M$ must be occupied by a token at
some point, i.e., every edge in $M$ is unskippable. Hence, every vertex of
$\Gamma$ having at least one neighbor is either in $V(M)$ or is adjacent to
some vertex of $V(M)$ (isolated vertices in $\Gamma$ correspond to those
vertices that only have neighbors in $U_{G}\cup A\cup B$). Since $|U_{G}\cup
A\cup B|\leq 3\ell$ and the maximum degree is $2\ell$, we get,
$|V(\Gamma)|\leq|V(M)|+\sum_{v\in V(M)}|N_{\Gamma}(v)|+6\ell^{2}\leq
2\ell+\sum_{v\in V(M)}(\ell-1)+6\ell^{2}\leq 2\ell+2\ell(\ell-1)+6\ell^{2}\leq
2\ell+8\ell^{2}$. Since $V(\Gamma)=V(H)\setminus(U_{G}\cup A\cup B)$ and
$|U_{G}\cup A\cup B|\leq 3\ell$, we have $|V(G)|=|V(H)|=|U_{G}\cup A\cup
B|+|V(\Gamma)|\leq 3\ell+2\ell+8\ell^{2}=5\ell+8\ell^{2}$. In terms of edges,
each edge of $\Gamma$ is incident to a vertex of $M$, so we have that
$|E(\Gamma)|\leq|E(M)|+\sum_{v\in V(M)}|N_{\Gamma}(v)|\leq\ell+2\ell(\ell-1)$
and $|E(H)|=E(\Gamma)+\sum_{v\in U_{G}\cup A\cup
B}|N_{G}(v)|\leq\ell+2\ell(\ell-1)+6\ell^{2}\leq 8\ell^{2}+\ell$. Hence, since
$|V(G)|\leq 2\ell^{2}+3\ell$, we get $|E(G)|\leq|E(H)|+2(2\ell^{2}+3\ell)\leq
8\ell^{2}+\ell+2(2\ell^{2}+3\ell)\leq 12\ell^{2}+7\ell$. ∎

##  10 Concluding Remarks

We studied the minimum $s$-$t$-separator reconfiguration problem through
several lenses. First, we considered the token sliding and token jumping
reconfiguration models, showing that the reachability question is answerable
in polynomial time in both cases. Afterwards, we considered the task of
finding a shortest reconfiguration sequence; we proved that it is easy under
the first model but -complete under the second. To tackle this hardness, we
studied the parameterized complexity of the token jumping version for the
natural parameterizations $k$ (the number of tokens) and $\ell$ (the length of
the sequence). In this context, we designed an algorithm for the $k$
parameterization, a quadratic kernel when parameterized by $\ell$, and showed
that no polynomial kernel exists for $k$ unless
$\NP\subseteq\coNP/\textsf{poly}$.

In terms of future work on minimum $s$-$t$-separator reconfiguration itself,
we are interested in understanding shortest token jumping sequences for some
graph classes, in particular for planar graphs. Other possibilities include
the study of structural parameterizations, such as treewidth, feedback edge
set, and vertex deletion distance metrics (e.g. distance to cluster, clique,
etc). In a different spirit, studying the connectivity of the minimum
$s$-$t$-separator reconfiguration graph might yield different insights than
the ones presented in this paper. Beyond minimum separators, the work of
Gomes, Nogueira, and dos Santos [18] investigated arbitrary $s$-$t$-separator
reconfiguration, but no research has yet been done on bounded size separators.
As such, we believe work on the complexity of reconfiguration of minimum + $r$
$s$-$t$-separators might be of independent interest.

## References

  * [1] Kira Adaricheva, Chassidy Bozeman, Nancy E. Clarke, Ruth Haas, Margaret-Ellen Messinger, Karen Seyffarth and Heather C. Smith  “Reconfiguration graphs for dominating sets”  In _Research Trends in Graph Theory and Applications_ 25, Assoc. Women Math. Ser.  Springer, Cham, 2021, pp. 119–135
  * [2] Akanksha Agrawal, Soumita Hait and Amer E. Mouawad  “On finding short reconfiguration sequences between independent sets”  In _33rd International Symposium on Algorithms and Computation_ 248, LIPIcs. Leibniz Int. Proc. Inform.  Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Paper No. 3914
  * [3] Hans L. Bodlaender  “A Partial _k_ -Arboretum of Graphs with Bounded Treewidth”  In _Theor. Comput. Sci._ 209.1-2, 1998, pp. 1–45  DOI: 10.1016/S0304-3975(97)00228-4
  * [4] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows and Danny Hermelin  “On problems without polynomial kernels”  In _J. Comput. Syst. Sci._ 75.8, 2009, pp. 423–434  DOI: 10.1016/j.jcss.2009.04.001
  * [5] Hans L. Bodlaender, Bart M.. Jansen and Stefan Kratsch  “Kernelization Lower Bounds by Cross-Composition”  In _SIAM J. Discret. Math._ 28.1, 2014, pp. 277–305  DOI: 10.1137/120880240
  * [6] Robert Connelly, Erik D. Demaine and Günter Rote  “Blowing Up Polygonal Linkages”  In _Discrete Comput. Geom._ 30, 2003, pp. 205–239
  * [7] Bruno Courcelle  “The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs”  In _Inf. Comput._ 85.1, 1990, pp. 12–75  DOI: 10.1016/0890-5401(90)90043-H
  * [8] Daniel W. Cranston and Reem Mahmoud  “In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent”  In _European J. Combin._ 104, 2022, pp. Paper No. 10353221
  * [9] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh  “Parameterized Algorithms”  Springer, 2015  DOI: 10.1007/978-3-319-21275-3
  * [10] Holger Dell and Dieter Melkebeek  “Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses”  In _J. ACM_ 61.4, 2014, pp. 23:1–23:27  DOI: 10.1145/2629620
  * [11] Quentin Deschamps, Carl Feghali, František Kardoš, Clément Legrand-Duchesne and Théo Pierron  “Strengthening a theorem of Meyniel”, 2022
  * [12] Rodney G. Downey and Michael R. Fellows  “Parameterized Complexity”, Monographs in Computer Science  Springer, 1999  DOI: 10.1007/978-1-4612-0515-9
  * [13] Andrew Drucker  “New Limits to Classical and Quantum Instance Compression”  In _SIAM J. Comput._ 44.5, 2015, pp. 1443–1479  DOI: 10.1137/130927115
  * [14] Cem Evrendilek  “Vertex separators for partitioning a graph”  In _Sensors_ 8.2, 2008, pp. 635–657
  * [15] Lester R. Ford and Delbert R. Fulkerson  “Flows in Networks”  USA: Princeton University Press, 2010
  * [16] Lance Fortnow and Rahul Santhanam  “Infeasibility of instance compression and succinct PCPs for NP”  In _J. Comput. Syst. Sci._ 77.1, 2011, pp. 91–106  DOI: 10.1016/j.jcss.2010.06.007
  * [17] Bin Fu and Zhixiang Chen  “Sublinear time width-bounded separators and their application to the protein side-chain packing problem”  In _J. Comb. Optim._ 15.4, 2008, pp. 387–407
  * [18] Guilherme C.. Gomes, Sérgio H. Nogueira and Vinícius F. Santos  “Some results on Vertex Separator Reconfiguration”, 2020
  * [19] Daniel J. Harvey and David R. Wood  “Parameters Tied to Treewidth”  In _J. Graph Theory_ 84.4, 2017, pp. 364–385  DOI: 10.1002/jgt.22030
  * [20] Takehiro Ito, Erik D. Demaine, Xiao Zhou and Takao Nishizeki  “Approximability of partitioning graphs with supply and demand”  In _J. Discrete Algorithms_ 6.4, 2008, pp. 627–650
  * [21] Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi and Yoshio Okamoto  “Shortest reconfiguration of perfect matchings via alternating cycles”  In _SIAM J. Discrete Math._ 36.2, 2022, pp. 1102–1123
  * [22] Enver Kayaaslan, Ali Pinar, Ümit Çatalyürek and Cevdet Aykanat  “Partitioning hypergraphs in scientific computing applications through vertex separators on graphs”  In _SIAM J. Sci. Comput._ 34.2, 2012, pp. A970–A992
  * [23] Charles E. Leiserson  “Area-efficient graph layouts”  In _21st Annual Symposium on Foundations of Computer Science_ , 1980, pp. 270–281
  * [24] Daniel Lokshtanov and Amer E. Mouawad  “The Complexity of Independent Set Reconfiguration on Bipartite Graphs”  In _ACM Trans. Algorithms_ 15.1, 2019, pp. 7:1–7:19  DOI: 10.1145/3280825
  * [25] Dániel Marx, Barry O’Sullivan and Igor Razgon  “Finding small separators in linear time via treewidth reduction”  In _ACM Trans. Algorithms_ 9.4, 2013, pp. 30:1–30:35  DOI: 10.1145/2500119
  * [26] Karl Menger  “Zur allgemeinen Kurventheorie”  In _Fundamenta Mathematicae_ 10, pp. 96–115
  * [27] István Miklós and Heather Smith  “Sampling and counting genome rearrangement scenarios”  In _BMC Bioinformatics_ 16, 2015
  * [28] Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman and Sebastian Siebertz  “Vertex Cover Reconfiguration and Beyond”  In _Algorithms_ 11.2, 2018, pp. 20  DOI: 10.3390/a11020020
  * [29] 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
  * [30] Neil Robertson and Paul D. Seymour  “Graph Minors. II. Algorithmic Aspects of Tree-Width”  In _J. Algorithms_ 7.3, 1986, pp. 309–322  DOI: 10.1016/0196-6774(86)90023-4
  * [31] Xie Xian-fen, Gu Wan-rong, He Yi-chen and Mao Yi-jun  “Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation”  In _Computer Science_ 49.6, 2022, pp. 272–279

## Appendices

##  Appendix A W[1]-hardness reduction for parameter $\ell$

######  Theorem 29.

The Vertex Cover Reconfiguration problem parameterized by $\ell$, the length
of a reconfiguration sequence, is W[1]-hard in the token jumping model, even
when restricted to bipartite graphs.

###### Proof.

We reduce the Clique problem to the Vertex Cover Reconfiguration problem on
bipartite graphs (under the token jumping model). Given an instance
$(G,\kappa)$ of Clique, we create a bipartite graph $H$, with parts $L$ (left)
and $R$ (right), as follows. We first add a copy of $V(G)$ to $L$ and another
copy to $R$. We use $L_{V}=\\{u_{1},\ldots,u_{n}\\}$ and
$R_{V}=\\{v_{1},\ldots,v_{n}\\}$ to denote these two sets, respectively. Then,
for each edge $e\in E(G)$, we add a vertex $u_{e}$ in $L$. We use $L_{E}$ to
denote this set. Finally, we add ${\kappa\choose 2}+1$ vertices to $L$ and
${\kappa\choose 2}+1$ vertices to $R$, which we denote by $L_{K}$ and $R_{K}$,
respectively. We proceed by describing the edges of $H$. We add all the edges
$\\{u_{i},v_{i}\\}$, $i\in[n]$, so that the graph induced by $L_{V}\cup R_{V}$
is a matching. We add edges between every vertex in $L_{K}$ and every vertex
in $R_{K}$ such that the graph induced by $L_{K}\cup R_{K}$ is a biclique
$K_{{\kappa\choose 2}+1,{\kappa\choose 2}+1}$. Finally, for every vertex
$v_{e}\in L_{E}$, where $e=\\{v_{i},v_{j}\\}$, we add the edges
$\\{u_{e},v_{i}\\}$ and $\\{u_{e},v_{j}\\}$. This completes the construction
of the bipartite graph $H$.

The corresponding Vertex Cover Reconfiguration instance requires a starting
vertex cover $A$, which we set as $A=L_{V}\cup L_{E}\cup L_{K}=L$, and a
target vertex cover $B$, which we set as $B=L_{V}\cup L_{E}\cup R_{K}$. In
other words, we simply want to switch sides on the biclique so that the tokens
occupy the right side instead of the left. Finally, we require a
reconfiguration sequence of at most $\ell=2{\kappa\choose 2}+2\kappa+1$ jumps.

Assume that $G$ has a clique of size $\kappa$ and let
$C=\\{v_{i_{1}},\ldots,v_{i_{\kappa}}\\}$ denote the vertices of that clique.
Then, we can reconfigure $A$ to $B$ as follows.

  1. 1.

Jump the token on $u_{i_{1}}$ to $v_{i_{1}}$, then the token on $u_{i_{2}}$ to
$v_{i_{2}}$, all the way to the token on $u_{i_{\kappa}}$ to $v_{i_{\kappa}}$
($\kappa$ jumps in total).

  2. 2.

Since $C$ is a clique, we now have ${\kappa\choose 2}$ tokens in $L_{E}$ whose
neighborhood in $R$ is full of tokens. So we can jump those tokens to any
${\kappa\choose 2}$ vertices of $R_{K}$ (${\kappa\choose 2}$ jumps in total).

  3. 3.

Next, we jump any token from $L_{K}$ to the remaining non-occupied vertex from
$R_{K}$ ($1$ jump in total).

  4. 4.

Now, the remaining tokens in $L_{K}$ will jump to $L_{E}$ to replace the lost
tokens (${\kappa\choose 2}$ jumps in total).

  5. 5.

Finally, the $\kappa$ tokens in $R_{V}$ will jump back to their corresponding
vertex in $L_{V}$ ($\kappa$ jumps in total).

For the reverse direction, assume that we have a sequence of at most $\ell$
jumps transforming vertex cover $A$ to vertex cover $B$. We can assume,
without loss of generality, that the tokens in $L_{V}\cup R_{V}$ will each
remain on their corresponding matching edge and no token from
$V(H)\setminus(L_{V}\cup R_{V})$ will ever jump to some vertex in $L_{V}\cup
R_{V}$; otherwise, if some token jumps to a matching edge so that the other
token jumps away, we can simply switch the roles of both tokens and obtain an
equivalent sequence. In other words, we can assume that every vertex cover in
a reconfiguration sequence will have exactly (the same) $n$ tokens in
$L_{V}\cup R_{V}$ (each token never leaving its edge). Now, since $H[L_{K}\cup
R_{K}]$ is a biclique $K_{{\kappa\choose 2}+1,{\kappa\choose 2}+1}$, we know
that any reconfiguration sequence from $A$ to $B$ must contain some vertex
cover $S$ such that $S\cap(L_{K}\cup R_{K})=2{\kappa\choose 2}+1$, with $S\cap
L_{K}={\kappa\choose 2}+1$ and $S\cap R_{K}={\kappa\choose 2}$. From our
previous observation, these additional ${\kappa\choose 2}$ tokens must come
from $L_{E}$. Hence, for any sequence of jumps transforming $A$ to $B$, at
least $2{\kappa\choose 2}+1$ jumps are required for tokens not in $L_{V}\cup
R_{V}$; at least ${\kappa\choose 2}$ jumps from $A$ to $S$ and at least
${\kappa\choose 2}+1$ jumps from $S$ to $B$. Given that $\ell=2{\kappa\choose
2}+2\kappa+1$, we know that at most $\kappa$ tokens from $L_{V}\cup R_{V}$ can
move (and each move will cost two jumps). However, given that $S$ must exist,
moving less than $\kappa$ tokens in $L_{V}\cup R_{V}$ is impossible since we
can never free ${\kappa\choose 2}$ tokens in $L_{E}$; the neighborhood of any
${\kappa\choose 2}$ vertices in $L_{E}$ has size at least $\kappa$. Therefore,
the corresponding $\kappa$ vertices from $R_{V}$ must form a clique in $G$,
which completes the proof. ∎

######  Theorem 30.

If we allow multiple tokens to occupy the same vertex then the Vertex Cover
Reconfiguration problem parameterized by $\ell$, the length of a
reconfiguration sequence, is W[1]-hard in the token sliding, even when
restricted to bipartite graphs.

###### Proof.

We give a reduction from the Multicolored Clique problem. Given an instance
$(G,\kappa)$ of Multicolored Clique, we assume, without loss of generality,
that $V(G)$ is partitioned into $\kappa$ independent sets $V_{1}$, $V_{2}$,
$\ldots$, $V_{\kappa}$, each consisting of $n$ vertices. We create a bipartite
graph $H$, with parts $L$ (left) and $R$ (right), as follows. We first add a
copy of each $V_{i}$, $i\in[\kappa]$, to $L$ and another copy to $R$. We use
$L_{V_{i}}=\\{u^{i}_{1},\ldots,u^{i}_{n}\\}$ and
$R_{V_{i}}=\\{v^{i}_{1},\ldots,v^{i}_{n}\\}$ to denote these two sets,
respectively. We let $E_{i,j}$, $i<j$, denote the edges of $G$ connecting
vertices in $V_{i}$ and $V_{j}$. Now, for each edge $e\in E_{i,j}$, we add a
vertex $v_{e}$ in $L_{E_{i,j}}$, where $L_{E_{i,j}}\subset L$. Finally, we add
${\kappa\choose 2}+1$ vertices to $L$ and ${\kappa\choose 2}+1$ vertices to
$R$, which we denote by $L_{K}=\\{y_{1},\ldots,y_{{\kappa\choose 2}+1}\\}$ and
$R_{K}=\\{z_{1},\ldots,z_{{\kappa\choose 2}+1}\\}$, respectively. We proceed
by describing the edges of $H$. We add all the edges
$\\{u^{i}_{j},v^{i}_{j}\\}$, $i\in[\kappa]$ and $j\in[n]$, so that the graph
induced by $L_{V_{i}}\cup R_{V_{i}}$ is a matching. We add edges between every
vertex in $L_{K}$ and every vertex in $R_{K}$ such that the graph induced by
$L_{K}\cup R_{K}$ is a biclique $K_{{\kappa\choose 2}+1,{\kappa\choose 2}+1}$.
For every vertex $v_{e}\in L_{E_{i,j}}$, where $e=\\{v^{i}_{p},v^{j}_{q}\\}$,
we add the edges $\\{v_{e},v^{i}_{p}\\}$ and $\\{v_{e},v^{j}_{q}\\}$. We order
the sets $L_{E_{i,j}}$ arbitrarily so that we can refer to them as
$L_{E_{1}}$, $L_{E_{2}}$, $\ldots$, $L_{E_{{\kappa\choose 2}}}$. Finally, we
add all the edges between $z_{i}$ and (every vertex in) $L_{E_{i}}$,
$i\in[{\kappa\choose 2}]$. This completes the construction of the bipartite
graph $H$. We let $L_{V}=\bigcup_{i\in[\kappa]}{{L_{V_{i}}}}$,
$R_{V}=\bigcup_{i\in[\kappa]}{{L_{R_{i}}}}$, and
$L_{E}=\bigcup_{i<j}{L_{E_{i,j}}}$.

The corresponding Vertex Cover Reconfiguration instance requires a starting
vertex cover $A$, which we set as $A=L_{V}\cup L_{E}\cup L_{K}$, and a target
vertex cover $B$, which we set as $B=L_{V}\cup L_{E}\cup R_{K}$. Finally, we
require a reconfiguration sequence of at most $\ell=3{\kappa\choose
2}+2\kappa+1$ slides.

Assume that $G$ has a multicolored clique of size $\kappa$ and let
$C=\\{v^{1}_{j_{1}},\ldots,v^{\kappa}_{j_{\kappa}}\\}$ denote the vertices of
that clique. Then, we can reconfigure $A$ to $B$ as follows.

  1. 1.

Slide the token on $u^{1}_{j_{1}}$ to $v^{1}_{j_{1}}$, then the token on
$u^{2}_{j_{2}}$ to $v^{2}_{j_{2}}$, all the way to the token on
$u^{\kappa}_{j_{\kappa}}$ to $v^{\kappa}_{j_{\kappa}}$ ($\kappa$ slides in
total).

  2. 2.

Since $C$ is a multicolored clique, we now have ${\kappa\choose 2}$ tokens,
one in each set $L_{E_{i}}$, $i\in[{\kappa\choose 2}]$, whose neighborhood in
$R$ is full of tokens. So we can slide those tokens to the vertices
$\\{z_{1},\ldots,z_{{\kappa\choose 2}}\\}$ (${\kappa\choose 2}$ slides in
total).

  3. 3.

Next, we slide any token from $L_{K}$ to the remaining non-occupied vertex
$z_{{\kappa\choose 2}+1}$ from $R_{K}$ ($1$ slide in total).

  4. 4.

Now, the remaining tokens in $L_{K}$ will slide to $R_{K}$, to
$\\{z_{1},\ldots,z_{{\kappa\choose 2}}\\}$, then to $L_{E}$ to replace the
lost tokens ($2{\kappa\choose 2}$ slides in total).

  5. 5.

Finally, the $\kappa$ tokens in $R_{V}$ will slide back to their corresponding
vertex in $L_{V}$ ($\kappa$ slides in total).

For the reverse direction, assume that we have a sequence of at most $\ell$
slides transforming vertex cover $A$ to vertex cover $B$. We can assume,
without loss of generality, that the tokens in $L_{V}\cup R_{V}$ will each
remain on their corresponding matching edge; otherwise, if some token from
outside the matching slides to a matching edge so that the matching token
slides away, we can simply switch the roles of both tokens and obtain an
equivalent sequence. In other words, we can assume that every vertex cover in
a reconfiguration sequence will have at least $\kappa n$ tokens in $L_{V}\cup
R_{V}$ (each token never leaving its edge). Now, since $H[L_{K}\cup R_{K}]$ is
a $K_{{\kappa\choose 2}+1,{\kappa\choose 2}+1}$ biclique, we know that any
reconfiguration sequence from $A$ to $B$ must contain some vertex cover $S$
such that $S\cap(L_{K}\cup R_{K})=2{\kappa\choose 2}+1$, with $S\cap
L_{K}={\kappa\choose 2}+1$ and $S\cap R_{K}={\kappa\choose 2}$. From our
previous observation, these additional ${\kappa\choose 2}$ tokens must come
from $L_{E}$. Hence, for any sequence of slides transforming $A$ to $B$, at
least $3{\kappa\choose 2}+1$ slides are required for tokens not in $L_{V}\cup
R_{V}$; at least ${\kappa\choose 2}$ slides from $A$ to $S$ and at least
$2{\kappa\choose 2}+1$ slides from $S$ to $B$. Given that
$\ell=3{\kappa\choose 2}+2\kappa+1$, we know that at most $\kappa$ tokens can
slide to $R_{V}$ (as each token will have to slide back). However, given that
$S$ must exist, sliding less than $\kappa$ tokens to $R_{V}$ is impossible
since we can never free ${\kappa\choose 2}$ tokens in $L_{E}$; the
neighborhood of any ${\kappa\choose 2}$ vertices in $L_{E}$ has size at least
$\kappa$. Therefore, to free ${\kappa\choose 2}$ tokens in $L_{E}$ by sliding
$\kappa$ tokens to $R_{V}$, the corresponding vertices (and edges) must form a
multicolored clique in $G$, which completes the proof. ∎

######  Theorem 31.

If we forbid multiple tokens to occupy the same vertex then the Vertex Cover
Reconfiguration problem parameterized by $\ell$, the length of a
reconfiguration sequence, is W[1]-hard in the token sliding, even when
restricted to bipartite graphs.

###### Proof.

We give a reduction from the Multicolored Biclique problem. An instance of the
Multicolored Biclique problem consists of a bipartite graph $G=(X\cup Y,E)$
and a parameter $\kappa$, where $X$ and $Y$ are partitioned into $\kappa$ sets
(each of size $n$), i.e., $X=X_{1}\cup\ldots X_{\kappa}$, and
$Y=Y_{1}\cup\ldots\cup Y_{\kappa}$. We assume, without loss of generality,
that each vertex in $X_{i}$ ($Y_{i}$), $i\in[\kappa]$, has at least two
neighbors and at least two non-neighbors in each set of $Y_{j}$ ($X_{j}$),
$j\in[\kappa]$. The goal is to decide if $G$ contains a subgraph isomorphic to
the biclique $K_{\kappa,\kappa}$ containing exactly one vertex from each
$X_{i}$ and exactly one vertex from each $Y_{i}$, $i\in[\kappa]$. We call such
a biclique a multicolored biclique.

Given an instance $(G=(X\cup Y,E),\kappa)$ of Multicolored Biclique, we create
a bipartite graph $H$, with parts $L$ (left) and $R$ (right), as follows. We
first add a copy of each $X_{i}$, $i\in[\kappa]$, to $L$ which we denote by
$L_{X_{i}}=\\{x^{i}_{1},\ldots,x^{i}_{n}\\}$. Similarly, we add a copy of each
$Y_{i}$, $i\in[\kappa]$, to $R$ which we denote by
$R_{Y_{i}}=\\{y^{i}_{1},\ldots,y^{i}_{n}\\}$. We use $L_{X}$ and $R_{Y}$ to
denote the union of the sets on each side, respectively. We add $\kappa+1$ new
vertices to $L$ and $\kappa+1$ new vertices to $R$, which we denote by
$L_{K}=\\{u_{1},\ldots,u_{\kappa+1}\\}$ and
$R_{K}=\\{v_{1},\ldots,v_{\kappa+1}\\}$, respectively. Finally, we add
$\kappa+1$ new vertices to $L$ and $\kappa+1$ new vertices to $R$, which we
denote by $L_{Q}=\\{w_{1},\ldots,w_{\kappa+1}\\}$ and
$R_{Q}=\\{z_{1},\ldots,z_{\kappa+1}\\}$, respectively. We proceed by
describing the edges of $H$. We add a copy of each non-edge in $G$ between the
corresponding vertices in $L_{X}\cup R_{Y}$, i.e., we add an edge between a
vertex in $L_{X}$ and a vertex in $R_{Y}$ whenever the corresponding vertices
are not adjacent in $G$. We add edges between every vertex in $L_{K}$ and
every vertex in $R_{K}$ as well as between every vertex in $L_{Q}$ and every
vertex in $R_{Q}$ such that the graphs induced by $L_{K}\cup R_{K}$ and
$L_{Q}\cup R_{Q}$ are bicliques $K_{\kappa+1,\kappa+1}$. Finally, we connect
every vertex $u_{i}$ with every vertex in $R_{Y_{i}}$, every vertex $v_{i}$
with every vertex in $L_{X_{i}}$, every vertex $w_{i}$ with every vertex in
$R_{Y_{i}}$, and every vertex $z_{i}$ with every vertex in $L_{X_{i}}$,
$i\in[\kappa]$. This completes the construction of $H$, which is clearly a
bipartite graph.

The corresponding Vertex Cover Reconfiguration instance requires a starting
vertex cover $A$, which we set as $A=L_{X}\cup R_{Y}\cup L_{K}\cup R_{Q}$, and
a target vertex cover $B$, which we set as $B=L_{X}\cup R_{Y}\cup R_{K}\cup
L_{Q}$. Finally, we require a reconfiguration sequence of at most
$\ell=4\kappa+2$ slides.

Assume that $G$ has a multicolored biclique and let
$\\{x^{1}_{i_{1}},\ldots,x^{\kappa}_{i_{\kappa}},y^{1}_{j_{1}},\ldots,y^{\kappa}_{j_{\kappa}}\\}$
denote the vertices of that biclique. Then, we can reconfigure $A$ to $B$ as
follows.

  1. 1.

Slide the token on $x^{1}_{i_{1}}$ to $v_{1}\in R_{K}$, then the token on
$x^{2}_{i_{2}}$ to $v_{2}\in R_{K}$, all the way to the token on
$x^{\kappa}_{i_{\kappa}}$ to $v_{\kappa}\in R_{K}$ ($\kappa$ slides in total).

  2. 2.

Slide the token on $y^{1}_{j_{1}}$ to $w_{1}\in L_{Q}$, then the token on
$y^{2}_{j_{2}}$ to $w_{2}\in L_{Q}$, all the way to the token on
$y^{\kappa}_{j_{\kappa}}$ to $w_{\kappa}\in L_{Q}$ ($\kappa$ slides in total).
Note that this is possible since the vertices
$\\{x^{1}_{i_{1}},\ldots,x^{\kappa}_{i_{\kappa}}\\}$ and the vertices
$\\{y^{1}_{j_{1}},\ldots,y^{\kappa}_{j_{\kappa}}\\}$ are pairwise non-adjacent
in $H$.

  3. 3.

Next, we slide the token on $u_{\kappa+1}\in L_{K}$ to the remaining non-
occupied vertex $v_{\kappa+1}\in R_{K}$ and we slide the token on
$z_{\kappa+1}\in R_{Q}$ to the remaining non-occupied vertex $w_{\kappa+1}\in
L_{Q}$ ($2$ slides in total).

  4. 4.

Now, the remaining tokens in $L_{K}$ will slide to $R_{Y}$ to replace the lost
tokens ($\kappa$ slides in total).

  5. 5.

Finally, the remaining tokens in $R_{Q}$ will slide to $L_{X}$ to replace the
lost tokens ($\kappa$ slides in total).

For the reverse direction, assume that we have a sequence of at most $\ell$
slides transforming vertex cover $A$ to vertex cover $B$. Since $H[L_{K}\cup
R_{K}]$ and $H[L_{Q}\cup R_{Q}]$ are $K_{\kappa+1,\kappa+1}$ bicliques, we
know that any reconfiguration sequence from $A$ to $B$ must contain an
(earliest) vertex cover $S$ followed by som (earliest) vertex cover $T$ ($S$
and $T$ not consecutive but $S$ appears before $T$) such that one of the
following is true:

  1. 1.

Either $S\cap(L_{K}\cup R_{K})=2\kappa+1$, with $S\cap L_{K}=\kappa$ and
$S\cap R_{K}=\kappa+1$, no token will subsequently (after $S$) slide from
$R_{K}$, $T\cap(L_{Q}\cup R_{Q})=2\kappa+1$, with $T\cap L_{Q}=\kappa+1$ and
$T\cap R_{Q}=\kappa$, and no token will subsequently (after $T$) slide from
$L_{Q}$; or

  2. 2.

$S\cap(L_{Q}\cup R_{Q})=2\kappa+1$, with $S\cap L_{Q}=\kappa+1$ and $S\cap
R_{Q}=\kappa$, no token will subsequently (after $S$) slide from $L_{Q}$,
$T\cap(L_{K}\cup R_{K})=2\kappa+1$, with $T\cap L_{K}=\kappa$ and $T\cap
R_{K}=\kappa+1$, and no token will subsequently (after $T$) slide from
$R_{K}$.

We assume, without loss of generality, that $S$ and $T$ are the earliest
vertex covers in the sequence such that $S$ and $T$ satisfy the first
condition (condition (1)). Note that, since we do not allow multiple tokens to
occupy the same vertex, we must have $\kappa$ tokens that slide from $L_{X}$
to $R_{K}$ and $\kappa$ tokens that slide from $R_{Y}$ to $L_{Q}$. Combined
with the fact that $\ell=4\kappa+2$ (and that $2$ slides are required for the
tokens on $u_{\kappa+1}$ and $z_{\kappa+1}$), we know that exactly $\kappa$
tokens will leave $L_{X}$, exactly $\kappa$ tokens will enter $L_{X}$, exactly
$\kappa$ tokens will leave $R_{Y}$, and exactly $\kappa$ tokens will enter
$R_{Y}$.

Let the sequence of slides be chosen (amongst all sequences of at most $\ell$
slides transforming $A$ to $B$) to be a sequence that minimizes the number of
slides transforming $A$ to $S$. We claim that, in this case, $S$ must exclude
at least one vertex from each $L_{X_{i}}$, $i\in[\kappa]$. Assume otherwise.
Then, since $S\cap(L_{K}\cup R_{K})=2\kappa+1$, every token on $v_{i}\in S\cap
R_{K}$ must come from a vertex in $L_{X_{i}}$, $i\in[\kappa]$ (recall that we
do not allow multiple tokens to occupy the same vertex). Hence, in a sequence
that minimizes the number of slides transforming $A$ to $S$, if $S$ includes
all vertices from some $L_{X_{i}}$ then it must be the case that the sequence
contains another vertex cover $S^{\prime}$, prior to $S$, such that
$S^{\prime}$ is the last vertex cover in the sequence that slides some token
to $L_{X_{i}}$ which is different from the token already on $v_{i}$ (the slide
must be from $R_{Y}$ to $L_{X}$). We can assume, without loss of generality,
that the sequence transforming $S^{\prime}$ to $S$ consists only of slides
from $L_{X}$ to $R_{K}$; the only other possible slides are between $R_{Y}$
and $L_{Q}$ which can be safely deleted contradicting our choice of sequence.
Now, consider the sequence that transforms $A$ to $S$ without including the
slide resulting in $S^{\prime}$. It is not hard to see that the sequence
remains valid; $R_{K}\cup R_{Q}$ cover all the edges between $L_{X_{i}}$ and
$R_{K}\cup R_{Q}$ which implies that the slide resulting in $S^{\prime}$
corresponds to a slide from some vertex $y\in R_{Y}$ to some vertex $x\in
L_{X}$ such that all other neighbors of $x$ are in $S^{\prime}$ as well as the
vertex cover preceeding $S^{\prime}$. Therefore, the existence of $S^{\prime}$
implies that the sequence can be made shorter and we get the required
contradiction. Using similar arguments, we can show that $S$ must exclude at
most one vertex from each $L_{X_{i}}$, $i\in[\kappa]$. Consequently, we assume
in what follows that $S$ excludes exactly one vertex from each $L_{X_{i}}$,
$i\in[\kappa]$. We denote those vertices in $L_{X}$ (which are not in $S$) by
$W=\\{x^{1}_{j_{1}},x^{2}_{j_{2}},\ldots,x^{\kappa}_{j_{\kappa}}\\}$.

We now consider the vertex covers $S_{q_{1}}$, $S_{q_{2}}$, $\ldots$,
$S_{q_{\kappa}}$, appearing in the sequence (not necessarly consecutively) but
in order and all succeeding $S$ (by one or more sets) and such that
$S_{q_{i}}$ is the earliest vertex cover (after $S$) resulting from sliding a
token from some vertex $y^{q_{i}}_{j}\in R_{Y_{q_{i}}}$, $q_{i}\in[\kappa]$
and $j\in[n]$, to vertex $w_{q_{i}}\in L_{Q}$. We claim that, for each
$S_{q_{i}}$, we have $S_{q_{i}}\cap W=\emptyset$. Hence, after
$S_{q_{\kappa}}$ we have a set that excludes exactly one vertex from each
$L_{X_{i}}$ and each $R_{Y_{i}}$, $i\in[\kappa]$, and we are done since we
have $2\kappa$ vertices corresponding to a multicolored biclique in $G$.
Consider the first set where the claim is not true and denote this set by
$S_{q^{\prime}}$. That is, we have $S_{q^{\prime}}\cap W\neq\emptyset$. This
implies that some token slides occured from $R_{Y}$ to $W$ (tokens in $R_{K}$
are assumed to be fixed and tokens in $R_{Q}$ cannot yet slide). However, as
previously noted, no more than $\kappa$ tokens can slide out of $R_{Y}$ and
therefore $S_{q^{\prime}}$ cannot exist. ∎