\section{Distance-r dominating set reconfiguration}

\subsection{Polynomial kernel}

The kernelization for the reconfiguration of 
distance-$r$ domination strongly depends on the following
notion of a domination core which was (in different variants)
also used in the earlier kernelization results for distance-$r$
dominating sets~\cite{DawarK09,drange2016kernelization,eickmeyer2016neighborhood}.


\begin{domcore}
Let $G$ be a graph and $k,r\geq 1$. A set $Z\subseteq V(G)$ is a \emph{$(k,r)$-domination core} if every set $D$ of size at most $k$ that $r$-dominates $Z$ also $r$-dominates $G$.
\end{domcore}

Clearly, $V(G)$ is a $(k,r)$-domination core. Hence, 
starting with $Z=V(G)$, using the next lemma, we can 
gradually remove vertices from $Z$ while maintaining the 
invariant that $Z$ is a $(k,r)$-domination core. 
The proof of the lemma is the same as the proof of
Lemma 11 in \cite{DawarK09} and Lemma 4.1 in \cite{siebertz2016polynomial}, we just use the better bounds from \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:uqw}}{Lemma~\ref{thm:uqw}}.

\begin{lemma}\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:findredundantvertex}}{\label{lem:findredundantvertex}}
Let $\mathcal{C}$ be a nowhere dense class of graphs and 
let $k,r\geq 1$. Let $N=N_{2r}$ and $t=t_{2r}$ 
be the functions characterizing $\mathcal{C}$ as uniformly quasi-wide according to \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:uqw}}{Lemma~\ref{thm:uqw}} with parameter $2r$. 
  There is an algorithm
  that, given a graph $G\in\mathcal{C}$, $k\geq 1$ and $Z\subseteq V(G)$ with 
  $\abs{Z}>N\bigl((k+2)(2r+1)^t\bigr)\eqqcolon \ell$ runs in time $\mathcal{O}(t\cdot \ell\cdot |E(G)|)$, and  
  returns a vertex $w\in Z$ such that for 
  any set $X\subseteq V(G)$
  with $\abs{X}\leq k$,
  it holds that $X$ is an $r$-dominating set of $Z$ if, and only if, 
  $X$ is an $r$-dominating set of
    $Z\setminus \{w\}$.
\end{lemma}

We iteratively apply \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:findredundantvertex}}{Lemma~\ref{lem:findredundantvertex}}
for at most $n$ times, until this is no longer possible. This yields the
following lemma. 

\begin{lemma}\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:findcore}}{\label{lem:findcore}}
Let $\mathcal{C}$ be a nowhere dense class of graphs and 
let $k,r\geq 1$. There exists a polynomial~$q_r$ and a
polynomial time algorithm
  that, given a graph $G\in\mathcal{C}$ and $k\geq 1$
either correctly concludes that $G$ cannot be $r$-dominated by a 
set of at most $k$ vertices, or finds a $(k,r)$-domination core $Z\subseteq V(G)$ of $G$ of size at most $q_r(k)$. 
\end{lemma}

As the source dominating set $D_s$ witnesses that $G$
can be $r$-dominated by a set of $k$ vertices, we conclude
the existence of a domination core from the lemma. 

We now define the annotated problem \textsc{Distance-$r$ $Z$-Dominating Set}, $r$-ZDS, as the problem to find on input
$(G,Z,k)$ a set $D$ with $Z\subseteq N_r(D)$. Such a set
is called a \emph{$(Z,r)$-dominator}. By definition, if $Z$ is a $(k,r)$-domination 
core, then every $(Z,r)$-dominator of size 
at most $k$ corresponds to a distance-$r$ dominating set of
$G$. Similarly, if $Z$ is a distance-$r$ domination core, 
then every minimum $(Z,r)$-dominator corresponds to a 
\mbox{distance-$r$} dominating set of $G$. 
We define the reconfiguration variant of the problem, 
$r$-ZDSR, in the obvious way. 


\begin{theorem}\label{thm:reconfig-ds}
Let $\mathcal{C}$ be a nowhere dense class of graphs and let $r\in \mathbb{N}$. 
Let $(G,D_s,D_t,k)$ be an instance of $r$-DSR, where $G\in \mathcal{C}$. 
We can 
compute in polynomial time a subgraph $G'\subseteq G$ with 
$D_s,D_k\subseteq G'$ and $Z\subseteq V(G')$ 
such that $(G,k,D_s,D_t)$ is a positive
instance of $r$-DSR if and only if $((G',Z),k,D_s,D_t)$ is a positive instance
of $r$-ZDSR and $G'$ has order polynomial in $k$. 
\end{theorem}
\begin{proof}
We compute a $(k,r)$-domination core $Z\subseteq V(G)$
of size at most $q_r(k)$ using \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:findcore}}{Lemma~\ref{lem:findcore}}. 
Let $\epsilon>0$ and let $f_{\mathrm{proj}}(r,\epsilon)$ be the 
function from \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:projection-complexity}}{Lemma~\ref{lem:projection-complexity}}. 
According to the lemma there are at most 
$f_{\mathrm{proj}}(r,\epsilon)\cdot |Z|^{1+\epsilon}$ different $r$-projections
to $Z$. We classify the elements of $V(G)\setminus Z$
according to their $r$-projections to $Z$, that is, we define
$u\cong v\Leftrightarrow \rho_r^G[u,Z]=\rho_r^G[v,Z]$.
Now for each projection class $\kappa$ we choose a representative
$v_\kappa$ from that class. 

\smallskip
\begin{claim}
For all $u,v\in V(G)$, $\rho_r^G[u,Z]=\rho_r^G[v,Z]$ implies $N_r^G(u)\cap Z=N_r^G(v)\cap Z$.
\end{claim}
To see this, let $z\in N_r^G(u)\cap Z$ and let $P$ be a shortest path between $u$ and $z$. 
If $P$ is $Z$-avoiding we conclude from $\rho_r^G[u,Z]=\rho_r^G[v,Z]$ that there 
exists also a $Z$-avoiding path $P'$ of the same length as $P$ between $v$ and $z$, 
which implies $z\in N_r^G(v)\cap Z$. Otherwise, let $z'$ be the first vertex of $Z$ on $P$
and let $Q$ be the initial part of $P$ between $u$ and $z'$. Note that $Q$ is a shortest
path between $u$ and $z'$. By the same argument as above, we find a $Z$-avoiding 
path~$Q'$ of the same length as $Q$ between $v$ and $z'$. By replacing $Q$ in $P$ 
by $Q'$ we obtain a path of the same length at $P$ between $v$ and $z$, which again
proves $z\in N_r^G(v)\cap Z$. \hfill$\lrcorner$

\bigskip
We now construct $G'$ such that it contains $D_s, D_t$, the 
set $Z$, all the representatives $v_\kappa$ and furthermore
a small set $T$ of vertices such that $N_r^G(v_\kappa)\cap Z=N_r^{G'}(v_\kappa)\cap Z$. 
The set $T$ is constructed as follows. For each $v\in V(G)$, let $T_v$
be a breadth-first search tree with root~$v$ of depth $r$ which has 
elements of~$Z$ as its leaves. Clearly, $\mathrm{dist}_G(v,z)=\mathrm{dist}_{T_{v}}(v,z)$
for all $z\in N_r(v)\cap Z$. Let $T$ be the set $\bigcup_{\kappa}V(T_{v_\kappa})\cup \bigcup_{v\in D_s\cup D_t}V(T_v)$.
Hence for each $v_\kappa$ we have $N_r^{G'}(v_\kappa)\cap Z=N_r^{G}(v_\kappa)\cap Z$,
which immediately implies the next claim. 

\bigskip 

\begin{claim}
Let $D'$ be a $(Z,r)$-dominator in $G'$ which contains only representative
vertices~$v_\kappa$. Then $D'$ is also a $(Z,r)$-dominator in $G$. 
\end{claim}

\medskip
We will always find $(Z,r)$-dominators of the above form. 

\medskip
\begin{claim}
Let $v\in V(G')$. Then there is $v_\kappa\in G'$ such that 
$N_r^{G'}(v)\cap Z\subseteq N_r^{G'}(v_\kappa)\cap Z$. 
\end{claim}
Let $\kappa$ be the equivalence class of $v$ in $G$. Then 
$N_r^{G'}(v)\cap Z\subseteq N_r^{G'}(v_\kappa)\cap Z$. 
\hfill$\lrcorner$


\bigskip
Conversely, $(Z,r)$-dominators in $G$ can be translated to 
$(Z,r)$-dominators in $G'$. 
\begin{claim}
Let $D$ be a distance-$r$ dominating set in $G$. Then $D'=\{v_\kappa : v\in D\}$ is a 
$(Z,r)$-dominator in $G'$.
\end{claim}
As~$v_\kappa$ is chosen so that 
$\rho_r^G[v,Z]=\rho_r^G[v_\kappa,Z]$, by Claim 1
it holds that $N_r^G(v)\cap Z=N_r^G(v_\kappa)\cap Z$. Hence 
$Z\subseteq N_r^G(D)$ and $N_r^{G'}(v_\kappa)\cap Z=N_r^{G}(v_\kappa)\cap Z$
 implies that also $Z\subseteq N_r^{G'}(D')$. 
\hfill$\lrcorner$

\bigskip

We can now prove that the instance $((G',Z),k,D_s,D_t)$ of $r$-ZDSR is equivalent
to the instance $(G,k,D_s,D_t)$. If $D_1,\ldots, D_n$ is a valid reconfiguration sequence in 
$G$, then according to Claim 4 it is also a valid reconfiguration sequence of 
$(Z,r)$-dominators in $G'$. 

Conversely, Let $D_1',\ldots,D_n'$ be a reconfiguration sequence of 
$(Z,r)$-dominators in $G'$. We first modify $D_i'$ such that it uses only
representative vertices $v_\kappa$, using Claim 3. Now according to 
Claim 2, $D_i'$ is also a $(Z,r)$-dominator in $G$. By definition of 
a $(k,r)$-domination core, $D_i'$ is a distance-$r$ dominating set in $G$. 

It remains to estimate the size of $G'$. According to \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:findcore}}{Lemma~\ref{lem:findcore}}, 
$Z$ has polynomial size at most $q_r(k)$. According to \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:projection-complexity}}{Lemma~\ref{lem:projection-complexity}}
there are at most $f_{\mathrm{proj}}(r,\epsilon)\cdot |Z|^{1+\epsilon}$ projection 
classes, hence we add at most so many vertices $v_\kappa$ to 
$G'$. Furthermore, each spanning tree $T_{v_\kappa}$ has 
order at most $r\cdot |Z|$. Together with the $2k$ spanning
trees we add for $D_s$ and $D_t$, we have
$|V(G')|\leq (f_{\mathrm{proj}}(r,\epsilon)+2k)\cdot q_r(k)^{2+\epsilon}\cdot r$, which 
is polynomial for every fixed value of $r$ and~$\epsilon$.
\end{proof}

The annoying fact that we reduce to an annotated version
of the problem can be dealt with by introducing a simple
gadget to $G'$. The same problem occurred also in the 
kernelization algorithms for \textsc{Distance-$r$ Dominating
Set} on bounded expansion and nowhere dense graph 
classes~\cite{drange2016kernelization, eickmeyer2016neighborhood}. 
We refer to these papers for the (very simple) 
details. 

\bigskip
We can find much smaller domination cores if we make a
further assumption on the dominating set size. The following
definition was first given in~\cite{drange2016kernelization}
and is also the basis for the kernelization of 
\textsc{Distance-$r$ Dominating Set} in~\cite{eickmeyer2016neighborhood}.

\begin{domcore2}
Let $G$ be a graph and $r\geq 1$. A set $Z\subseteq V(G)$ is a \emph{distance-$r$ domination core} 
if every set $D$ of minimum size that $r$-dominates $Z$ also $r$-dominates $G$.
\end{domcore2} 

The little change in the definition makes a large difference for the sizes of 
the respective cores, as the next lemma shows. 

\begin{lemma}[Eickmeyer et al.~\cite{eickmeyer2016neighborhood}]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:core2}}{\label{lem:core2}}
Let $\mathcal{C}$ be a nowhere dense class of graphs. There exists a function $f_{\mathrm{core}}(r,\epsilon)$ and a polynomial-time algorithm that, given a graph $G\in \mathcal{C}$, integer $k\in \mathbb{N}$ and $\epsilon>0$, 
either correctly concludes that $G$ cannot be $r$-dominated by $k$ vertices, or finds a distance-$r$ domination core $Z\subseteq V(G)$ of $G$ of size at most $f_{\mathrm{core}}(r,\epsilon)\cdot k^{1+\epsilon}$.
\end{lemma} 

If we make the assumption that the source and target sets
$D_s$ and $D_t$ are of minimum size, we can work with 
the improved bounds of \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:core2}}{Lemma~\ref{lem:core2}} instead of the 
polynomial bounds of \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:findcore}}{Lemma~\ref{lem:findcore}}. The final obstacle is 
to better control the sizes of the trees $T_{v_\kappa}$ that we 
add to the graph $G'$ in the construction of \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:reconfig-ds}}{Theorem~\ref{thm:reconfig-ds}}. 
For this, we need the following two lemmas. 

\begin{lemma}[Lemma 2.9 of~\cite{drange2016kernelization}, adjusted (see Lemma 8 of~\cite{eickmeyer2016neighborhood})]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:closure}}{\label{lem:closure}}
There exists a function $f_{\cl}(r,\epsilon)$ and a polynomial-time algorithm that, given $G\in \mathcal{C}$, $X\subseteq V(G)$, $r\in \mathbb{N}$, and $\epsilon>0$, computes the {\em{$r$-closure}} of~$X$, denoted $\mathrm{cl}_r(X)$
with the following properties. 
\begin{itemize}
  \item $X\subseteq \mathrm{cl}_r(X)\subseteq V(G)$;
  \item $|\mathrm{cl}_r(X)|\leq f_{\cl}(r,\epsilon)\cdot |X|^{1+\epsilon}$; and
  \item $|M_r^G(u,\mathrm{cl}_r(X))|\leq f_{\cl}(r,\epsilon)\cdot |X|^{\epsilon}$ for each $u\in V(G)\setminus \mathrm{cl}_r(X)$.
\end{itemize}
\end{lemma}

We can now compute a breadth-first search tree with root $v_\kappa$ of depth at most
$r$ which stops whenever it first encounters a vertex of $Z$. This gives us a tree $T_{v_\kappa}$ 
of size at most $f_{\cl}(r,\epsilon)\cdot |Z|^\epsilon\cdot r$. As breadth-first search does not
continue when meeting $Z$, we now have to connect the vertices of $Z$ with minimum length
paths (up to length $r$) to preserve all distances. This is possible as the next lemma shows. 

\begin{lemma}[Lemma 2.11  of~\cite{drange2016kernelization}, adjusted (see Lemma 9 of~\cite{eickmeyer2016neighborhood})]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:pathsclosure}}{\label{lem:pathsclosure}}
There is a function $f_{\mathrm{pth}}(r,\epsilon)$ and a polynomial-time algorithm which on input $G\in \mathcal{C}$, $X\subseteq V(G)$, $r\in \mathbb{N}$, and $\epsilon>0$, 
computes a superset $X'\supseteq X$ of vertices with the following properties:
\begin{itemize}
\item whenever $\mathrm{dist}_G(u,v)\leq r$ for $u,v\in X$, then $\mathrm{dist}_{G[X']}(u,v)=\mathrm{dist}_G(u,v)$; and
\item $|X'|\leq f_{\mathrm{pth}}(r,\epsilon)\cdot |X|^{1+\epsilon}$.
\end{itemize}
\end{lemma}

We can now prove the following theorem. 

\begin{theorem}\label{thm:reconfig-ds2}
Let $\mathcal{C}$ be a nowhere dense class of graphs and let $r\in \mathbb{N}$. 
Let $(G,D_s,D_t,k)$ be an instance of $r$-DSR, where $G\in \mathcal{C}$
and where $D_s$ and $D_t$ are minimum \mbox{distance-$r$} dominating
sets in~$G$. 
There is a function $f_{\ker}(r,\epsilon)$ and a polynomial-time algorithm
which on input $(G,D_s,D_t,k)$ computes a subgraph $G'\subseteq G$ with 
$D_s,D_k\subseteq G'$ and $Z\subseteq V(G')$ 
such that $(G,k,D_s,D_t)$ is a positive
instance of $r$-DSR if and only if $((G',Z),k,D_s,D_t)$ is a positive instance
of $r$-ZDSR and $G'$ has order at most $f_{\ker}(r,\epsilon)\cdot k^{1+\epsilon}$. 
\end{theorem}
\begin{proof}
The proof parallels that of \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:reconfig-ds}}{Theorem~\ref{thm:reconfig-ds}}. We compute a 
distance-$r$ domination core $Z\subseteq V(G)$ using 
\ifthenelse{\boolean{IsArxiv}}{\Cref{lem:core2}}{Lemma~\ref{lem:core2}} with parameter $\epsilon'$ which will 
be determined in the course of the proof instead of \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:findcore}}{Lemma~\ref{lem:findcore}}. Now, using 
\ifthenelse{\boolean{IsArxiv}}{\Cref{lem:closure}}{Lemma~\ref{lem:closure}}, we compute $Z'=\mathrm{cl}_r(Z)$ and using \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:pathsclosure}}{Lemma~\ref{lem:pathsclosure}}
we compute $Z''\supseteq Z'$ such that 
whenever $\mathrm{dist}_G(u,v)\leq r$ for $u,v\in Z'$, then $\mathrm{dist}_{G[Z'']}(u,v)=\mathrm{dist}_G(u,v)$. 
Again, we classify the elements of $V(G)\setminus Z$
according to their $r$-projections to $Z$, that is, we define
$u\cong v\Leftrightarrow \rho_r^G[u,Z]=\rho_r^G[v,Z]$.

We now construct $G'$ such that it contains $D_s, D_t$, the 
set $Z''$, all the representatives $v_\kappa$ and furthermore
a small set $T$ of vertices such that $N_r^G(v_\kappa)\cap Z=N_r^{G'}(v_\kappa)\cap Z$. 
The set $T$ is constructed as follows. For each $v\in V(G)$, let $T_v$
be a breadth-first search tree with root~$v$ of depth $r$ which does not continue
when meeting $Z$ for the first time. The crucial claim is the following. 

\medskip
\begin{claim}
Let $v_\kappa$ be a representative vertex. Then $\mathrm{dist}_G(v_\kappa,z)=\mathrm{dist}_{G'}(v_\kappa,z)$
for all $z\in N_r^G(v_\kappa)\cap Z$.
\end{claim}
Let $z\in N_r^G(v_\kappa)\cap Z$ and let $P$ be a minimum length path between $v_\kappa$ 
and $z$. Let $z'$ be the first vertex on $P$ which belongs to $Z'$. Then we have 
$\mathrm{dist}_G(v_\kappa,z')=\mathrm{dist}_{T_{v_\kappa}}(v_\kappa,z')$. Now by construction 
of $Z''$ we have $\mathrm{dist}_G(z',z)=\mathrm{dist}_{G'}(z',z)$, which implies the claim. \hfill$\lrcorner$

\medskip
The rest of the proof works exactly as the proof of \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:reconfig-ds}}{Theorem~\ref{thm:reconfig-ds}}. Let
us determine a bound on the size of $G'$, which also determines our initial choice of
$\epsilon'$. The set $Z$ has size at most $f_{\mathrm{core}}(r,\epsilon')\cdot k^{1+\epsilon'}$. 
According to \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:projection-complexity}}{Lemma~\ref{lem:projection-complexity}}
there are at most $f_{\mathrm{proj}}(r,\epsilon')\cdot |Z|^{1+\epsilon'}$ projection 
classes, hence we add at most so many vertices $v_\kappa$ to 
$G'$. The set $Z'$ has size at most $f_{\mathrm{proj}}(r,\epsilon')\cdot |Z|^{1+\epsilon'}$
according to \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:closure}}{Lemma~\ref{lem:closure}} and the set $Z''$ has size at most 
$f_{\mathrm{pth}}(r,\epsilon')\cdot |Z'|^{1+\epsilon}$ according to 
\ifthenelse{\boolean{IsArxiv}}{\Cref{lem:pathsclosure}}{Lemma~\ref{lem:pathsclosure}}. Now, each tree $T_v$ has order 
at most $|Z'|^{\epsilon'}\cdot r$. Hence in total we have
\begin{align*}
V(G')| & \leq |Z''|+(f_{\mathrm{proj}}(r,\epsilon')\cdot |Z|^{1+\epsilon'}+2)\cdot |Z'|^{\epsilon'}\cdot r\\
& \eqqcolon f_{\ker}(r,\epsilon)\cdot k^{1+\epsilon} \text{ for an appropriately chosen function $f_{\mathrm{ker}}$ and $\epsilon'$.}
\end{align*}
\end{proof}

\subsection{Lower bounds}

\begin{theorem}
Let $\mathcal{C}$ be somewhere dense and closed under taking
subgraphs. Then there is $r\in \mathbb{N}$ such that 
the distance-$r$ dominating set 
reconfiguration problem is $\mathsf{W}[1]$-hard on 
$\mathcal{C}$. 
\end{theorem}
\begin{proof}
The proof works in principle as the proof of \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:isw1}}{Theorem~\ref{thm:isw1}}. 
Again, let $s\in \mathbb{N}$ be the number such that according to 
\ifthenelse{\boolean{IsArxiv}}{\Cref{lem:subdiv}}{Lemma~\ref{lem:subdiv}} for all graphs $G$ we have $G_s\in \mathcal{C}$. 
We reduce $1$-DSR to $(3s)$-DSR on $\mathcal{C}$ by finding an 
appropriate subdivision of a graph in which dominating sets
are translated $1$-to-$1$ to distance-$(3s)$ dominating sets. 
Here we can directly use the 
reduction from set cover to distance-$r$
dominating set from~\cite{drange2016kernelization}, where 
we use the fact that dominating set and set cover are equivalent
problems (just define the set system consisting of the 
neighborhoods of all vertices). 
Now use that the token swapping version of dominating set 
reconfiguration is 
$\mathsf{W}[1]$-hard~\cite{lokshtanov2015reconfiguration}. 
\end{proof}

\section{Distance-r independent set reconfiguration}

\subsection{Polynomial kernel}

Our approach for kernelization of $r$-ISR is similar to that of
Lokshtanov et al.~\cite{lokshtanov2015reconfiguration}. 
We iteratively remove \emph{irrelevant vertices} from 
the input instance, until this is no longer possible, in which case
the resulting instance will be small. 


\begin{irrelevant-vertex}
Let $(G,I_s,I_t,k)$ be an instance of the distance-$r$ independent
set reconfiguration problem. A vertex $v\in V(G)\setminus 
(I_s\cup I_t)$ is called
an \emph{irrelevant vertex} if $(G, k, I_s, I_t)$ is a positive 
instance if and only if $(G-v, k,I_s, I_t)$
is a positive instance.
\end{irrelevant-vertex}

\begin{lemma}\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:irrelevantvertex}}{\label{lem:irrelevantvertex}}
Let $\mathcal{C}$ be a nowhere-dense class of graphs and let 
$r\in \mathbb{N}$. Let $N=N_{2r}:\mathbb{N}\times \mathbb{N}$ be the function 
and $t=t_{2r}\in \mathbb{N}$ be the constant for 
$\mathcal{C}$ describing $\mathcal{C}$ as uniformly quasi-wide (for 
parameter $2r$) as defined in \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:uqw}}{Lemma~\ref{thm:uqw}}. 
Let $(G,k,I_s,I_t)$ for $G\in\mathcal{C}$ be an instance of the
distance-$r$ independent set reconfiguration problem and let $R\coloneqq V(G)\setminus (I_s\cup I_t)$. 
For $u,v\in R$ define $u\cong v$ if $\rho_r^G[u,I_s\cup I_t]=\rho_r^G[v,I_s\cup I_t]$. If there is an equivalence
class $\kappa$ with $|\kappa|>N_{2r}(r+2)^{t}(k+2))$, then $\kappa$ contains an irrelevant vertex.
\end{lemma}
\begin{proof}
Assume there is an equivalence class $\kappa$ with 
$|\kappa|>N((r+2)^t(k+2))$. Using \ifthenelse{\boolean{IsArxiv}}{\Cref{thm:uqw}}{Lemma~\ref{thm:uqw}}, we compute a set
$S\subseteq V(G)$ with $|S|\leq t$ 
and $B\subseteq \kappa$ with $|B|\geq (r+2)^t(k+2)$ which is $2r$-independent in 
$G-S$. Now, for $u,v\in B$, let $u \cong_S v$ if $\rho_r^G[u,S]=\rho_r^G[v,S]$. 
Note that there are at most $(r+2)^t$ distinct projection profiles to $S$, 
as $|S|\leq t$ and $\rho_r^G[u,S]$ is a mapping from $S$ to 
$\{0,1,\ldots, r,\infty\}$. 

Since $|B|\geq (r+2)^t(k+2)$, 
we know that at least one equivalence class 
$\kappa_S$ (of equivalence relation~$\cong_S$) 
contains at least $k+2$ vertices of $S$. Let $v\in \kappa_S$. 
We claim that $v$ is an irrelevant vertex. 
Note that $v$ does not belong to $I_s\cup I_t$. 

Consider a reconfiguration sequence $I_s=I_1,I_2,\ldots, I_t=I_\ell$ from $I_s$ to $I_t$ in $G$ with a minimum number of occurrences 
of $v$. We want to prove that $v$ does not occur at all in the 
sequence, as this proves that $v$ is irrelevant. Towards a 
contradiction assume that $v$ does occur in the sequence
and let $p$, $1<p<\ell$, be the first index at which $v$ appears in $I_p$ (that is, $v\in I_p$ and $v\not\in I_i$ for all 
$i<p$).
Let $q+1, p<q+1\leq \ell$ be the first index after~$p$ at 
which~$v$ is 
removed (that is, $v\in I_q$ and $v\not\in I_{q+1}$). 
We will modify the sub-sequence $I_p,\ldots, I_q$ such that it does not use $v$, contradicting our choice of a reconfiguration 
sequence with a minimum number of occurrences of $v$. 

Enumerate the vertices of $\kappa_S\setminus \{v\}$
as $w_1,w_2,\ldots, w_{k+1},\ldots$.
Fix some $j$, $p\leq j\leq q$, and let $I=I_j\setminus\{v\}$. 
Assume there is $z\in I$ with $\mathrm{dist}_{G-S}(w_i,z)\leq r$. 
We claim that in this case $\mathrm{dist}_G(w_\ell,z)>r$ for all
$\ell\neq j$. Because $B$ is $2r$-independent in $G-S$
and $\mathrm{dist}_{G-S}(w_i,z)\leq r$ 
we have $\mathrm{dist}_{G-S}(w_\ell,z)>r$ for $\ell\neq j$. Hence, if 
$\mathrm{dist}_G(w_\ell,z)\leq r$, then there are $s_1,s_2\in S$ 
(possibly $s_1=s_2$) such 
that $\mathrm{dist}_{G-(S\setminus \{s_1\})}(z,s_1)+\mathrm{dist}_G(s_1,s_2)+
\mathrm{dist}_{G-(S\setminus \{s_2\})}(s_2,w_\ell)\leq r.$ However, as 
$\rho_r^G[v,S]=\rho_r^G[w_2,S]$
we have $\mathrm{dist}_{G-(S\setminus\{s_1\})}(z,s_1)+\mathrm{dist}_G(s_1,s_2)+
\mathrm{dist}_{G-(S\setminus\{s_2\})}(s_2,v)\leq r$, which implies $\mathrm{dist}_G(z,v)\leq r$, 
contradicting that $I_j$ is a distance-$r$ independent set. 
Similarly, there does not exist $z\in I$ with both
$\mathrm{dist}_G(z,w_i)\leq r$ for some $i$ and $\mathrm{dist}_{G-S}(z,w_i)>r$
for all $i$, as again in this case $\mathrm{dist}_G(z,v)\leq r$. 
As the set~$I$ 
contains at most $k-1$ elements we conclude by the pigeon
hole principle that there is 
$w\in \kappa_S\setminus\{v\}$ with $I
\cap N_r(w)=\emptyset$. 

We now modify the sequence $I_p,\ldots, I_q$ as follows. 
For each $j$, $p\leq j\leq q$, choose $w^j\in \kappa_S\setminus
\{v\}$ such that $I_j\setminus\{v\}
\cap N_r(w^j)=\emptyset$ (which exists by our above argument). 
Note that we have $|I_p|=|I_q|=k$, as $v$ was introduced
at $I_p$ and removed at $I_{q+1}$. We replace each 
sub-sequence $I_j, I_{j+1}$, $j=p,p+2,\ldots,q$, by the
sub-sequence $J_j,J_j^1,J_j^2,J_{j+1}$, where
\smallskip
\begin{itemize}
\item $J_j=(I_j\setminus\{v\})\cup\{w^j\}$, 
\item $J_j^1=J_j\setminus \{w^j\}$,
\item $J_j^2=J_j^1\cup \{w^{j+1}\}$,
\item $J_{j+1}=J_j^2\setminus (I_j\setminus I_{j+1})$.
\end{itemize}
\smallskip
By our above argument, each of the intermediate 
configurations is a distance-$r$ independent set. Furthermore,
the transition $I_{p-1}, J_p$ is valid, so is every intermediate
transition and the transition $J_q, I_{q+1}$. This finishes the
proof of the lemma. 
\end{proof}

\begin{theorem}\label{thm:reconfig}
Let $\mathcal{C}$ be a nowhere dense class of graphs and let $r\in \mathbb{N}$. 
Let $(G,k,I_s,I_t)$ be an instance of the distance-$r$ independent
set reconfiguration problem, where $G\in \mathcal{C}$. Then we can 
compute in polynomial time a subgraph $G'\subseteq G$ with 
$I_s,I_k\subseteq G'$ such that $(G,k,I_s,I_t)$ is a positive
instance if and only if $(G',k,I_s,I_t)$ is a positive instance
and $G'$ has order polynomial in $k$. 
\end{theorem}
\begin{proof}
Iteratively apply \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:irrelevantvertex}}{Lemma~\ref{lem:irrelevantvertex}} until this is no 
longer possible. Fix some $\epsilon>0$ and let $f_{\mathrm{proj}}(r,\epsilon)$
be the function from \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:projection-complexity}}{Lemma~\ref{lem:projection-complexity}}. According
to the lemma there are only $f_{\mathrm{proj}}(r,\epsilon)\cdot (k^{1+\epsilon})$ 
projection classes and according to \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:irrelevantvertex}}{Lemma~\ref{lem:irrelevantvertex}}
we can find an irrelevant vertex as long as 
some class contains more than $N((r+2)^t(k+2))$ vertices. We 
hence find a kernel of size $f_{\mathrm{proj}}(\epsilon,r)\cdot N((r+2)^t(k+2))\cdot k^{1+\epsilon})$, 
which is polynomial in $k$ for each fixed value of $r$. 
\end{proof}

It is easy to see that we can carry out the same proof for the 
reconfiguration variant where 
we get as input two integer parameters $k,k'$ and we replace the 
fourth condition by $k\leq |I_j|\leq k'$ for all $1\leq j\leq \ell$. The kernel
will have size polynomial in $k'$. 

\subsection{Lower bounds}

Recall that for a graph $G$ and 
$r\in\mathbb{N}$, $G_r$ denotes the $r$-subdivision of $G$. 

\begin{lemma}[Ne\v{s}et\v{r}il and Ossona de Mendez~\cite{nevsetvril2011nowhere}, see also
\cite{drange2016kernelization}]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:subdiv}}{\label{lem:subdiv}}
Let $\mathcal{C}$ be somewhere dense and closed under taking
subgraphs. Then there is $r\in \mathbb{N}$ such that for all graphs $G$
we have $G_r\in\mathcal{C}$. 
\end{lemma}

\begin{lemma}[Ito et al.~\cite{ito2014parameterized}]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:is-whard}}{\label{lem:is-whard}}
The token jumping variant of \textsc{Distance-$1$ Independent Set Reconfiguration} is 
$\mathsf{W}[1]$-hard. 
\end{lemma}

\begin{theorem}\label{thm:isw1}
Let $\mathcal{C}$ be somewhere dense and closed under taking
subgraphs. Then there is $r\in \mathbb{N}$ such that 
\textsc{Distance-$r$ Independent Set 
Reconfiguration} is $\mathsf{W}[1]$-hard on 
$\mathcal{C}$. 
\end{theorem}
\begin{proof}
According to \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:subdiv}}{Lemma~\ref{lem:subdiv}}, there is $s\in \mathbb{N}$ such that
for all graphs $G$ we have $G_s\in \mathcal{C}$. We reduce 
$1$-ISR to $(4s-1)$-ISR on $\mathcal{C}$ by establishing the following. 
For each graph $G$ there exists a polynomial time computable graph 
$H\in\mathcal{C}$ such that $V(G)\subseteq V(H)$ and such that
\begin{enumerate}
\item every independent set $I$ in $G$ is a $(4s-1)$-independent
set in $H$ and 
\item every $(4s-1)$-independent set $I$ of size at least $2$ in 
$H$ consists only of vertices which are also vertices of $G$ and
$I$ is an independent set in $G$. 
\end{enumerate}

Note that we may assume that the parameter $k$ is always at least
$2$. The above properties guarantee that every reconfiguration 
sequence $I_1,\ldots, I_\ell$ of independent sets in $G$
corresponds uniquely to a reconfiguration sequence of distance-$(4s-1)$
independent sets in $H$ and vice versa. Hence, we can conclude 
the statement of the theorem for $r=4s-1$ by
applying \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:is-whard}}{Lemma~\ref{lem:is-whard}}. Note that the reduction also establishes
$\mathsf{W}[1]$-hardness of \textsc{Distance-$r$ Independent Set}
on somewhere dense graph classes which are closed under taking 
subgraphs.

Let $G$ be a graph with vertex set $\{v_1,\ldots,v_n\}$ and
edge set $\{e_1,\ldots,e_m\}$. We remark that the hardness result
 of \ifthenelse{\boolean{IsArxiv}}{\Cref{lem:is-whard}}{Lemma~\ref{lem:is-whard}} works also if we assume that all input graphs do not
 have isolated vertices, so we may assume that $G$ does not contain isolated vertices. We define the new graph
$J$ with vertex set \[\{v_1,\ldots,v_n,e_1,\ldots, e_m, w\}\] 
and edge set \[\{ve:v\in V(G), e\in E(G), v\in e\}\cup \{ew :e\in E(G)\}.\] 
We claim that $H=J_s$ satisfies the above claimed properties. 

Let $I$ be a distance-$1$ independent set in $G$. By construction
of $J$, if $u,v\in V(G)$ are adjacent in $G$, then they have 
distance $2s$ in $J_s$, otherwise they have distance $4s$ in 
$J_s$ (via the vertex~$w$). Hence, $I$ is a distance-$(4s-1)$
independent set in $J_s$. 

Conversely, let $I$ be a distance-$(4s-1)$ independent set
in $J_s$ of size at least $2$. First observe that $I$ consists
only of vertices which are also vertices of $G$. All other
vertices have mutual distance at most $4s-1$ via the vertex $w$. 
As seen above, the elements of $I$ have distance $4s$ in~$J_s$
and therefore distance at least $2$ in $H$, that is, $I$ is
an independent set in~$H$. This finishes the proof. 
\end{proof}



\section{Preliminaries}

\begin{graphs}
All graphs in this paper 
are finite, undirected and simple.
Our notation is standard, we 
refer to the textbook~\cite{diestel2012graph} for 
more background on graphs.  We write $V(G)$
for the vertex set of a graph $G$ and $E(G)$ for its
edge set. For a positive integer $r$, a graph $G$ and
$v\in V(G)$ we write $N_r(v)$ for the set of vertices
of $G$ at distance at most~$r$ from~$v$. The 
radius of a graph $G$ is the minimum integer $r$ such that
there is a vertex $v\in V(G)$ with $N_r(v)=V(G)$. 
\end{graphs}

\begin{ind}
Let $G$ be a graph and $r\in \mathbb{N}$. 
A set $B\subseteq V(G)$ is called {\em{$r$-independent}} in~$G$ if for all
distinct $u,v\in B$ we have $\mathrm{dist}_G(u,v)>r$. The set $B$ 
is a \emph{distance-$r$ dominating set} in $G$ if 
$N_r(B)=\bigcup_{v\in B}N_r(v)=V(G)$. 
\end{ind}

\begin{minors}
Let $G$ be a graph and let $r\in \mathbb{N}$. 
A graph~$H$ with vertex set
$\{v_1,\ldots, v_n\}$ is a \emph{depth-$r$ minor} of~$G$, written
$H\preccurlyeq_r G$, if there are connected and pairwise vertex disjoint
subgraphs $H_1,\ldots, H_n\subseteq G$, each of radius at most $r$,
such that if $v_iv_j\in E(H)$, then there are $w_i\in V(H_i)$ and
$w_j\in V(H_j)$ with $w_iw_j\in E(G)$.

An \emph{$r$-subdivision} of $H$ is obtained by replacing edges of $H$
by internally vertex disjoint paths of length (exactly) $r$.  We write 
$H_r$ for the $r$-subdivision of $H$. 
\end{minors}


\begin{nd}
  A class $\mathcal{C}$ of graphs is \emph{nowhere dense} if there exists a
  function $t\colon \mathbb{N}\rightarrow \mathbb{N}$ such that $K_{t(r)}\not\preccurlyeq_r G$ 
  for all $r\in\mathbb{N}$ and for all $G\in \mathcal{C}$. Otherwise, 
  $\mathcal{C}$ is called \emph{somewhere dense}.
\end{nd}

We will work mainly with the following equivalent characterization
of nowhere dense graph classes. 

\begin{qw}
  A class $\mathcal{C}$ of graphs is called \emph{uniformly quasi-wide} if there are
  functions $N\colon \mathbb{N}\times\mathbb{N}\rightarrow \mathbb{N}$ and $s:\mathbb{N}\rightarrow \mathbb{N}$ such
  that for all $r,m\in \mathbb{N}$ and all subsets $A\subseteq V(G)$ for
  $G\in \mathcal{C}$ of size $\abs{A}\geq N(r,m)$ there is a set
  $S\subseteq V(G)$ of size $\abs{S}\leq s(r)$ and a set
  $B\subseteq A\setminus S$ of size $\abs{B}\geq m$ which is $r$-independent in
  $G-S$.  The functions $N$ and $s$ are called the \emph{margins} of
  the class~$\mathcal{C}$.
\end{qw}


It was shown by Ne\v{s}et\v{r}il and Ossona de
Mendez~\cite{nevsetvril2011nowhere} that a class $\mathcal{C}$ of graphs is
nowhere dense if and only if it is uniformly quasi-wide. Quasi-wideness
is a very useful property for distance-$r$ domination, as large $2r$-independent
sets are natural obstructions for small distance-$r$ dominating sets. 
For us it will be important that the function~$N$ can be assumed 
to be polynomial in~$m$ (the degree of the polynomial may depend on~$r$) and that the sets~$B$ and~$S$ can be efficiently
computed. Polynomial bounds were first obtainend 
by Kreutzer et al.~\cite{siebertz2016polynomial}, we refer 
to the improved bounds of Pilipczuk et al.~\cite{pilipczuk2017wideness}.

\pagebreak
\begin{lemma}[Pilipczuk et al.~\cite{pilipczuk2017wideness}]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]}{\label{thm:uqw}}
Let $\mathcal{C}$ be a nowhere dense class of graphs. 
For all $r\in \mathbb{N}$ there is a polynomial  $N_r\colon \mathbb{N}\to \mathbb{N}$ 
and a constant $t_r\in \mathbb{N}$, such that the following holds
Let $G\in \mathcal{C}$ and
let $A\subseteq V(G)$ be a vertex subset of size at least $N_r(m)$, for a given $m$.
Then there exists a set $S\subseteq V(G)$ of size $|S|\leq t$ and a set $B\subseteq A\setminus S$ 
of size $|B|\geq m$ which is $r$-independent in $G-S$.
Moreover, given~$G$ and $A$, such sets $S$ and $B$ can be computed in time $\mathcal{O}(|A|\cdot |E(G)|)$. 
\end{lemma}

We remark that the $\mathcal{O}$-notation in the above lemma 
hides constant factors depending on~$r$ (which is considered
fixed) and the class $\mathcal{C}$. 

We need a precise description of how vertices interact 
with sets in their $r$-neighborhood.

\begin{av-path}
Let $G$ be a graph and let $A\subseteq V(G)$ be a subset of vertices. For vertices $v\in A$ and $u\in V(G)\setminus A$, a path $P$ connecting $u$ and $v$ is called {\em{$A$-avoiding}}
if all its vertices apart from $v$ do not belong to $A$. 
\end{av-path}

\begin{profile}
Let $G$ be a graph, $A\subseteq V(G)$ and $r\in \mathbb{N}$. The {\em{$r$-projection}} of a vertex $u\in V(G)\setminus A$ onto~$A$, denoted $M^G_r(u,A)$ is the set of all vertices $v\in A$ that
can be connected to $u$ by an $A$-avoiding path of length at most $r$. The {\em{$r$-projection profile}} of a vertex $u\in V(G)\setminus A$ on $A$ is the function $\rho^G_r[u,A]$ mapping vertices of
$A$ to $\{0,1,\ldots,r,\infty\}$, defined as follows: for every $v\in A$, the value $\rho^G_r[u,A](v)$ is the length of a shortest $A$-avoiding path connecting $u$ and~$v$, and~$\infty$ in case this length
is larger than $r$. We define 
\[\widehat{\mu}_r(G,A)=|\{\rho_r^G[u,A]\colon u\in V(G)\setminus A\}|\]
to be the number of different $r$-projection profiles realized on $A$, respectively.
\end{profile}

\begin{lemma}[Eickmeyer et al.~\cite{eickmeyer2016neighborhood}]\ifthenelse{\boolean{IsArxiv}}{\label[lemma]{lem:projection-complexity}}{\label{lem:projection-complexity}}
  Let $\mathcal{C}$ be a nowhere dense class of graphs. Then there is 
  a function $f_{\mathrm{proj}}(r,\epsilon)$ such that for every $r\in \mathbb{N}$, 
  $\epsilon>0$, graph $G\in \mathcal{C}$, and vertex subset $A\subseteq V(G)$, 
  it holds that $\widehat{\mu}_r(G,A)\leq f_{\mathrm{proj}}(r,\epsilon)\cdot |A|^{1+\epsilon}$.
\end{lemma}

\begin{complexity}
A problem is fixed-parameter tractable on a class~$\mathcal{C}$ of
graphs with respect to an input parameter $k$, if there is an
algorithm deciding whether a graph $G\in \mathcal{C}$ admits a solution of
size $k$ in time $f(k)\cdot \abs{V(G)}^c$, for some computable function
$f$ and constant~$c$. A powerful method in parameterized complexity theory is to compute a
problem kernel in a polynomial time pre-computation step, that is, to
reduce the input instance to a sub-instance of size bounded in the
parameter only (independently of the input graph size). Every fixed-parameter
tractable problem has a kernel, however, possibly of exponential or worse size. 
For efficient algorithms it is therefore most desirable to obtain polynomial, 
or optimally even linear, kernels. 

The $\mathsf{W}$-hierarchy is a collection of parameterized complexity classes
$\mathsf{FPT}\subseteq \mathsf{W}[1]\subseteq \mathsf{W}[2]\subseteq \ldots$. 
The assumption $\mathsf{FPT}\subsetneq \mathsf{W}[1]$ can be seen as the 
analogue of the conjecture that $\mathsf{P}\subsetneq \mathsf{NP}$. Therefore, 
showing hardness in the parameterized setting is usually accomplished by establishing
an $\mathit{fpt}$-reduction to a $\mathsf{W}[1]$-hard problem. We refer to 
the textbooks \cite{cygan2015parameterized,downey2013fundamentals,flum2006parameterized} 
for extensive background on parameterized complexity. 
\end{complexity}

\begin{reconfiguration}
We consider the token jumping variants of the 
\textsc{Distance-$r$ Independent Set Reconfiguration} problem ($r$-ISR) and
\textsc{Distance-$r$ Dominating Set Reconfiguration} problem ($r$-DSR) which are formally defined as follows.
\end{reconfiguration}

\begin{center}\normalfont\fbox{%
\begin{tabular}[h]{rp{10cm}}%
\multicolumn{2}{l}{\textsc{Distance-$r$ Independent Set Reconfiguration}}\\%
\textit{Input:} & Graph $G$, positive integer $k$, distance-$r$ independent sets $I_s,I_t\subseteq V(G)$ with $|I_s|=|I_t|=k$, \\%
\textit{Parameter:} & $k$\\%
\textit{Problem:} & Does there exist a sequence $I_1,\ldots, I_\ell$ for some $\ell$ with
\begin{enumerate}
\item $I_1=I_s$ and $I_\ell=I_t$,
\item $I_j$ is a distance-$r$ independent set in $G$ for all $1\leq j\leq \ell$,
\item $|(I_j\setminus I_{j+1})\cup (I_{j+1}\setminus I_j)|\leq 1$ for all $1\leq j\leq \ell-1$, and
\item $k-1\leq |I_j|\leq k$ for all $1\leq j\leq \ell$. 
\end{enumerate}
\end{tabular}}%
\end{center}

The \textsc{Distance-$r$ Dominating Set Reconfiguration} problem is defined analogously, we only demand that in the forth item we 
have $k\leq |D_j|\leq k+1$ for the appearing distance-$r$ dominating
sets $D_j$, $1\leq j\leq \ell$. 
We obtain positive results also for the variants where for $r$-ISR we get as input two integer parameters
$k,k'$ and we replace the 
fourth condition by $k\leq |I_j|\leq k'$ for all $1\leq j\leq \ell$. For $r$-DSR we may
remove the condition on a lower bound completely, that is, in the forth condition 
demand only that $|D_j|\leq k+1$ for all $i\leq j\leq \ell$.




\section{Conclusion}

The study of computationally hard problems on restricted classes
of inputs is a very fruitful line of research in algorithmic graph structure
theory and in particular in parameterized complexity theory. This
research is based on the observation that many problems such as
\textsc{Dominating Set}, which are considered intractable in general,
can be solved efficiently on restricted graph classes. Of course it 
is a very desirable goal in this line of research to identify the most
general classes of graphs on which certain problems 
can be solved efficiently. In this work we were able to identify
the exact limit of tractability for the reconfiguration variants of 
the distance-$r$ independent set problem and distance-$r$ dominating 
set problem on subgraph closed graph classes. Clearly, the main open
question is to identify the most general graph classes which are not subgraph closed
on which these problems admit efficient solutions. 
\section{Introduction}

In the reconfiguration framework we are not asked to 
find a feasible solution to an optimization problem, 
but rather to transform a source feasible solution $S_s$
into a more desirable feasible target solution $S_t$
such that each intermediate solution is also feasible. 
This framework allows to model real-world dynamic situations 
in which we need to transform one valid system state
into another and it is crucial that the system keeps running
in all intermediate states. 

The reconfiguration question can naturally be formulated
by defining the reconfiguration graph $R_\mathcal{Q}(I)$ of an
instance $I$ of $\mathcal{Q}$. Its vertex set consists of all 
feasible solutions of $\mathcal{Q}$ on instance $I$ and there
is an arc from solution $S_1$ to solution $S_2$ if we
allow the transition from~$S_1$ to $S_2$ by one or more
reconfiguration rules. A reconfiguration sequence 
corresponds to a walk in the reconfiguration graph. 
Most results in the literature are limited to the 
problem of determining the existence of a reconfiguration 
sequence between two given solutions; an even more
difficult problem is to find a (possibly minimum-length) 
reconfiguration sequence of solutions.
Typically there are exponentially many feasible solutions
to an instance $I$, and not surprisingly, 
the above problem has been shown to be 
\textsc{PSpace}-complete for the
reconfiguration variants of many important 
\textsc{NP}-complete problems. 

Reconfiguration problems have received considerable attention
in recent literature. The list of problems that has been studied
includes \textsc{Vertex Coloring}~\cite{bonamy2013recoloring,
bonsma2009finding,bonsma2014complexity,cereceda2008connectedness,
cereceda2011finding,cereceda2009mixing}, \textsc{List Edge-Coloring}~\cite{ito2012reconfiguration}, \textsc{Vertex Cover}~\cite{mouawad2014vertex,mouawad2014reconfiguration}, \textsc{Independent Set}~\cite{bousquet2017token,hearn2005pspace,ito2011complexity,ito2014fixed,
lokshtanov2017complexity}, \textsc{Clique, Set Cover, Integer Programming, Matching, Spanning Tree, Matroid Bases}~\cite{ito2011complexity}, \textsc{Satisfiability}~\cite{gopalan2009connectivity,mouawad2015shortest,schwerdtfeger2013computational}, \textsc{Shortest Path}~\cite{bonsma2013complexity, kaminski2011shortest}, \textsc{Subset Sum}~\cite{ito2011approximability}, \textsc{Dominating Set}~\cite{haas2014k, haddadan2015complexity, mouawad2017parameterized}, \textsc{Odd Cycle Transversal}, \textsc{Feedback Vertex Set}, and \textsc{Hitting Set}~\cite{mouawad2017parameterized}. We refer to the excellent 
survey by Van den Heuvel~\cite{van2013complexity} for a
detailed overview.

Recently, a systematic study of the parameterized complexity of reconfiguration problems
was initiated by Mouawad et al.~\cite{mouawad2017parameterized}. 
They study mostly graph theoretical vertex subset problems, 
that is, solutions consist of subsets $S\subseteq V(G)$ of the
input graph $G$. For such problems, one natural parameterization
is the parameter $k$, a bound on the size of feasible solutions, 
another natural parameter is $\ell$, the length of the reconfiguration sequence. Note that
when $k$ is not bounded, the reconfiguration of many such problems, 
e.g.\ of the dominating set problem, becomes easy (first add 
the vertices of $S_s\cup S_t$ one by one to $S_s$ and then 
remove the vertices of $S_t\setminus S_s$ to finally arrive 
at $S_t$). They proved that \textsc{Feedback Vertex Set}
and \textsc{Bounded Hitting Set} (where the cardinality of
each input set is bounded) admit polynomial reconfiguration
kernels (parameterized by~$k$). Concerning lower bounds, 
they proved that reconfiguration of \textsc{Dominating Set} is
$\mathsf{W}[2]$-hard when parameterized by $k+\ell$, as well 
as a general result on reconfiguration of hereditary properties and
their parametric duals, implying $\mathsf{W}[1]$-hardness of
reconfiguration of \textsc{Independent Set, Induced Forest} and
\textsc{Bipartite Subgraph} parameterized by $k+\ell$, and \textsc{Vertex Cover, Feedback Vertex Set,} and \textsc{Odd Cycle Transversal} parameterized by $\ell$. 

\textsc{Independent Set} reconfiguration if the solutions appearing
in the reconfiguration sequence are only allowed to be of size
$k$ and $k-1$ is equivalent to reconfiguration under the token jumping model considered by Ito et al.~\cite{ito2014fixed,ito2014parameterized}. 
In the \emph{token jumping problem} for a vertex subset
problem $\mathcal{Q}$ on graphs we are given a graph $G$ and 
two feasible solutions $S_s, S_t\subseteq V(G)$ of $\mathcal{Q}$
with $|S_s|=|S_t|$, and imagine that a token is placed on 
each vertex of $S_s$. The problem is to determine whether
there exists a sequence $S_1,\ldots,S_n$ of 
feasible solutions, where $S_1=S_s$, $S_n=S_t$ and 
each $S_{i+1}$ results from $S_i$, $1\leq i<n$, 
by moving exactly one
token to another vertex. The token jumping problem for
\textsc{Independent Set} is
known to be \textsc{PSpace}-complete in this setting on graphs of bounded bandwidth~\cite{mouawad2014reconfiguration,wrochna2014reconfiguration} (hence pathwidth and treewidth) 
and W[1]-hard on general graphs~\cite{ito2014parameterized}. 
On the positive side, the problem was shown to be 
fixed-parameter tractable, with parameter $k$, for graphs of 
bounded degree, planar graphs, and graphs excluding $K_{3,d}$ as a 
subgraph, for any constant $d$~\cite{ito2014fixed,ito2014parameterized}. This result was 
extended by Lokshtanov et al.~\cite{lokshtanov2015reconfiguration} 
to graphs of bounded degeneracy and nowhere dense graphs. 
Lokshtanov et al.\ also proved that dominating set reconfiguration (in the token jumping model) is
$\textsf{W}[1]$-hard on general graphs and fixed-parameter tractable, with parameter $k$, for graphs excluding $K_{d,d}$ 
as a subgraph, for any constant $d$ (in particular on all degenerate 
graph classes and nowhere dense graph classes).

Nowhere dense graph classes, which are also the object of
study in the present paper, are very general classes of uniformly
sparse graphs~\cite{nevsetvril2010first,nevsetvril2011nowhere}. 
Many
familiar classes of sparse graphs, like planar
graphs, graphs of bounded treewidth, graphs of bounded degree, and,
in fact, all classes that exclude a fixed (topological) minor, are nowhere
dense. Notably, classes of bounded average degree or bounded
degeneracy are not necessarily nowhere dense. In an algorithmic context this is
reasonable, as every graph can be turned into a graph of
degeneracy at most~$2$ by subdividing every edge once; however, the
structure of the graph is essentially preserved under this operation.
In our context, a particularly interesting algorithmic result states
that every first-order definable property of graphs can be 
decided in almost linear time on nowhere dense graph 
classes~\cite{grohe2014deciding}. This result implies that 
the reconfiguration variants of many of the above mentioned 
vertex subset problems are fixed-parameter tractable with
respect to parameter $k+\ell$ on every nowhere dense
graph class (the existence of a reconfiguration sequence 
can be expressed with $\mathcal{O}(k\cdot \ell)$ quantifiers in 
first-order logic, whenever the property itself can be
defined by a first-order formula), and by the result
of~\cite{grohe2014deciding} be decided in fixed-parameter
time. 

Nowhere dense graph classes play a special role
for \textsc{Dominating Set} and its more general 
variant \textsc{Distance-$r$ Dominating Set}.
A distance-$r$ dominating set in a graph~$G$ 
(for a fixed integer parameter
$r$) is a set $D\subseteq V(G)$ such that 
every vertex of $G$ is at distance at most $r$ 
to a vertex from $D$. 
\textsc{Distance-$r$ Dominating Set} was shown 
to be fixed-parameter tractable on nowhere dense
classes in~\cite{DawarK09} (this result is again implied
by the more general result of~\cite{grohe2014deciding} which 
was obtained later). 
It was then shown that nowhere dense classes are the
limit of tractability based on sparsity methods, more precisely, 
it was shown in~\cite{drange2016kernelization} that 
if a class $\mathcal{C}$ is not nowhere dense and closed under taking
subgraphs, then there is some $r\geq 1$ such that
\textsc{Distance-$r$ Dominating Set} on~$\mathcal{C}$ is
$\mathsf{W}[2]$-hard. It was later shown that the problem
admits a polynomial kernel~\cite{siebertz2016polynomial} 
and in fact an almost linear kernel~\cite{eickmeyer2016neighborhood} on nowhere dense classes. 
A kernelization algorithm, or just a kernel, is a polynomial time
algorithm which transforms every input instance $(G,k)$ to 
an equivalent instance $(G',k')$ such that $|G'|+k'\leq f(k)$
for some function $f$. Hence for a token jumping problem
a kernelization algorithm is a polynomial time algorithm which
transforms every input instance $(G,k,S_s,S_t)$ into an 
instance $(G',k', S_s',S_t')$ with $|G'|+k'\leq f(k)$ for some function $f$ and such that there exists a valid
reconfiguration sequence $S_1=S_s,S_2,\ldots,S_n=S_t$ in $G$
if and only if there exists a valid reconfiguration
sequence $S_1'=S_s',S_2',\ldots, S_m'=S_t'$ in $G'$. 
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 polynomial, or optimally even linear, kernels. 

\subparagraph*{Our results.}

We prove that for every nowhere dense class of graphs 
and for every $r\geq 1$ there exists a polynomial $p_r$ such 
that the token jumping problem for the \mbox{distance-$r$}
independent set problem and for the distance-$r$ dominating
set problem admit kernels of size $p_r(k)$, where~$k$ 
is the number of used tokens. If~$k$ is equal to the size
of a minimum distance-$r$ dominating set, then we even obtain
a kernel of almost linear size $\mathcal{O}(k^{1+\epsilon})$ 
for any fixed $\epsilon>0$. 

Unfortunately, for \textsc{Distance-$r$ Domination Set}
there is a technical subtlety that 
prevents us from reducing the input instance $(G,k,I_s,I_t)$ 
to an equivalent instance $(G',k,I_s,I_t)$ such that $G'$ is a 
subgraph of $G$. Instead, we can kernelize to an 
annotated version of the problem, where only a given subset of vertices of $G'$ needs to be dominated, or we can output
an instance $(G',k,I_s,I_t)$, where $G'$ does not belong
to the class~$\mathcal{C}$ under consideration 
(it's density parameters are only slightly
larger than those of $G$ though). Formally, in any case, 
we do not reduce
to the same problem, hence we compute only a so-called 
\emph{bi-kernel} for the problem. 
Our results generalize the
earlier mentioned results of Lokshtanov et al.~\cite{lokshtanov2015reconfiguration}, 
who proved that 
\textsc{Independent Set} reconfiguration (i.e.\ the case $r=1$) 
is fixed-parameter tractable
on every nowhere dense graph class and \textsc{Dominating Set} 
(i.e.\ the case $r=1$) 
is fixed-parameter tractable if the input graph does not contain large 
complete bipartite graphs (as a subgraph), 
in particular on all nowhere dense graph classes.

Our methods for \textsc{Distance-$r$ Independent Set} generalize
those of Lokshtanov et al.~\cite{lokshtanov2015reconfiguration}
to the more general setting or distance-$r$ independence. They 
are strongly based on the equivalence of nowhere denseness 
and uniform quasi-wideness (a notion that will be defined in the next
section) and polynomial bounds for the quasi-wideness 
functions which were recently obtained by Kreutzer et 
al.~\cite{siebertz2016polynomial} and Pilipczuk et al.~\cite{pilipczuk2017wideness}. 

\pagebreak
Our methods for \textsc{Distance-$r$ Dominating Set} combine
the approach of Lokshtanov et al.~\cite{lokshtanov2015reconfiguration} for \textsc{Dominating Set}
with new methods developed for the kernelization of \textsc{Distance-$r$ Dominating Set} on nowhere dense graph
classes by Eickmeyer et al.~\cite{eickmeyer2016neighborhood}. 

We then prove that if a class~$\mathcal{C}$ is somewhere dense and 
closed under taking subgraphs, then for some value of $r\geq 1$ the reconfiguration variants for these problems on $\mathcal{C}$ is $\mathsf{W}[1]$-hard (and in particular we cannot expect the
existence of kernelization algorithms). 
Hence our results show that the limit of tractability for
the reconfiguration variants of 
\textsc{Distance-$r$ Independent Set} and \textsc{Distance-$r$ Dominating Set} on subgraph closed graph classes lies exactly 
on the boundary
between nowhere denseness and somewhere denseness.

Our hardness results are rather straight forward generalizations of the
$\mathsf{W}[1]$-hardness proofs known for 
\textsc{Independent Set} and \textsc{Dominating Set} to 
their distance-$r$ variants. 
