---
abstract: 'Computing a (shortest) path between two vertices in a graph is one of the most fundamental primitive in graph algorithmics.  In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set remains static but the edge set may change over time, gained more and more attention.  In a nutshell, temporal paths have to respect time, that is, they may only move forward in time.  More formally, the time edges used by a temporal path either need to have increasing or non-decreasing time stamps.  In is well known that computing temporal paths is polynomial-time solvable.  We study a natural variant, where temporal paths may only dwell a certain given amount of time steps in any vertex, which we call *restless temporal paths*.  This small modification creates a significant change in the computational complexity of the task of finding temporal paths.  We show that finding restless temporal paths is -complete and give a thorough analysis of the (parameterized) computational complexity of this problem.  In particular, we show that problem remains computationally hard on temporal graphs with three layers and is -hard when parameterized by the feedback vertex number of the underlying graph.  On the positive side, we give an efficient (FPT) algorithm to find *short* restless temporal paths that has an asymptotically optimal running time assuming the Exponential Time Hypothesis.' 
author:
- Arnaud Casteigts
- 'Anne-Sophie Himmel[^1]'
- 'Hendrik Molter[^2]'
- Philipp Zschoche
bibliography:
- 'literature.bib'
- 'diss.bib'
title: The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
---

Introduction
============

Checking connectivity and computing shortest paths between vertices in a graph is one of the most important tasks in graph algorithmics, both as a direct problem setting and as a subroutine for numerous other applications.  On static graphs, this problem has been studied for decades. 

The study of paths and connectivity in *temporal graphs*, that is, graphs where the vertex set remains static but the edge set may change over time, gained more and more attention in the recent years.  Intuitively, a temporal path (sometimes also called “journey”) is a path through a temporal graph that “respects” time, that is, the time edges it uses have increasing or non-decreasing time stamps.  Even with this informal description we can already see that temporal paths have some properties that usual paths in static (undirected) graphs to not have. 

-   Temporal paths are “directed” even in *undirected* temporal graphs: Since the time stamps of the time edges used by the path have to increase (or may not decrease), it is not necessarily possible to traverse a temporal path in the opposite direction.  This implies that the relation of “being connected” between vertices is not symmetric in a temporal graph. 

-   Temporal paths cannot necessarily be “composed”: If there is a temporal path from a vertex $v$ to a vertex $w$ and a temporal path from vertex $w$ to a vertex $u$, there is not necessarily a temporal path from $v$ to $u$, since the path from $w$ to $u$ might be “too early”.  This implies that the relation of “being connected” between vertices is not transitive in a temporal graph. 

This puts some challenges on designing algorithms to check connectivity that are not present in the static setting.  We are in a somewhat similar situation when we want to compute “shortest” temporal paths.  There are several canonical notions of a “shortest” or “optimal” temporal path.  We informally describe the three most important ones in the following. 

-   A *shortest* temporal path is a temporal path between two vertices that uses a minimum number of time edges. 

-   A *fastest* temporal path is a temporal path between two vertices with a minimum difference between the time stamps of the first and last time edge used by the path. 

-   A *foremost* temporal path is a temporal path between two vertices with a minimum time stamp on its last time edge. 

Each one of these optimal temporal paths have some properties that shortest paths in static graphs do not have, in particular, a “subpath” of an optimal path is not necessarily optimal.  Furthermore, we have that also temporal walks, that is, temporal paths that visit the same vertex multiple times, may be optimal (at least in the case of “fastest” and “foremost”).  This makes computing optimal temporal paths, while still being polynomial-time solvable for the above three mentioned optimality criteria, more challenging than computing their static counterpart. 

In this paper, we consider yet another natural type of temporal paths, which we call *restless temporal paths*.  Intuitively, a restless temporal path cannot stay in any vertex longer than some given time period $\Delta$. Consider the following motivating example.  In a disease spreading scenarios it is very natural to model the spreading process with a temporal network, where vertices correspond to individuals and time edges to for example physical contact, where infections can happen [@Hol16].  Many diseases have the property that infected individuals can recover (or die) after some fixed time period and are immune afterwards[^3], the disease travels along restless paths: It has to infect another individual before its current host recovers.  If we assume that a recovered person is immune to the disease afterwards, then the disease cannot infect a host twice.  Hence, it has to travel along a path with bounded waiting times.  This model for temporal paths has not received much attention of late.  It has been considered as a natural variant for temporal paths [@HS12; @PS11], but only recently this model was studied from a computational perspective [@Him+19; @Zsc17; @Him18] where, however, mainly restless temporal walks are considered.  Restless temporal walks, that is, temporal paths with restricted maximum waiting times that may visit vertices multiple times can be found in polynomial time [@Him+19].  In this paper, we focus on restless temporal paths, that is, any vertex can be visited at most once.  Surprisingly and in stark contrast to both restless temporal walks and non-restless temporal paths, we show that it is -complete (even in very restricted cases) to decide whether there exist a restless temporal path between two vertices. 

Related Work {#sec:path:related}
------------

To the best of our knowledge, temporal paths and walks were first considered by @GCV91 in the context of information flow over time.  Other early work on temporal paths includes @Ber96, where they were also considered in the context of network flows, and the work of @KKK02, where they were considered in the context of connectivity and separation problems. 

More systematic work with a focus on computing (optimal) temporal paths as an algorithmic primitive (as opposed to a subroutine) was conducted for example by @XFJ03, @Wu+16, and @Him+19.  They give polynomial time algorithms for finding optimal temporal paths for several optimality criteria.  @Cas+15b studied the problem from a distributed computing perspective. 

Maximum waiting times have been considered as a natural variant for temporal paths [@HS12; @PS11], however only recently this model has been studied from an algorithmic standpoint [@Him+19] and only in the context of temporal walks, where in particular, they show that restless temporal walks can be computed in polynomial time.  @Cas+15a studied temporal paths with maximum waiting times in the context of analysing the expressivity of temporal graphs.  In the context of temporal flows, a concent somewhat similar to maximum waiting times, called “vertex buffers”, has been considered by @Akr+19a. 

Further work related to temporal paths and connectivity in temporal graphs includes research on temporal spanners and temporally connected graphs [@AF16; @Akr+17; @CPS19; @MMS19], temporal graph exploration [@BZ19; @FMS13; @ES18; @AMS19; @Akr+19b; @Erl+19; @EHK15], temporal separators [@KKK02; @Ber96; @MMS19; @Flu+19a; @Zsc+19], modifying temporal graphs to increase or decrease connectivity [@Enr+19; @EMS19], and a temporal version of the <span style="font-variant:small-caps;">Traveling Sales Person</span> problem [@MS16]. 

Our Contributions and Organization of the Paper
-----------------------------------------------

To the best of our knowledge, we are the first to establish -completeness of the problem of computing a restless temporal path between two vertices.  We show that the problem is -complete even if the input temporal graph has only three layers.  The reduction we present also implies some running time lower bounds based on the Exponential Time Hypothesis.  We further show that finding restless temporal paths is -hard when parameterized by the feedback vertex number of the underlying graph of the input temporal graph.  On the positive side, we show that finding restless temporal paths of bounded length (that is, number of time edges) is fixed-parameter tractable with respect to the length bound.  We also discuss some implications of this result for structural parameterizations. 

In \[sec:path:prelims\] we formally introduce all necessary concepts related to temporal paths that we need in this work, we formally define our problem setting and report some basic observations about the problem.  In \[sec:path:hardness\] we present our main computational hardness results.  In \[sec:fptalg\] we present our algorithmic results.  We conclude in \[sec:path:conclusion\]. 

Preliminaries {#sec:path:prelims}
=============

In this section, we formally introduce the most important concepts related to temporal graphs, paths, and walks and give the formal problem definition of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}and [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}. 

We start with some basic mathematical definitions.  We refer to an interval as a contiguous ordered set of discrete time steps.  Formally, an *interval* is an ordered set $$I=[a,b]:=\{n \mid n \in {\mathbb{N}}\wedge a \leq n \leq b \},$$where $a,b \in {\mathbb{N}}$. Further, let $[a]:=[1,a]$.

Static Graphs
-------------

We use standard notation from (static) graph theory [@Die16].  Unless stated otherwise, we assume graphs in this thesis to be *undirected* and *simple*.  To clearly distinguish them from temporal graphs, they are sometimes referred to as *static* graphs.  Given a (static) graph $G=(V,E)$ with $E\subseteq \binom{V}{2}$, we denote by $V(G):=V$ and $E(G):=E$ the sets of its vertices and edges, respectively.  We call two vertices $u,v\in V$ *adjacent* if $\{u,v\}\in E$. Two edges $e_1,e_2\in E$ are *adjacent* if $e_1\cap e_2\neq \emptyset$. For some vertex subset $v'\subseteq V$, we denote by $G[V']$ the *induced* subgraph of $G$ on the vertex set $V'$, that is, $G[V']=(V',E')$ where $E' = \{\{v,w\}\mid \{v,w\}\in E\wedge v\in V'\wedge w\in V'\}$.

Temporal Graphs
---------------

Since temporal graph theory and temporal graph algorithmics are still rather young research fields, notation and terminology is not yet completely standardized and in the literature one can find many synonyms for terminology or mathematically equivalent definitions that use different notation [@LVM18; @CF13a; @CF13b; @Hol15; @HS12; @Boc+14; @Mic16; @Cas+12].  In the following we introduce the notation and terminology we use in this paper. 

Temporal graphs are graphs where the edge set may change over a discrete set of time steps.  We model a temporal graph as a vertex set together with an ordered list of edge set over this vertex set. 

An (undirected, simple) *temporal graph* is a tuple ${\ensuremath{\mathcal{G}=(V, E_1, E_2, \ldots, E_{\ensuremath{\ell}})}\xspace}$ (or [$\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})$]{}for short), with $E_i\subseteq\binom{V}{2}$ for all $i\in[{\ensuremath{\ell}}]$.

We call ${\ensuremath{\ell}}({\ensuremath{\mathcal{G}}\xspace}) := {\ensuremath{\ell}}$ the *lifetime* of ${\ensuremath{\mathcal{G}}\xspace}$. As with static graphs, we assume all temporal graphs in this thesis to be undirected and simple. 

We call the graph $G_i({\ensuremath{\mathcal{G}}\xspace}) = (V, E_i({\ensuremath{\mathcal{G}}\xspace}))$ the *[layer]{}* $i$ of ${\ensuremath{\mathcal{G}}\xspace}$ where $E_i({\ensuremath{\mathcal{G}}\xspace}) := E_i$. If $E_i=\emptyset$, then $G_i$ is a *trivial* layer.  We call layers $G_i$ and $G_{i+1}$ *adjacent*.  We call $i$ a *[time step]{}*.  If an edge $e$ appears at time $i$, that is, $e\in E_i$, we say that $e$ has *time stamp* $i$. We further denote $V({\ensuremath{\mathcal{G}}\xspace}):=V$. The *underlying graph* ${\ensuremath{G_\downarrow ({\ensuremath{\mathcal{G}}\xspace})}\xspace}$ of ${\ensuremath{\mathcal{G}}\xspace}$ is defined as ${\ensuremath{G_\downarrow ({\ensuremath{\mathcal{G}}\xspace})}\xspace} := (V, \bigcup_{i=1}^{{\ensuremath{\ell}}({\ensuremath{\mathcal{G}}\xspace})} E_i({\ensuremath{\mathcal{G}}\xspace}))$. To improve readability, we remove $({\ensuremath{\mathcal{G}}\xspace})$ from the introduced notations whenever it is clear from the context. 

For every $v\in V$ and every [time step]{}$t\in [{\ensuremath{\ell}}]$, we denote the *appearance of vertex* $v$ *at time* $t$ by the pair $(v,t)$. For evey $t\in [{\ensuremath{\ell}}]$ and every $e\in E_t$ we call the pair $(e,t)$ a *time edge*.  We assume that the *size* (for example when referring to input sizes in running time analyzes) of ${\ensuremath{\mathcal{G}}\xspace}$ is $|{\ensuremath{\mathcal{G}}\xspace}|:=|V|+\sum_{i=1}^{\ensuremath{\ell}}|E_i|$, that is, we do not assume that we have compact representations of temporal graphs. 

Temporal Walks and Paths {#sec:path:def}
------------------------

Intuitively, a temporal path (sometimes also called “journey”) is a path through a temporal graph that respects time, that is, the time edge is uses have non-decreasing time stamps.  A temporal walk may visit the same vertex multiple times.  Formally, these two concepts are defined as follows. 

\[def:temppath\] A *temporal walk* of length $n$ from vertex $s$ to vertex $z$ in a temporal graph ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ is a sequence $$P =\big( (\{s=v_0,v_1\}, t_1), (\{v_1, v_2\}, t_2), \dots, (\{v_{n-1}, v_n=z\}, t_{n} ) \big)$$ of edges together with time stamps such that for all $i\in[n]$ we have that $\{v_{i-1},v_i\}\in E_i$ and for all $i\in [n-1]$ we have that $t_i \leq t_{i+1}$. Moreover, we call $P$ a *temporal path* of length $n$ if $v_i\neq v_j$ for all $i, j\in \{0,\ldots,n\}$ with $i\neq j$.

Given a temporal path $P=\big( (\{v_0,v_1\}, t_1), (\{v_1, v_2\}, t_2), \dots, (\{v_{n-1}, v_n\}, t_{n} ) \big)$, we denote the set of vertices visited by $P$ by $V(P)=\{v_0,v_1,\ldots,v_n\}$.

Restless Temporal Walks and Paths {#sec:path:defrestless}
---------------------------------

A *restless* temporal path is not allowed to wait an arbitrary amount of time in a vertex, but has to leave any vertex it visits within the next $\Delta$-window, for some given value for $\Delta$. Analogue to the non-restless case, a restless temporal walk may visit a vertex multiple times.  Formally, they are defined as follows. 

\[def:rtemppath\] A *${\ensuremath{\Delta}}$-restless temporal walk* of length $n$ from vertex $s$ to vertex $z$ in a temporal graph ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ is a sequence $P =\big( (\{s=v_0,v_1\}, t_1), (\{v_1, v_2\}, t_2), \dots, (\{v_{n-1}, v_n=z\}, t_{n} ) \big)$ of edges together with time stamps such that for all $i\in[n]$ we have that $\{v_{i-1},v_i\}\in E_i$ and for all $i\in [n-1]$ we have that $t_i \leq t_{i+1} \leq t_i + {\ensuremath{\Delta}}$. Moreover, we call $P$ a *$\Delta$-restless temporal path* of length $n$ if $v_i\neq v_j$ for all $i, j\in \{0,\ldots,n\}$ with $i\neq j$. We say that $P$ *respects* the waiting time ${\ensuremath{\Delta}}$.

Having this definition at hand, we are ready to define the main decision problem of this work. 

We also consider a variant, where we want to find $\Delta$-restless paths of a certain maximum length. 

[<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}is the special case of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}for $k=|V|-1$, since no $\Delta$-restless temporal path in a graph ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ can have length more than $|V|-1$. Furthermore, both [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}and [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}are clearly contained in since, given a temporal path, we can easily verify in polynomial time whether it is $\Delta$-restless. 

Parameterized Complexity
------------------------

We use standard notation and terminology from parameterized complexity theory [@DF13; @FG06; @Nie06; @Cyg+15] and give here a brief overview of the most important concepts that are used in this thesis.  A *parameterized problem* is a language $L\subseteq \Sigma^* \times {\mathbb{N}}$, where $\Sigma$ is a finite alphabet.  We call the second component the *parameter* of the problem.  A parameterized problem is *fixed-parameter tractable* (in the complexity class ) if there is an algorithm that solves each instance $(I, r)$ in $f(r) \cdot |I|^{O(1)}$ time, for some computable function $f$. A decidable parameterized problem $L$ admits a *polynomial kernel* if there is a polynomial-time algorithm that transforms each instance $(I,r)$ into an instance $(I', r')$ such that $(I,r)\in L$ if and only if $(I',r')\in L$ and $|(I', r')|\in r^{O(1)}$. If a parameterized problem is hard for the parameterized complexity class , then it is (presumably) not in .  The complexity classes  is closed under parameterized reductions, which may run in -time and additionally set the new parameter to a value that exclusively depends on the old parameter.  We employ the cross-composition framework by @BJK14 to refute the existence of a polynomial kernel for a parameterized problem under the assumption that [$\not\subseteq$ /]{}, the negation of which would cause a collapse of the polynomial-time hierarchy to the third level.  In order to formaly introduce the framework, we need some definitions. 

An equivalence relation $R$ on the instances of some problem $L$ is a *polynomial equivalence relation* if

1.   one can decide for each two instances in time polynomial in their sizes whether they belong to the same equivalence class, and

2.   for each finite set $S$ of instances, $R$ partitions the set into at most $(\max_{x \in S} |x|)^{O(1)}$ equivalence classes. 

Using this, we can now define OR-cross-compositions and AND-cross-compositions. 

An *OR-cross-composition* of a problem $L\subseteq \Sigma^*$ into a parameterized problem $P$ (with respect to a polynomial equivalence relation $R$ on the instances of $L$) is an algorithm that takes $n$ $R$-equivalent instances $x_1,\ldots,x_n$ of $L$ and constructs in time polynomial in $\sum_{i=1}^n |x_i|$ an instance $(x,k)$ of $P$ such that

1.   $k$ is polynomially upper-bounded in $\max_{1\leq i\leq n}|x_i|+\log(n)$ and

2.   $(x,k)$ is a [*yes*]{}-instance of $P$ if and only if there is an $i\in [n]$ such that $x_{i}$ is a [*yes*]{}-instance of $L$.

If an -hard problem $L$ OR-cross-composes into a parameterized problem $P$, then $P$ does not admit a polynomial kernel, unless [$\subseteq$ /]{} [@BJK14]. 

Basic Observations
------------------

It is easy to observe that computational hardness of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}for some fixed value of $\Delta$ implies hardness for all larger values of $\Delta$. This allows us to construct hardness reductions for small fixed values of $\Delta$ and still obtain general hardness results. 

\[obs:path:delta\] For every fixed $\Delta$, the problem [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}on instances $({\ensuremath{\mathcal{G}}\xspace}, s,z,\Delta+1)$ is at least as hard as [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}on instances $({\ensuremath{\mathcal{G}}\xspace}, s,z,\Delta)$.

The result immediately follows from the observation that a temporal graph ${\ensuremath{\mathcal{G}}\xspace}$ contains a $\Delta$-restless [temporal $(s,z)$-path]{} if and only if the temporal graph ${\ensuremath{\mathcal{G}}\xspace}'$ contains a $(\Delta+1)$-restless [temporal $(s,z)$-path]{}, where ${\ensuremath{\mathcal{G}}\xspace}'$ is obtained from ${\ensuremath{\mathcal{G}}\xspace}$ by inserting one trivial layer after every $\Delta$ consecutive layers. 

Furthermore, we can show that [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}does not admit a polynomial kernel when parameterized by the number $|V|$ of vertices. 

\[prop:path:nopk\] [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}parameterized by the number $|V|$ of vertices does not admit a polynomial kernel for all $\Delta\ge 1$ unless [$\subseteq$ /]{}. 

We provide an OR-cross-composition from [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}onto itself.  We define an equivalence relation $R$ as follows: Two instances $({\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace},s,z,\Delta)$ and $({\ensuremath{\mathcal{G}}\xspace}'=(V', (E'_i)_{i\in[{\ensuremath{\ell}}']}),s',z',\Delta')$ are equivalent under $R$ if and only if $|V|=|V'|$ and $\Delta=\Delta'$. Clearly, $R$ is a polynomial equivalence relation. 

Now let $({\ensuremath{\mathcal{G}}\xspace}_1=(V_1, (E_{1,i})_{i\in[{\ensuremath{\ell}}_1]}),s_1,z_1,\Delta_1),\ldots,({\ensuremath{\mathcal{G}}\xspace}_n=(V_n, (E_{n,i})_{i\in[{\ensuremath{\ell}}_n]}),s_n,z_n,\Delta_n)$ be $R$-equivalent instances of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}.  We construct a temporal graph ${\ensuremath{\mathcal{G}}\xspace}^\star=(V^\star, (E^\star_{i})_{i\in[{\ensuremath{\ell}}^\star]})$ as follows.  Let $|V^\star|=|V_1|$ and $s^\star, z^\star\in V^\star$. We identify all vertices $s_i$ with $i\in[n]$ with each other and with $s^\star$, that is, $s^\star=s_1=\ldots=s_n$. Analogously, we identify all vertices $z_i$ with $i\in[n]$ with each other and with $z^\star$, that is, $z^\star=z_1=\ldots=z_n$. We arbitrarily identify the remaining vertices of the instances with the remaining vertices from $V^\star$, that is, let $V^\star\setminus\{s^\star,z^\star\}=V_1\setminus\{s_1,z_1\}=\ldots=V_n\setminus\{s_n,z_n\}$. Now let $E^\star_1=E_{1,1}, E^\star_2=E_{1,2}, \ldots, E^\star_{{\ensuremath{\ell}}_1}=E_{1,{\ensuremath{\ell}}_1}$. Intuitively, the first instance $({\ensuremath{\mathcal{G}}\xspace}_1=(V_1, (E_{1,i})_{i\in[{\ensuremath{\ell}}_1]})$ essentially forms the first ${\ensuremath{\ell}}_1$ layers of ${\ensuremath{\mathcal{G}}\xspace}^\star$. Then we introduce $\Delta_1+1$ trivial layers, that is, $E^\star_{{\ensuremath{\ell}}_1+1}=E^\star_{{\ensuremath{\ell}}_1+2}=\ldots=E^\star_{{\ensuremath{\ell}}_1+\Delta+1}=\emptyset$. Then we continue in the same fashion with the second instance and so on.  We have that ${\ensuremath{\ell}}^\star=\sum_{i\in[n]} {\ensuremath{\ell}}_i + (n-1)\cdot(\Delta_1+1)$. Finally, we set $\Delta^\star=\Delta_1$.

This instance can be constructed in polynomial time and the number of vertices is the same as the vertices of the input instances, hence $|V^\star|$ is polynomially upper-bounded by a maximum size of an input instance.  Furthermore, it is easy to check that ${\ensuremath{\mathcal{G}}\xspace}^\star$ contains a $\Delta^\star$-restless [temporal $(s^\star,z^\star)$-path]{} one if and only if there is an $i\in[n]$ such that ${\ensuremath{\mathcal{G}}\xspace}_i$ contains a $\Delta_i$-restless [temporal $(s_i,z_i)$-path]{}.  This follows from the fact that all instances are separated in time by $\Delta_1+1$ trivial layers, hence no $\Delta^\star$-restless [temporal $(s^\star,z^\star)$-path]{} can use time edges from different original instances.  Since [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}is -hard (\[thm:probRestlessPath:NPh\]) the result follows. 

Optimality Concepts for Temporal Paths {#subs:path:opt}
--------------------------------------

In contrast to the static setting, there are several canonical notions of a “shortest” or “optimal” temporal path.  We informally describe the three most important ones in the following and then give their formal definitions. 

-   A *shortest* temporal path is a temporal path between two vertices that uses a minimum number of time edges. 

-   A *fastest* temporal path is a temporal path between two vertices with a minimum difference between the time stamps of the first and last time edge used by the path. 

-   A *foremost* temporal path is a temporal path between two vertices with a minimum time stamp on its last time edge. 

Formally they are defined as follows. 

Let ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ be a temporal graph with two vertices $s,z\in V$ and let $P =\big( (\{s=v_0,v_1\}, t_1), (\{v_1, v_2\}, t_2), \dots, (\{v_{n-1}, v_n=z\}, t_{n} ) \big)$ be a [temporal $(s,z)$-path]{}.  We call $P$

-   a *shortest* [temporal $(s,z)$-path]{}, if there is no [temporal $(s,z)$-path]{} $$P' =\big( (\{s=v_0,v_1'\}, t_1'), (\{v_1', v_2'\}, t_2'), \dots, (\{v_{n'-1}', v'_{n'}=z\}, t'_{n'} ) \big)$$ with $n'<n$ in ${\ensuremath{\mathcal{G}}\xspace}$,

-   a *fastest* [temporal $(s,z)$-path]{}, if there is no [temporal $(s,z)$-path]{} $$P' =\big( (\{s=v_0,v_1'\}, t_1'), (\{v_1', v_2'\}, t_2'), \dots, (\{v_{n'-1}', v'_{n'}=z\}, t'_{n'} ) \big)$$ with $t'_{n'}-t'_1<t_n-t_1$ in ${\ensuremath{\mathcal{G}}\xspace}$, and

-   a *foremost* [temporal $(s,z)$-path]{}, if there is no [temporal $(s,z)$-path]{} $$P' =\big( (\{s=v_0,v_1'\}, t_1'), (\{v_1', v_2'\}, t_2'), \dots, (\{v_{n'-1}', v'_{n'}=z\}, t'_{n'} ) \big)$$ with $t'_{n'}<t_n$ in ${\ensuremath{\mathcal{G}}\xspace}$.

These concepts transfer to $\Delta$-restless temporal paths in a straight forward way.  For an overview on further optimality concepts for temporal graphs we refer to @Him18 [@Him+19]. 

Strict vs. Non-Strict Temporal Paths
------------------------------------

Here, we want to briefly discuss the concept of *strict* temporal paths and how it differs from the model we use here.  In contrast to a (non-strict) temporal path (see \[def:temppath\]), a the edges used by a strict temporal path need to have strictly increasing time stamps.  Strict restless paths are defined in an analogous way.  In this paper, we focus on non-strict temporal paths.  However, we remark that for some problem setting, the two models can behave quite differently [@Zsc+19].  One obvious difference is that the length of a strict temporal path in a temporal graph in upper-bounded by the lifetime of the temporal graph, which allows for some tractability results for temporal graph with small lifetime, where it is often not clear whether similar results also hold for the non-strict temporal path model [@Zsc+19]. 

Hardness Results for Restless Temporal Paths {#sec:path:hardness}
============================================

In this section we thorougly analyse the computational hardness of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}which of course transfers also to [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}. 

NP-Hardness for few Layers
--------------------------

We start by showing that [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}is -complete even if the lifetime of the input temporal graph is constant. 

\[thm:probRestlessPath:NPh\] [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}is -complete for all ${\ensuremath{\Delta}}\ge 1$ and ${\ensuremath{\ell}}\ge \Delta+2$ even if every edge has only one time stamp. 

We show this result by a reduction from the -complete [<span style="font-variant:small-caps;">Exact $(3,4)$-SAT</span>]{}problem [@Tov84].  The problem [<span style="font-variant:small-caps;">Exact $(3,4)$-SAT</span>]{}asks whether a given formula $\phi$ is satisfiable and is in conjunctive normal form where each clause has exactly three literals and each variable appears in exactly four clauses. 

Let $\phi$ be an instance of [<span style="font-variant:small-caps;">Exact $(3,4)$-SAT</span>]{}with $n$ variables and $m$ clauses.  We construct a temporal graph ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ with ${\ensuremath{\ell}}=3$ (note that to get larger values for ${\ensuremath{\ell}}$, we can simply append trivial layers to the constructed instance) consisting of a series of variable gadgets followed by a dedicated vertex $s_n$ and then a series of clause gadgets.  It is constructed in a way such that for $\Delta=1$, any $\Delta$-restless temporal $(s,z)$-path has to visit a vertex $s_n$ and each possible $\Delta$-restless temporal $(s,s_n)$-path represents exactly one variable assignment for the formula $\phi$. Further we show that for any $\Delta$-restless temporal $(s,s_n)$-path it holds that it can only be extended to a $\Delta$-restless temporal $(s,z)$-path if and only if the $\Delta$-restless temporal $(s,s_n)$-path represents a satisfying assignment for the formula $\phi$.

[*Variable Gadget.*]{}  We start by adding a vertex $s$ to the vertex set $V$ of ${\ensuremath{\mathcal{G}}\xspace}$. For each variable $x_i$ with $i \in [n]$ of $\phi$, we add 9 fresh vertices to $V$: $x_i^{(1)}$, $x_i^{(2)}$, $x_i^{(3)}$, $x_i^{(4)}$, $\bar x_i^{(1)}$, $\bar x_i^{(2)}$, $\bar x_i^{(3)}$, $\bar x_i^{(4)}$, and $s_i$. Each variable $x_i$ is represented by a gadget consisting two disjoint path segments of four vertices each.  One path segment is formed by $x_i^{(1)}$, $x_i^{(2)}$, $x_i^{(3)}$, and $x_i^{(4)}$ in that order and the second path segment is formed by $\bar x_i^{(1)}$, $\bar x_i^{(2)}$, $\bar x_i^{(3)}$, and $\bar x_i^{(4)}$ in that order.  The connecting edges all appear exclusively at time step one, that is, $\{x_i^{(1)}, x_i^{(2)}\}$, $\{x_i^{(2)}, x_i^{(3)}\}$, and $\{x_i^{(3)}, x_i^{(4)}\}$ are added to $E_1$. Analogously for the edges connecting $\bar x_i^{(1)}$, $\bar x_i^{(2)}$, $\bar x_i^{(3)}$, and $\bar x_i^{(4)}$. Intuitively, if a $\Delta$-restless temporal $(s,z)$-path passes the first segment, then this corresponds to setting the variable $x_i$ to .  If it passes the second segment, then the variable is set to .  For all $i \in [n-1]$ we add the edges $\{x_i^{(4)},s_i\}$, $\{\bar x_i^{(4)},s_i\}$, $\{s_i,\bar x_{i+1}^{(1)}\}$, and $\{s_i,\bar x_{i+1}^{(1)}\}$ to $E_1$ and, additionally, we add $\{s,x_{1}^{(1)}\}$, $\{s,\bar x_{1}^{(1)}\}$, $\{x_{n}^{(4)},s_n\}$, and $\{\bar x_{n}^{(4)},s_n\}$ to $E_1$. We can observe that there are exactly $2^n$ different temporal $(s,s_n)$-paths at time step one.  Intuitively, each path represents exactly one variable assignment for the formula $\phi$. [*Clause Gadget.*]{}  We add a vertex $z$ to $V$. For each clause $c_j$ with $j \in [m]$ we add a fresh vertex $c_j$ to $V$. We further add a vertex $s'$ to $V$ and add the edge $\{s_n,s'\}$ to $E_2$. Let $x_i$ (or $\bar x_i$) be a literal that appears in clause $c_j$ and let this be the $k$th appearance of variable $x_i$ in $\phi$. Then, we add the edges $\{c_j, x_i^{(k)}\}, \{x_i^{(k)},c_{j+1}\}$ (or $\{c_j, \bar x_i^{(k)}\}, \{\bar x_i^{(k)},c_{j+1}\}$) to $E_3$ (where $c_{m+1} = z$).  Finally, we add the edge $\{s',c_1\}$ to $E_3$. Hence, there are exactly $3^m$ different temporal $(s',z)$-paths at time step three.  Each path must visit the clause vertices $c_1,\ldots,c_m$ in the given order by construction. 

Finally, we set ${\ensuremath{\Delta}}=1$. This finishes the construction, for a visualization see \[fig:pathred1\].  It is easy to check that every edge in the constructed temporal graph has only one time step and that the temporal graph can be computed in polynomial time. 

(Sl) at (-3,1) [$s$]{}; (X1l) at (3,-1) [$x_1$]{}; (X2l) at (13,-1) [$x_2$]{}; (X3l) at (23,-1) [$x_3$]{}; (S) at (-2,1) ; (A1) at (0,0) ; (A2) at (2,0) ; (A3) at (4,0) ; (A4) at (6,0) ; (A5) at (0,2) ; (A6) at (2,2) ; (A7) at (4,2) ; (A8) at (6,2) ; (S2) at (8,1) ; (B1) at (10,0) ; (B2) at (12,0) ; (B3) at (14,0) ; (B4) at (16,0) ; (B5) at (10,2) ; (B6) at (12,2) ; (B7) at (14,2) ; (B8) at (16,2) ; (S3) at (18,1) ; (C1) at (20,0) ; (C2) at (22,0) ; (C3) at (24,0) ; (C4) at (26,0) ; (C5) at (20,2) ; (C6) at (22,2) ; (C7) at (24,2) ; (C8) at (26,2) ; (S4) at (28,1) ; (SN) at (38,1) ; (SNl) at (39.2,1) [$s_n$]{};

(SP) at (36,-2.5) ; (SPl) at (37,-2.5) [$s'$]{};

(CC1) at (32,-5) ; (CC1l) at (32,-5.8) [$c_1$]{};

(CCi) at (20,-5) ; (CCil) at (20,-5.8) [$c_i$]{}; (CCii) at (14,-5) ; (CCiil) at (14,-5.8) [$c_{i+1}$]{};

(Zl) at (-3,-5) [$z$]{}; (Z) at (-2,-5) ;

\(S) – (A1); (A1) – (A2); (A2) – (A3); (A3) – (A4); (A4) – (S2); (S) – (A5); (A5) – (A6); (A6) – (A7); (A7) – (A8); (A8) – (S2);

(S2) – (B1); (B1) – (B2); (B2) – (B3); (B3) – (B4); (B4) – (S3); (S2) – (B5); (B5) – (B6); (B6) – (B7); (B7) – (B8); (B8) – (S3);

(S3) – (C1); (C1) – (C2); (C2) – (C3); (C3) – (C4); (C4) – (S4); (S3) – (C5); (C5) – (C6); (C6) – (C7); (C7) – (C8); (C8) – (S4);

(S4) – (30,0); (S4) – (30,2); (SN) – (36,0); (SN) – (36,2);

(SN) – (SP); (SP) – (CC1);

(CCi) – (C7); (CCii) – (C7); (CCi) – (B3); (CCii) – (B3); (CCi) – (A4); (CCii) – (A4);

(CC1) – (30,-4.5); (CC1) – (30,-4); (CC1) – (30,-3.4);

(CCi) – (22,-4.5); (CCi) – (22,-4); (CCi) – (22,-3.4);

(CCii) – (12,-4.5); (CCii) – (12,-4); (CCii) – (12,-3.4);

\(Z) – (0,-4.5); (Z) – (0,-4); (Z) – (0,-3.4);

[*Correctness.*]{}  Now we can show that $\phi$ is satisfiable if and only if ${\ensuremath{\mathcal{G}}\xspace}$ has a $\Delta$-restless temporal $(s,z)$-path. 

[$(\Rightarrow)$:]{}Let us assume there is a satisfying assignment for formula $\phi$. Then we construct a $\Delta$-restless temporal path from vertex $s$ to $z$ as follows.  Starting from $s$, for each variable $x_i$ of $\phi$ the $\Delta$-restless temporal path passes through the variables $x_i^{(1)}$, $x_i^{(2)}$, $x_i^{(3)}$, and $x_i^{(4)}$, if $x_i$ is set to , and $\bar x_i^{(1)}$, $\bar x_i^{(2)}$, $\bar x_i^{(3)}$, and $\bar x_i^{(4)}$, if $x_i$ is set to , at time step one.  The $\Delta$-restless temporal path arrives at time step one in the vertex $s_n$. In time step two it goes from $s_n$ to $s'$.

At time step three, the $\Delta$-restless temporal path can be extended to $c_1$. In each clause $c_j$ for $j \in [m]$ there is at least one literal $x_i$ (or $\bar x_i$) that is evaluated to .  Let $c_j$ be the $k$th clause in which $x_i$ appears.  We have that, depending on whether $x_i$ is set to  (or ), the vertex $x^{(k)}_i$ (or $\bar x^{(k)}_i$) has not been visited so far.  Hence, the $\Delta$-restless temporal path can be extended from $c_j$ to $c_{j+1}$ (or to $z$ for $j = m$) at time step three via $x^{(k)}_i$ (or $\bar x^{(k)}_i$).  Thus, there exists a $\Delta$-restless temporal $(s,z)$-path in ${\ensuremath{\mathcal{G}}\xspace}$.

[$(\Leftarrow)$:]{}Let us assume that there exists a $\Delta$-restless temporal $(s,z)$-path in the constructed temporal graph ${\ensuremath{\mathcal{G}}\xspace}$. Note that any $\Delta$-restless temporal $(s,z)$-path must reach $s_n$ in time step one because the variable gadget has only edges at time step one and the waiting time ${\ensuremath{\Delta}}=1$ prevents the path to enter the clause gadget (which only has edges at time step three) before using the edge $\{s_n, s'\}$ at time step two. 

It is easy to see that for the first part of the $\Delta$-restless temporal graph from $s$ to $s_n$ it holds that for each $i\in [n]$, it visits either vertices $x_i^{(1)}$, $x_i^{(2)}$, $x_i^{(3)}$, and $x_i^{(4)}$, or vertices $\bar x_i^{(1)}$, $\bar x_i^{(2)}$, $\bar x_i^{(3)}$, and $\bar x_i^{(4)}$. In the former case we set $x_i$ to  and in the latter case we set $x_i$ to .  We claim that this produces a satisfying assignment for $\phi$. In time step three, the part of the $\Delta$-restless temporal path from $s'$ to $z$ has to pass vertices $c_1,c_2,\ldots,c_m$ to reach $z$. The $\Delta$-restless temporal path passes exactly one variable vertex $x_i^{(k)}$ (or $\bar x^{(k)}_i$) when going from $c_j$ to $c_{j+1}$ (and finally from $c_m$ to $z$) that has not been visited so far and that corresponds to a variable that appears in the clause $c_j$ for the $k$th time.  The fact that the variable vertex was not visited implies that we set the corresponding variable to a truth value that makes it satisfy clause $c_j$. This holds for all $j \in [m]$. Hence, each clause is satisfied by the constructed assignment and, consequently, $\phi$ is satisfiable. 

The reduction presented in the proof of \[thm:probRestlessPath:NPh\] also yields a running time lower bound assuming the Exponential Time Hypothesis (ETH) [@IP01; @IPZ01]. 

\[cor:path:eth\] [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{} does not admit a $f({\ensuremath{\ell}})^{o(|{\ensuremath{\mathcal{G}}\xspace}|)}$-time algorithm for any computable function $f$ unless the ETH fails. 

First, note that any [<span style="font-variant:small-caps;">3-SAT</span>]{}formula with $m$ clauses can be transformed into an equisatisfiable [<span style="font-variant:small-caps;">Exact $(3,4)$-SAT</span>]{} formula with $O(m)$ clauses [@Tov84].  The reduction presented in the proof of \[thm:probRestlessPath:NPh\] produces an instance of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{} with a temporal graph of size $|{\ensuremath{\mathcal{G}}\xspace}|\in O(m)$ and ${\ensuremath{\ell}}=3$. Hence an algorithm for [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{} with running time $f({\ensuremath{\ell}})^{o(|{\ensuremath{\mathcal{G}}\xspace}|)}$ for some computable function $f$ would imply the existence of an $2^{o(m)}$-time algorithm for [<span style="font-variant:small-caps;">3-SAT</span>]{}.  This is a contradiction to the ETH [@IP01; @IPZ01]. 

-Hardness for Feedback Vertex Number
------------------------------------

In the following, we show that parameterizing [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}with structural graph parameters of the underlying graph of the input temporal graph presumably does not yield fixed-parameter tractability for a large number of popular parameters. 

\[thm:probRestlessPath:W1hFVS\] [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}parameterized by the feedback vertex number of the underlying graph is -hard for all ${\ensuremath{\Delta}}\ge 1$ even if every edge has only one time stamp. 

We present a parameterized reduction from [<span style="font-variant:small-caps;">Multicolored Clique</span>]{}where, given a $k$-partite graph $H=(U_1\uplus U_2\uplus\ldots\uplus U_k, F)$, we are asked to decide whether $H$ contains a clique of size $k$. [<span style="font-variant:small-caps;">Multicolored Clique</span>]{}is known to be -hard when parameterized by the clique size $k$ [@Fel+09; @Cyg+15]. 

Let $(H=(U_1\uplus U_2\uplus\ldots\uplus U_k, F),k)$ be an instance of [<span style="font-variant:small-caps;">Multicolored Clique</span>]{}.  For each $i,j\in[k]$ with $i<j$ let $F_{i,j} = \{\{u,v\}\in F \mid u\in U_i \wedge v\in U_j\}$ be the set of edges between vertices in $U_i$ and $U_j$. We assume that $k\ge 3$, otherwise we can solve the instance in polynomial time.  Without loss of generality, we assume that for all $i,j,i',j'\in[k]$ with $i<j$ and $i'<j'$ we have that $|F_{i,j}|=|F_{i',j'}|=m$ for some $m\in{\mathbb{N}}$. Note that if this is not the case, we add new vertices and single edges to increase the cardinality of some set $F_{i,j}$ and this does not introduce new cliques since $k\ge 3$. We further assume that without loss of generality that $|U_1|=|U_2|=\ldots=|U_k|=n$ for some $n\in{\mathbb{N}}$. If this is not the case, we can add additional isolated vertices to increase the cardinality of some set $U_i$. We construct a temporal graph ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ with two distinct vertices $s,z\in V$ such that there is a $\Delta$-restless [temporal $(s,z)$-path]{} in ${\ensuremath{\mathcal{G}}\xspace}$ if and only if $H$ contains a clique of size $k$. Furthermore, we show that the underlying graph ${\ensuremath{G_{\downarrow}}\xspace}$ of ${\ensuremath{\mathcal{G}}\xspace}$ has a feedback vertex number in $O(k^2)$.

[*Vertex Selection Gadgets.*]{}  For each set $U_i$ with $i\in[k]$ of the vertex set of $H$ we create the following gadget.  Let $U_i = \{u_1^{(i)}, u_2^{(i)}, \ldots, u_{n}^{(i)}\}$. We create a path of length $k\cdot n + n + 1$ on fresh vertices $w_1^{(i)},v_{1,1}^{(i)}, v_{1,2}^{(i)}, \ldots, v_{1,k}^{(i)},w_2^{(i)}, v_{2,1}^{(i)}, \ldots, v_{n,k}^{(i)},w_{n+1}^{(i)}$. Intuitively, this path contains a segment of length $k$ for each vertex in $U_i$ which are separated by the vertices $w_j^{(i)}$, and the construction will allow a $\Delta$-restless [temporal $(s,z)$-path]{} to skip exactly one of these segments, which is going to correspond to selecting this vertex for the clique. 

Formally, for each vertex $u_j^{(i)}\in U_i$ we create $k$ vertices $v_{j,1}^{(i)}, v_{j,2}^{(i)}, \ldots, v_{j,k}^{(i)}$, which we call the *segment corresponding to $u_j^{(i)}$*.  We further create vertices $w_1^{(i)}, w_2^{(i)}, \ldots, w_{n+1}^{(i)}$. For all $j\in[n]$ and $x\in [k-1]$ we connect vertices $v_{j,x}^{(i)}$ and $v_{j,x+1}^{(i)}$ with an edge at time $(i-1)\cdot n + j$ and we connect $w_j^{(i)}$ with $v_{j,1}^{(i)}$ and $w_{j+1}^{(i)}$ with $v_{j,k}^{(i)}$ at time $(i-1)\cdot n + j$ each.  Lastly, we introduce a “skip vertex” $s^{(i)}$ that will allow a $\Delta$-restless [temporal $(s,z)$-path]{} to skip one path segment of length $k$ that corresponds to one of the vertices in $U_i$. For each $j\in[n+1]$, we connect vertices $s^{(i)}$ and $w_{j}^{(i)}$ with an edge at time $(i-1)\cdot n+j$.

Now we connect the gadgets for all $U_i$’s in sequence, that is, a $\Delta$-restless [temporal $(s,z)$-path]{} passes through the gadgets one after another, selecting one vertex of each part $U_i$. Formally, for all $i\in [k-1]$, we connect vertices $w_{n+1}^{(i)}$ and $w_{1}^{(i+1)}$ with an edge at time $i\cdot n + 1$. It is easy to check that the set $\{s^{(1)}, s^{(2)}, \ldots, s^{(k)}\}$ forms a feedback vertex set of size $k$ for the vertex selection gadgets.  The vertex selection gadget is visualized in \[fig:pathred2\]. 

(Sl) at (-3,-1) [$s$]{}; (S) at (-3,0) ; (S1) at (18,4) ; (S1l) at (18,4.8) [$s^{(1)}$]{}; (W1) at (0,0) ; (W1l) at (-.3,-1) [$w_1^{(1)}$]{}; (A1) at (2,0) ; (A1l) at (2,-1) [$v_{1,1}^{(1)}$]{}; (A2) at (4,0) ; (A2l) at (4,-1) [$v_{1,2}^{(1)}$]{}; (A3) at (6,0) ; (A3l) at (6,-1) [$v_{1,3}^{(1)}$]{}; (Ak) at (10,0) ; (Akl) at (10,-1) [$v_{1,k}^{(1)}$]{}; (W2) at (12,0) ; (W2l) at (12.3,-1) [$w_2^{(1)}$]{}; (B1) at (14,0) ; (B2) at (16,0) ; (B3) at (18,0) ; (Bk) at (22,0) ; (W3) at (24,0) ; (W3l) at (24,-1) [$w_3^{(1)}$]{}; (C1) at (26,0) ; (Dk) at (34,0) ; (Wn) at (36,0) ; (Wnl) at (36,-1) [$w_n^{(1)}$]{}; (Wnn) at (40,0) ; (Wnnl) at (40,-1) [$w_1^{(2)}$]{};

\(S) – (W1); (W1) – (A1); (A1) – (A2); (A2) – (A3); (A3) – (7.2,0); (Ak) – (8.8,0); (Ak) – (W2);

(W2) – (B1); (B1) – (B2); (B2) – (B3); (B3) – (19.2,0); (Bk) – (20.8,0); (Bk) – (W3);

(W3) – (C1); (C1) – (28,0);

(Dk) – (32,0); (Dk) – (Wn);

(Wn) – (Wnn); (Wnn) – (42,0); (Wnn) – (41.8,0.6);

(W1) – (S1); (W2) – (S1); (W3) – (S1); (Wn) – (S1);

[*Validation Gadgets.*]{}  A $\Delta$-restless [temporal $(s,z)$-path]{} has to pass through the validation gadgets after it passed through the vertex selection gadgets.  Intuitively, this should only be possible if the selected vertices form a clique.  We construct the gadget in the following way. 

For each $i,j\in[k]$ with $i<j$ let the edges in $F_{i,j}$ be ordered in an arbitrary way, that is, $F_{i,j} = \{e_1^{(i,j)}, e_2^{(i,j)},\ldots, e_{m}^{(i,j)}\}$. We create two paths of length $2m$ on fresh vertices $v_{1,1}^{(i,j)}, v_{1,2}^{(i,j)}, v_{2,1}^{(i,j)},$ $v_{2,2}^{(i,j)}, \ldots, v_{m,2}^{(i,j)}$ and $v_{1,3}^{(i,j)}, v_{1,4}^{(i,j)}, v_{2,3}^{(i,j)}, v_{2,4}^{(i,j)}, \ldots, v_{m,4}^{(i,j)}$, respectively.  Intuitively, the *first path* selects an edge from $U_i$ to $U_j$ and the transition to the *second path* should only be possible if the two endpoints of the selected edge are selected in the corresponding vertex selection gadgets. 

Formally, for each edge $e_h^{(i,j)}\in F_{i,j}$ we create four vertices $v_{h,1}^{(i,j)}, v_{h,2}^{(i,j)}, v_{h,3}^{(i,j)}, v_{h,4}^{(i,j)}$. Furthermore, we introduce three extra vertices $s_1^{(i,j)},s_2^{(i,j)},s_3^{(i,j)}$. For all $h\in[m]$ we connect vertices $v_{h,1}^{(i,j)}$ and $v_{h,2}^{(i,j)}$ with an edge at time $y_{i,j} + 2h-1$, we connect vertices $v_{h,1}^{(i,j)}$ and $s_1^{(i,j)}$ with an edge at time $y_{i,j} + 2h-1$, we connect vertices $v_{h,3}^{(i,j)}$ and $v_{h,4}^{(i,j)}$ with an edge at time $y_{i,j} + 2h-1$, we connect vertices $v_{h,3}^{(i,j)}$ and $s_3^{(i,j)}$ with an edge at time $y_{i,j} + 2h-1$, and if $h<m$, we connect vertices $v_{h,2}^{(i,j)}$ and $v_{h+1,1}^{(i,j)}$ with an edge at time $y_{i,j} + 2h$ and we connect vertices $v_{h,4}^{(i,j)}$ and $v_{h+1,3}^{(i,j)}$ with an edge at time $y_{i,j} + 2h$, where $y_{i,j}=k\cdot n+2m\cdot (i\cdot j+\frac{1}{2}\cdot i\cdot (i-1)-1)$ (the value of $y_{i,j}$ can be interpreted as a “time offset” for the validation gadget for $F_{i,j}$, the value is computed by adding all time steps needed in validation gadget for $F_{i',j'}$ with $i'<j'$, $i'\le i$, $j'\le j$, and $(i',j')\neq (i,j)$).  Next, for each edge $e_h^{(i,j)}= \{u_a^{(i)},u_b^{(j)}\}\in F_{i,j}$ we connect vertices $s_1^{(i,j)}$ and $v_{a,j}^{(i)}$ (from the vertex selection gadget for $U_i$) with an edge at time $y_{i,j} + 2h-1$, we connect vertices $s_2^{(i,j)}$ and $v_{a,j}^{(i)}$ with an edge at time $y_{i,j} + 2h-1$, we connect vertices $s_2^{(i,j)}$ and $v_{b,i}^{(j)}$ (from the vertex selection gadget for $U_j$) with an edge at time $y_{i,j} + 2h-1$, and we connect vertices $s_3^{(i,j)}$ and $v_{b,i}^{(j)}$ with an edge at time $y_{i,j} + 2h-1$.

Now we connect the gadgets for all $F_{i,j}$’s in sequence, that is, a $\Delta$-restless [temporal $(s,z)$-path]{} passes through the gadgets one after another, selecting one edge of each part $F_{i,j}$ of the edge set $F$. Formally, for each $i,j\in[k]$ with $i<j$, if $i< j-1$, we connect vertices $v_{m,4}^{(i,j)}$ and $v_{1,1}^{(i+1,j)}$ with an edge at time $y_{i+1,j}$, and if $i= j-1<k-1$, we connect vertices $v_{m,4}^{(i,j)}$ and $v_{1,1}^{(i,j+1)}$ with an edge at time $y_{i,j+1}$. It is easy to check that the set $\{s^{(1,2)}_1, s^{(1,2)}_2, s^{(1,2)}_3, s^{(1,3)}_1, \ldots, s^{(1,k)}_3, \ldots s^{(k-1,k)}_3\}$ forms a feedback vertex set of size $3\cdot \binom{k}{2}$ for the validation gadgets.  The validation gadget is visualized in \[fig:pathred3\]. 

Finally, we create two new vertices $s$ and $z$, we connect vertices $s$ and $w_1^{(1)}$ (the “first” vertex of the vertex selection gadgets) with an edge at time one, we connect vertices $s$ and $s^{(1)}$ (the “skip vertex” of the first vertex selection gadget) with an edge at time one, and we connect $z$ and $v_{m,4}^{(k-1,k)}$ (the “last” vertex of the validation gadgets) with an edge at time $k\cdot n+m\cdot (3k^2+5k+3)$. We further connect vertices $w_{n+1}^{(k)}$ and $v_{1,1}^{(1,2)}$ (connecting the vertex selection gadgets and the validation gadgets) with an edge at time $k\cdot n$. Finally, we set $\Delta=1$. This completes the contruction.  It is easy to check that ${\ensuremath{\mathcal{G}}\xspace}$ can be constructed in polynomial time and that the feedback vertex number of ${\ensuremath{G_{\downarrow}}\xspace}$ is at most $k+3\cdot\binom{k}{2}$ and that every edge has only one time stamp. 

(A11) at (0,0) ; (A12) at (0,-2) ; (A21) at (0,-4) ; (A22) at (0,-6) ; (A31) at (0,-8) ; (A32) at (0,-10) ; (A41) at (0,-12) ; (A41l) at (-2,-12) [$v_{h,1}^{(i,j)}$]{}; (A42) at (0,-14) ; (Am1) at (0,-20) ; (Am2) at (0,-22) ;

(S1) at (8,-11) ; (S2) at (14,-11) ; (S3) at (20,-11) ; (S1l) at (9,-12.6) [$s_1^{(i,j)}$]{}; (S2l) at (14,-12.6) [$s_2^{(i,j)}$]{}; (S3l) at (19,-12.6) [$s_3^{(i,j)}$]{};

(B11) at (28,0) ; (B12) at (28,-2) ; (B21) at (28,-4) ; (B22) at (28,-6) ; (B31) at (28,-8) ; (B32) at (28,-10) ; (B41) at (28,-12) ; (B41l) at (30,-12) [$v_{h,3}^{(i,j)}$]{}; (B42) at (28,-14) ; (Bm1) at (28,-20) ; (Bm2) at (28,-22) ;

(A11) – (A12); (A12) – (A21); (A21) – (A22); (A22) – (A31); (A31) – (A32); (A32) – (A41); (A41) – (A42); (A42) – (0,-15.6); (Am1) – (0,-18.4); (Am1) – (Am2);

(B11) – (B12); (B12) – (B21); (B21) – (B22); (B22) – (B31); (B31) – (B32); (B32) – (B41); (B41) – (B42); (B42) – (28,-15.6); (Bm1) – (28,-18.4); (Bm1) – (Bm2);

(A11) – (S1); (A21) – (S1); (A31) – (S1); (A41) – (S1); (Am1) – (S1);

(B11) – (S3); (B21) – (S3); (B31) – (S3); (B41) – (S3); (Bm1) – (S3);

(Vij) at (9,-2) ; (Vji) at (19,-2) ; (Vijl) at (7.4,-3.6) [$v_{a,j}^{(i)}$]{}; (Vjil) at (20.6,-3.6) [$v_{b,i}^{(j)}$]{};

(Vij) – (S1); (Vij) – (S2); (Vji) – (S2); (Vji) – (S3);

(Uil) at (10,1) [$U_i$]{}; (Ujl) at (18,1) [$U_j$]{};

(Vij) – (13,-2) – (10,0) – (7,-2) – (Vij); (Vji) – (21,-2) – (18,0) – (15,-2) – (Vji); (13,-2) – (15,-2); (7,-2) – (6,-2); (21,-2) – (22,-2);

(A11) – (-2,0); (Bm2) – (30,-22);

[*Correctness.*]{}  Now we show that $H$ contains a clique of size $k$ if and only if there is a $\Delta$-restless temporal path from $s$ to $z$ in ${\ensuremath{\mathcal{G}}\xspace}$.

[$(\Rightarrow)$:]{}Assume that $H$ contains a clique of size $k$ and let $X\subseteq V(H)$ with $|X| = k$ be the set of vertices that form the clique in $H$. Now we show how to construct a $\Delta$-restless [temporal $(s,z)$-path]{} in ${\ensuremath{\mathcal{G}}\xspace}$. Note that since $H$ is $k$-partite, we have that $|U_i\cap X|=1$ for all $i\in [k]$. The temporal path starts at vertex $s$ in ${\ensuremath{\mathcal{G}}\xspace}$ and then first passes through the vertex selection gadgets.  If $u_j^{(i)}\in X$ for some $i\in [k]$ and $j\in [n]$, then the temporal path skips the segment corresponding to $u_j^{(i)}$ in the vertex selection gadget for $U_i$. More formally, the temporal path follows the vertices $w_1^{(i)},v_{1,1}^{(i)}, v_{1,2}^{(i)}, \ldots,v_{1,k}^{(i)}, w_2^{(i)},\ldots, v_{j-1,k}^{(i)}, w_{j}^{(i)}, s^{(i)}, w_{j+1}^{(i)}, v_{j+1,1}^{(i)}, \ldots, v_{n,k}^{(i)}, w_{n+1}^{(i)}$ in that order, that is, it skips vertices $v_{j,1}^{(i)}, v_{j,2}^{(i)}, \ldots, v_{j,k}^{(i)}$. It is easy to check that the time labels of the edges in the vertex selection gadget allow for a restless temporal path as described that respects the waiting time ${\ensuremath{\Delta}}$.

In the validation gadget for $F_{i,j}$ with $i<j$, the path “selects” the edge $(U_i\cap X)\cup(U_j\cap X)\in F_{i,j}$ that connects the vertices from the parts $U_i$ and $U_j$ that are contained in the clique $X$. Let $(U_i\cap X)\cup(U_j\cap X)=\{u_a^{(i)},u_b^{(j)}\}=e_h^{(i,j)}\in F_{i,j}$. Formally, the path follows vertices $v_{1,1}^{(i,j)}, v_{1,2}^{(i,j)}, v_{2,1}^{(i,j)}, v_{2,2}^{(i,j)}, \ldots, v_{h,1}^{(i,j)}, s_1^{(i,j)},v_{a,j}^{(i)},s_2^{(i,j)},v_{b,i}^{(j)}, s_3^{(i,j)},v_{h,4}^{(i,j)}, v_{h+1,3}^{(i,j)}, v_{h+1,4}^{(i,j)}, \ldots, v_{m,4}^{(i,j)}$ in that order.  Note that vertices $v_{a,j}^{(i)}$ and $v_{b,i}^{(j)}$ have not been used by the path in the vertex selection gadgets, since they appear in the segments that were skipped by the temporal path in the corresponding vertex selection gadgets.  Furthermore, since the clique in $H$ only contains one edge that connects vertices from $U_i$ and $U_j$, the vertices $v_{a,j}^{(i)}$ and $v_{b,i}^{(j)}$ have not been used by the temporal path in an earlier validation gadget.  It is easy to check that the time labels of the edges in the validation gadget allow for a $\Delta$-restless temporal path as described.  After the last validation gadget the path arrives at vertex $z$. Hence, we have found a $\Delta$-restless [temporal $(s,z)$-path]{} in ${\ensuremath{\mathcal{G}}\xspace}$.

[$(\Leftarrow)$:]{}Assume that we are given a $\Delta$-restless [temporal $(s,z)$-path]{} in ${\ensuremath{\mathcal{G}}\xspace}$. We now show that $H$ contains a clique of size $k$.

After starting at $s$, the $\Delta$-restless temporal path first passes the vertex selection gadgets.  Here, we need to make the important observation, that for each $i\in[k]$, any $\Delta$-restless [temporal $(s,z)$-path]{} has to “skip” at least one segment corresponding to one vertex $u^{(i)}_j\in U_i$ in the vertex selection gadget corresponding to $U_i$, otherwise the temporal path cannot traverse the validation gadgets.  More formally, assume for contradiction that there is a $\Delta$-restless [temporal $(s,z)$-path]{} and an $i\in[k]$ such that the temporal path visits all vertices in the vertex selection gadget corresponding to $U_i$. Let $j\in[k]$ with $j\neq i$. Assume that $i<j$ (the other case works analogous).  We claim that the temporal path cannot traverse the validation gadget for $F_{i,j}$. For the temporal path to go from $s^{(i,j)}_1$ to $s^{(i,j)}_2$ by construction it has to visit at least one vertex from the vertex selection gadget for $U_i$. If all vertices have already been visited, that would mean the $\Delta$-restless [temporal $(s,z)$-path]{} visits one vertex twice—a contradiction. 

The waiting time ${\ensuremath{\Delta}}$ prevents the temporal path from “skipping” more than one segment.  More formally, any $\Delta$-restless [temporal $(s,z)$-path]{} arrives at the “skip vertex” $s^{(i)}$ of the vertex selection gadget for $U_i$ at time $(i-1)\cdot n + j$, for some $j\in[k-1]$. By construction this means the path visits $w_j^{(i)}$, then $s^{(i)}$, and then has to continue with $w_{j+1}^{(i)}$ since there is only one time edge the path can use without violating the waiting time $\Delta$. It follows that the temporal path skips exactly the segment corresponding to $u_j^{(i)}\in U_i$.

This implies that any $\Delta$-restless [temporal $(s,z)$-path]{} that traverses the vertex selection gadgets leaves exactly one segment of every vertex selection gadget unvisited.  Let the set $X = \{u^{(i)}_j\in U_i \mid i\in[k] \wedge j\in[n] \wedge v_{j,1} \text{ is an unvisited vertex.}\}$ be the set of vertices corresponding to the segments that are “skipped” by the given $\Delta$-restless [temporal $(s,z)$-path]{}.  It is easy to check that $|X|=k$. We claim that $X$ is a clique in $H$.

Assume for contradiction that it is not.  Then there are two vertices $u_{i'}^{(i)}, u_{j'}^{(j)}\in X$ such that the edge $\{u_{i'}^{(i)}, u_{j'}^{(j)}\}$ is not in $F$. Assume that $i<j$. We show that then the $\Delta$-restless [temporal $(s,z)$-path]{} is not able to pass through the validation gadget for $F_{i,j}$. By assumption we have that $\{u_{i'}^{(i)}, u_{j'}^{(j)}\}\notin F_{i,j}$. Note that the validation gadget is designed in a way that the first path “selects” an edge from $F_{i,j}$ and then the waiting time of one enforces that a $\Delta$-restless [temporal $(s,z)$-path]{} can only move from the first path to the second path of a validation gadget if the two endpoints of the selected edge are vertices whose corresponding segments in the vertex selection gadget were skipped.  We have seen that for every $U_i$ with $i\in[k]$, the path segment corresponding to exactly one vertex of that set was skipped.  Since $\{u_{i'}^{(i)}, u_{j'}^{(j)}\}\notin F_{i,j}$, we have that for every edge in $F_{i,j}$ that the segment corresponding to at least one of the two endpoint of the edge was *not* skipped.  Hence, we have that the $\Delta$-restless temporal path cannot pass through the validation gadget of $F_{i,j}$ and cannot reach $z$—a contradiction. 

An FPT-Algorithm for Short Restless Temporal Path {#sec:fptalg}
=================================================

In this section, we discuss how to find *optimal* restless temporal paths.  Of course, we have by \[thm:probRestlessPath:NPh\] that it is NP-hard to find optimal restless temporal paths for all optimality criteria introduced in \[subs:path:opt\].  However, the problem of finding restless temporal path with a certain quality introduces a natural parameter to the problem, which we want to discuss here. 

From \[thm:probRestlessPath:NPh\] we can deduce that there is not much hope for fast or foremost restless temporal paths, since the instance constructed in the reduction has lifetime ${\ensuremath{\ell}}= 3$ and hence the duration as well as the arrival time of any restless temporal path in this instance is at most three.  However, we can observe that in all our reductions (the one of \[thm:probRestlessPath:NPh\] and the one of \[thm:probRestlessPath:W1hFVS\]) the length of $\Delta$-restless [temporal $(s,z)$-path]{} is unbounded.  We defined [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}as the problem of finding restless temporal path of bounded length, and indeed it is known that [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}is fixed-parameter tractable when parameterized by the length bound $k$.

In this section, we show that there is a ${5.181}^{k}\cdot|{\ensuremath{\mathcal{G}}\xspace}|^{O(1)}$ algorithm for [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}, where $k$ is the length bound of the path.  Note that from \[cor:path:eth\] it follows that this algorithm is asymptotically optimal, unless the ETH fails.  Formally, our goal is to show the following theorem. 

\[thm:fpt-length\] [<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}can be solved in ${5.181}^{k}\cdot|{\ensuremath{\mathcal{G}}\xspace}|\cdot{\ensuremath{\Delta}}$ time. 

The actual proof of \[thm:fpt-length\] is deferred to the end of this section.  In the nutshell, we first reduced the [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{} to a problem on directed graphs, where identify which objects (in the directed graph) exactly describe a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{} in the given temporal graph.  Then, we introduce a new problem called [<span style="font-variant:small-caps;">Independent Path</span>]{}, which can capture the nature of or desired objects.  Given a directed graph $D$ with two distinct vertices $s$ and $z$ and a linear matroid $M$, the [<span style="font-variant:small-caps;">Independent Path</span>]{} problem asks whether there is a [$(s,z)$-dipath]{} in $D$ whose vertices form an independent set in the matroid $M$ (see \[sec:ipp\]).  Then, to solve [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{}, we develop a fixed-parameter algorithm for [<span style="font-variant:small-caps;">Independent Path</span>]{} parameterized by the length of a shortest witness. 

We introduce a so-called *${\ensuremath{\Delta}}$-$(s,z)$-expansion* of for two vertices $s$ and $z$ of a temporal graphs with waiting-times.  That is, a time-expanded version of the temporal graph which reduces reachability questions to directed graphs.  In the literature, similar approaches have been applied several times.  However, to the best of our knowledge, this is the first time that waiting-times are respected.  In a nutshell, the ${\ensuremath{\Delta}}$-$(s,z)$-expansion has essentially for each vertex $v$ at most ${\ensuremath{\ell}}$ many copies $v_1,\dots, v_{{\ensuremath{\ell}}}$ and if a [$(s,z)$-dipath]{} visits $v_i$ means the corresponding [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-walk]{} visits $v$ at time $i$, where ${\ensuremath{\ell}}$ is the time horizon. 

\[def:expansion\] Let ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ be a temporal graph with two distinct vertices $s,z \in V$ such that $\{s,z\} \not \in E_t$, for all $t \in [{\ensuremath{\ell}}]$. Let ${\ensuremath{\Delta}}\le{\ensuremath{\ell}}$. The *${\ensuremath{\Delta}}$-$(s,z)$-expansion* of ${\ensuremath{\mathcal{G}}\xspace}$ is the directed graph $D=(V',E')$ with $$\begin{aligned}
    V' :=&\ \{s,z\} \cup \left\{ v^{t}\ \middle\vert\ v \in e, e \in E_t, v \not \in \{ s, z \} \right\}, \\
    E' :=&\ E_s \cup E_z \cup \left\{(v^i,w^t) \ \middle\vert\ v^i \in V' \setminus \{ s, z \}, \{v,w\} \in E_t, 0 \leq t-i \leq {\ensuremath{\Delta}}\right\}, \\
    E_s :=&\ \left\{ (s,v^t) \ \middle\vert\   \{s,v\} \in E_t, \right\}, \text{and} \\
    E_z :=&\ \left\{(v^i,z) \ \middle\vert\ v^i \in V' \setminus \{ s, z \},  \{v,z\} \in E_t, 0 \leq t-i \leq {\ensuremath{\Delta}}\right\}.\end{aligned}$$ Furthermore, we define $V'(s) := \{ s \}$, $V'(z) := \{ z \}$, and $V'(v) := \{ v^{t} \in V' \mid t \in [{\ensuremath{\ell}}] \}$, for all $v \in V \setminus \{s,z\}$.

Next, we show that a ${\ensuremath{\Delta}}$-$(s,z)$-expansion of a temporal graph can be computed efficiently. 

\[lem:exp-runtime\] Given a temporal graph ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$, two distinct vertices $s,z\in V$, and ${\ensuremath{\Delta}}\le{\ensuremath{\ell}}$, we can compute its ${\ensuremath{\Delta}}$-$(s,z)$-expansion $D$ with $|V(D)| \in O(|{\ensuremath{\mathcal{G}}\xspace}|)$ in $O(|{\ensuremath{\mathcal{G}}\xspace}|\cdot {\ensuremath{\Delta}})$ time. 

Let $V' := \{s,z\}$ and $E'$ be empty in the beginning.  We will fill up $V'$ and $E'$ simultaneously.  In order to that efficiently, we will maintain for each vertex $v\in V$ a ordered list $L_v$ such that $t \in L_v$ if and only if $v^t \in V'$. We assume that $|V| \leq \sum_{i=1}^{\ensuremath{\ell}}|E_i|$, because vertices which are isolated in every layer are irrelevant for the ${\ensuremath{\Delta}}$-$(s,z)$-expansion and can be erased in linear time. 

We proceed as follows.  For each $t \in \{1,\dots,{\ensuremath{\ell}}\}$ (in ascending order), we iterate over $E_t$. For each $\{v,w\} \in E_t$, we distinguish into three cases. 

($w=s$):

:   We add $v^t$ to $V'$, $(s,v^t)$ to $E'$, and add $t$ to $L_v$. This can be done in constant time. 

($w=z$):

:   We add $v^t$ to $V'$, and add $t$ to $L_v$. Now we iterate over all $i \in L_v$ (in descending order) and add $(v^i,z)$ to $E'$ until $ t - i > {\ensuremath{\Delta}}$. This can be done in $O({\ensuremath{\Delta}})$ time. 

($\{s,z\} \cap \{v,w\} = \emptyset$):

:   We add $v^t,w^t$ to $V'$, and add $t$ to $L_v$ and $L_w$. Now we iterate over $i\in L_v$ (in descending order) and add $(v^i,w^t)$ to $E'$ until $ t - i > {\ensuremath{\Delta}}$. Afterwards, we iterate over $i\in L_w$ (in descending order) and add $(w^i,v^t)$ to $E'$ until $ t - i > {\ensuremath{\Delta}}$. This can be done in $O({\ensuremath{\Delta}})$ time. 

Observe that after this procedure the digraph $D=(V',E')$ is the ${\ensuremath{\Delta}}$-$(s,z)$-expansion of ${\ensuremath{\mathcal{G}}\xspace}$ and that we added at most $2$ vertices for each time-edge in ${\ensuremath{\mathcal{G}}\xspace}$. Hence, $V' \leq |{\ensuremath{\mathcal{G}}\xspace}|$. This gives a overall running time of $O(|{\ensuremath{\mathcal{G}}\xspace}|\cdot{\ensuremath{\Delta}})$.

It is easy to see that there is a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-walk]{} in the temporal graph if and only if there is a [$(s,z)$-dipath]{} in the ${\ensuremath{\Delta}}$-$(s,z)$-expansion.  Next, we identify the necessary side constraint to identify [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{}s in the ${\ensuremath{\Delta}}$-$(s,z)$-expansion. 

\[lem:exp-correct\] Let ${\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace}$ be a temporal graph, $s,z \in V$ two distinct vertices, ${\ensuremath{\Delta}}\le{\ensuremath{\ell}}$, and $D=(V',E')$ the ${\ensuremath{\Delta}}$-$(s,z)$-expansion of ${\ensuremath{\mathcal{G}}\xspace}$. There is a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{} in ${\ensuremath{\mathcal{G}}\xspace}$ of length $k$ if and only if there is an [$(s,z)$-dipath]{} $P'$ in $D$ of length $k$ such that for all $v \in V$ it holds that $|V'(v) \cap V(P')| \leq 1$.

($\Rightarrow$): Let $P = \big( (\{s,v_1\}, t_1), (\{v_1, v_2\}, t_2), \dots, (\{v_{k'-1},z\}, t_{k'} ) \big)$ be a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{} in ${\ensuremath{\mathcal{G}}\xspace}$ of length $k$. We can inductively construct an [$(s,z)$-dipath]{} $P'$ in $D$. Observe that $P_1' := (s,v_1^{t_1}))$ is an [$(s,v_1^{t_1})$-dipath]{} of length $1$ in $D$, because the arc $(s,v_1^{t_1})$ is in $E_s$ of $D$. Now let $i \in [k'-2]$ and $P'_i$ be an [$(s,v_i^{t_i})$-dipath]{} of length $i$ such that

for all $j \in [i]$, we have that $|V'(v_j) \cap V(P'_i)| = 1$, and

for all $v \in V \setminus \{s,v_1,\dots,v_i\}$, we have that $|V'(v) \cap V(P'_i)| = 0$.

In order to get an [$(s,v_{i+1}^{t_{i+1}})$-dipath]{} $P'_{i+1}$ of length $i+1$, we extend $P'_{i}$ by the arc $(v_i^{t_i},v_{i+1}^{t_{i+1}})$. Observe, that $v_{i+1}^{t_{i+1}} \in V'$ because of the time-edge $(\{v_i,v_{i+1}\},t_{i+1})$ in ${\ensuremath{\mathcal{G}}\xspace}$ and that the arc $(v_i^{t_i},v_{i+1}^{t_{i+1}}) \in E'$, because we have $0 \leq t_{i+1} - t_i \leq \beta(v_i)$. Observe that

for all $j \in [i+1]$, we have that $|V'(v_j) \cap V(P'_{i+1})| = 1$, and

for all $v \in V \setminus \{s,v_1,\dots,v_{i+1}\}$, we have that $|V'(v) \cap V(P'_{i+1})| = 0$.

Hence, we have an [$(s,v_{k'-1}^{t_{k'-1}})$-dipath]{} $P'_{k-1}$ of length $k-1$ satisfying (i) and (ii) which can be extended (in a similar way) to an [$(s,z)$-dipath]{} of length $k$ such that for all $v \in V$ it holds that $|V'(v) \cap V(P')| \leq 1$.

($\Leftarrow$): Let $P'$ be a [$(s,z)$-dipath]{} in $D$ of length $k$ such that for all $v \in V$ it holds that $|V'(v) \cap V(P')| \leq 1$. Let $V(P') = \{ s,v_1^{t_1},\dots,v_{k-1}^{t_{k-1}},z\}$. Observe that an arc from $s$ to $v_1^{t_1}$ in $D$ implies that there is a time-edge $(\{s,v_1\},t_1)$ in ${\ensuremath{\mathcal{G}}\xspace}$. Similarly, an arc from $v_i^{t_i}$ to $v_{i+1}^{t_{i+1}}$ implies that there is a time-edge $(\{v_i,v_{i+1}\},t_{i+1})$ in ${\ensuremath{\mathcal{G}}\xspace}$ and that $0 \leq t_{i+1} - t_i \leq \beta(v_i)$, for all $i \in [k-2]$. Moreover, an arc from $v_{k-1}^{t_{k-1}}$ to $z$ implies that there is some $t_{k}$ such that there is a time-edge $(\{v_k,z\},t_{k})$ in ${\ensuremath{\mathcal{G}}\xspace}$ with $0 \leq t_{k} - t_{k-1} \leq \beta(v_{k-1})$. Hence, $P = \big( (\{s,v_1\}, t_1), (\{v_1, v_2\}, t_2), \dots, (\{v_{k'-1},z\}, t_{k'} ) \big)$ is a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-walk]{} of length $k$ in ${\ensuremath{\mathcal{G}}\xspace}$. Finally, $|V'(v) \cap V(P')| \leq 1$, for all $v \in V$, implies that $v_i \not = v_j$ for all $i,j \in \{0,\dots,k\}$ with $i \not = j$. Thus, $P$ is a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{} of length $k$.

Independent Path Problem {#sec:ipp}
------------------------

In this section, we introduce a problem, [<span style="font-variant:small-caps;">Independent Path</span>]{}.  To do so, we need some notations first. 

We use standard terminology from matroid theory [@Oxl92].  A pair $(U,{\mathcal{I}})$, where $U$ is the *ground set* and ${\mathcal{I}}\subseteq 2^U$ is a family of *independent sets*, is a *matroid* if the following holds:

-   $\emptyset \in {\mathcal{I}}$,

-   if $A' \subseteq A$ and $A \in {\mathcal{I}}$, then $A' \in {\mathcal{I}}$, and

-   if $A,B \in {\mathcal{I}}$ and $|A| < |B|$, then there is an $x \in B \setminus A$ such that $A \cup \{x\} \in {\mathcal{I}}$.

An inclusion-wise maximal independent set $A\in {\mathcal{I}}$ of a matroid $M=(U,I)$ is a *basis*.  The cardinality of the bases of $M$ is called the *rank* of $M$. The *uniform matroid of rank $r$* on $U$ is the matroid $(U,{\mathcal{I}})$ with ${\mathcal{I}}=\{S\subseteq U\mid |S|\leq r\}$. A matroid $(U,{\mathcal{I}})$ is *linear* or *representable over a field $\mathbb F$* if there is a matrix $A$ with entries in $\mathbb F$ and the columns labeled by the elements of $U$ such that $S \in {\mathcal{I}}$ if and only if the columns of $A$ with labels in $S$ are linearly independent over $\mathbb F$. Such a matrix $A$ is called a *representation* of $(U,{\mathcal{I}})$.

[Does there exist an $(s,z)$-dipath $P$ of length at most $k$ in $D$ such that $V(P) \in {\mathcal{I}}$?]{}  For the reminder of this section, whenever we speak about *independent sets*, these are independent sets of a matroid and not a set of vertices which induce an edgeless graph. 

We will reduce the [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{} problem to [<span style="font-variant:small-caps;">Independent Path</span>]{} and then develop an efficient algorithm for [<span style="font-variant:small-caps;">Independent Path</span>]{}.  As a subroutine it will be necessary that we restrict the independent sets of a matroid to not exceed a specific size.  An *$k$-truncation* of a matroid $(U,{\mathcal{I}})$ is a matroid $(U,\{ X \in {\mathcal{I}}\mid |X| \leq k \})$ such that all independent sets are of size at most $k$. The $k$-truncation of a linear matroid is also a linear matroid [@Mar09]. 

In our reduction from [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{} to [<span style="font-variant:small-caps;">Independent Path</span>]{} we basically use \[def:expansion\] and a $(k+1)$-truncated partition matroid where we can pick at most one element from each partition.  Two general approaches are know to compute a representation for a $k$-truncate of a linear matroid—one is randomized [@Mar09] and one is deterministic [@LMPS18].[^4] Both approaches require a large field implying that one operation over that field is rather slow.  Furthermore, for the special case of a traversal matroid a quasi-polynomial[^5] algorithm is known.  However, for our specific matroid we employ the Vandermonde matrix to compute a representation over a small finite field.  Note that our approach also outperforms the more general algorithms of @LMPS18 and @Mar09 in terms of running time. 

\[lem:rep\] Given a universe $U$ of size $n$, a partition $P_1 \uplus \dots \uplus P_q = U$, and a natural number $k$, we can compute a representation $A_M$ for the matroid $$\begin{aligned}
    M = \Big(U, \Big\{ X \subseteq U \ \Big\vert\ |X| \leq k 
        \text{ and } \forall i \in [q] \colon |X \cap P_i| \leq 1  \Big\}\Big)
    \end{aligned}$$ over a prime field $\mathbb F$ in $O(k\cdot n)$ time, such that we can compute one operation over $\mathbb F$ in constant time. 

Without loss of generality we assume that $q \leq n$. Let $p$ be a prime number with $q \leq p \leq 2q$. Such a prime exists by the folklore Betrand-Chebyshev Theorem and can be computed in $O(n)$ time using Lagarias-Odlyzko Method [@TCH12].  To perform one operation on the prime field $\mathbb F_p$, one can first perform the primitive operation in $\mathbb Z$ and them take the result modulo $p$. Hence, we can compute one operation over $\mathbb F_p$ in constant time, because $p \in O(n)$ is small and we assume the *RAM model of compution*. 

Let $x_1,\dots,x_q$ be pair-wise distinct elements from $\mathbb F_p$. To compute an $(k \times n)$-matrix $A_M$ as representation for $M$ over $\mathbb F_p$, we compose (column-wise) for each element $u \in P_i$ the vector $\mathbf v_i := \begin{pmatrix}x_i^0 & x_i^1 & \dots & x_i^{k-1} \end{pmatrix}^T$, where $i \in [q]$. That gives a running time of $O(k \cdot n)$ operations over $\mathbb F_p$, since we can compute $\mathbf v_i$ in $O(k)$ operations over $\mathbb F_p$.

It remains to show that $A_M$ is a representation of $M$. Let $X \subseteq U$. If there is an $i \in [p]$ such that $|X \cap P_i| > 1$, then the corresponding columns of $A_M$ are linearly dependent, because we have the vector $\mathbf v_i$ twice.  Now we assume that for all $i \in [q]$ we have $|X \cap P_i| \leq 1$. Furthermore, if $|X| > k$, then we know that the corresponding columns of $A_M$ are linearly dependent, because $A_M$ is an $(k \times n)$-matrix.  We can observe that if $|X| = k$, then the corresponding columns in $A_M$ form a Vandermonde matrix, whose determinat is known to be non-zero.  Hence, if $|X| \leq k$, then the corresponding columns in $A_M$ are linearly independent.  Thus, $A_M$ is a representation of $M$.

Now, we are ready to state our reduction from [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{} to [<span style="font-variant:small-caps;">Independent Path</span>]{}. 

\[lem:tpp-to-ipp\] Given an instance $({\ensuremath{\mathcal{G}}\xspace},s,z,k,{\ensuremath{\Delta}})$ of [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{}, we can compute in $O({\ensuremath{\Delta}}\cdot |{\ensuremath{\mathcal{G}}\xspace}|)$ time an instance $(D,s,z,A_M)$ of [<span style="font-variant:small-caps;">Independent Path</span>]{} such that

(i) $M$ has rank $k+1$, and

(ii) $({\ensuremath{\mathcal{G}}\xspace},s,z,k,{\ensuremath{\Delta}})$ is a [*yes*]{}-instance if and only if $(D,s,z,A_M)$ is a [*yes*]{}-instance and contains an independent [$(s,z)$-dipath]{} of length at most $k$,

where one operation over the finite field of $A_M$ can be computed in constant time. 

Let $({\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace},s,z,k,{\ensuremath{\Delta}})$ be an instance of [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{}.  We construct an instance $(D,s,z,A_M,k)$ of [<span style="font-variant:small-caps;">Independent Path</span>]{} in the following way.  Let digraph $D = (V',E')$ be the ${\ensuremath{\Delta}}$-$(s,z)$-expansion of ${\ensuremath{\mathcal{G}}\xspace}$ which can be computed, by \[lem:exp-runtime\], in $O(|{\ensuremath{\mathcal{G}}\xspace}|\cdot{\ensuremath{\Delta}})$ time such that $V' \in O(|{\ensuremath{\mathcal{G}}\xspace}|)$. Observe that $\bigcup_{v \in V} V'(v)$ is a partition of $V'$. Now, we construct a representation $A_M$ (over a finite field where we can perform one operation in constant time) of the matroid $$\begin{aligned}
        M =  \Big(V', \big\{ X \subseteq V' \ \big\vert\ |X| \leq k+1 \text{ and } \forall v \in V \colon |X \cap V'(v)| \leq 1 \big\}   \Big)
    \end{aligned}$$ in $O(k\cdot|{\ensuremath{\mathcal{G}}\xspace}|)$ time by \[lem:rep\].  Note that $M$ is an $(k+1)$-truncated partition matroid and hence has rank $k+1$. This completes the construction and gives us an overall running time of $O(\max\{k,{\ensuremath{\Delta}}\}\cdot |{\ensuremath{\mathcal{G}}\xspace}|)$.

We now claim $({\ensuremath{\mathcal{G}}\xspace},s,z,k,{\ensuremath{\Delta}})$ is a [*yes*]{}-instance if and only if $(D,s,z,A_M)$ is a [*yes*]{}-instance and contains an independent [$(s,z)$-dipath]{} of length at most $k$.

[$(\Leftarrow)$:]{}Let $P$ be a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{} of length $k' \leq k$ in ${\ensuremath{\mathcal{G}}\xspace}$. Then, by \[lem:exp-correct\] there is an [$(s,z)$-dipath]{} $P'$ of length $k'$ such that for all $v \in V$ it holds that $|V'(v) \cap V(P')| \leq 1$. Since $|V(P')| = k'+1 \leq k+1$, we know that $V(P')$ is an independent set of $M$. Thus, $P'$ is a witness of length at most $k$ for $(D,s,z,A_M)$ being a [*yes*]{}-instance. 

[$(\Rightarrow)$:]{}Let $P'$ be an [$(s,z)$-dipath]{} of length $k' \leq k$ in $D$ such that $V(P')$ is an independent set of $M$. Clearly, for $v \in V$ it holds that $|V'(v) \cap V(P')| \leq 1$. Then, by \[lem:exp-correct\], there is a [${\ensuremath{\Delta}}$-restless temporal $(s,z)$-path]{} of length $k'$ in ${\ensuremath{\mathcal{G}}\xspace}$.

From \[lem:tpp-to-ipp\] it is intermediately clear that the lower-bounds of \[cor:path:eth,thm:probRestlessPath:NPh\] translate to [<span style="font-variant:small-caps;">Independent Path</span>]{}. 

\[cor:ipp-hard\] [<span style="font-variant:small-caps;">Independent Path</span>]{} is NP-hard and unless the ETH fails there is no $2^{o(n)}$-time algorithm for it, where $n$ is the number of vertices. 

### An FPT-Algorithm for [<span style="font-variant:small-caps;">Independent Path</span>]{}

In this section, we provide a fixed-parameter algorithm for [<span style="font-variant:small-caps;">Independent Path</span>]{} parameterized by rank $r$ of the matroid which is, by \[cor:ipp-hard\], asymptotically optimal, unless the ETH fails. 

\[thm:fpt-ipp\] An instance $(D,s,z,A_M)$ of [<span style="font-variant:small-caps;">Independent Path</span>]{} can be solved in time of $O(2^{\omega r}m)$ operations over the field $\mathbb F$, where $\mathbb F$ is the field of $A_M$, $r$ is rank of $M$, $m$ is the number of edges in $D$, and $\omega < 2.373$ is an upper-bound for the matrix multiplication exponent. 

The proof of \[thm:fpt-ipp\] is deferred to the end of this section.  Later \[thm:fpt-ipp\] will follow from \[lem:fpt-ipp-time,lem:fpt-ipp-correct\].  The idea of our algorithm follows the algorithm of @FLPS16 for <span style="font-variant:small-caps;">$k$-Path</span> and independently from us @AJKS19 showed an algorithm which runs in $2^{O(\omega r)} n^{O(1)}$ time for [<span style="font-variant:small-caps;">Independent Path</span>]{} and @LMPSZ18 provided a dynamic program, running in $5.18^{r} n^{O(1)}$ time, for the special case of [<span style="font-variant:small-caps;">Independent Path</span>]{} when the matroid given in the input is a transversal matroid.  Note that both, the algorithm of @AJKS19 and @LMPSZ18 are also based on the idea of @FLPS16.  However, in contrast to @AJKS19 and @LMPSZ18, we show that the algorithm behind \[thm:fpt-ipp\] runs in linear time. 

The main tool of our algorithm are representative families of independent sets. 

\[def:qrep\] Given a matroid $(U,{\mathcal{I}})$, and a family $\mathcal S \subseteq 2^U$, we say that a subfamily $\widehat{\mathcal S} \subseteq \mathcal S$ is a *$q$-representative for $\mathcal S$* if, for each set $Y \subseteq U$ of size at most $q$, it holds that:

-   if there is a set $X \in \mathcal S$ with $X \uplus Y \in {\mathcal{I}}$,

-   then there is a set $\widehat X \in \widehat{\mathcal S}$ with $\widehat X \uplus Y \in {\mathcal{I}}$.

For linear matroids, we can compute small representative families efficiently.  Formally, the following is known. 

\[thm:eff-rep-fam\] Let $M = (U,{\mathcal{I}})$ be a linear matroid of rank $r=p + q$ given together with its representation $A_M$ over field $\mathbb F$. Let $\mathcal S$ be a $p$-family of independents of $M$. Then a $q$-representative family $\widehat{\mathcal S} \subseteq \mathcal S$ of size at most $r \choose p$ can be found in $O\left({r \choose p}tp^\omega + t{r \choose q}^{\omega-1}\right)$ operations over $\mathbb F$, where $\omega < 2.373$ is the matrix multiplication exponent. 

We are now ready to give the pseudo-code of the algorithm behind \[thm:fpt-ipp\] (see \[alg:fpt-ipp\]). 

$T[v,i] \gets \emptyset$, for all $v \in V$ and $i \in [r-1]$.\[line:init-start\] $T[s,0] \gets \{s\}$.\[line:init-end\] (\[line:for-r\])[$i\gets1$ $r-1$]{}[ (\[line:yes\])[$T[z,i] \not=\emptyset$]{}[ ]{} ]{}

\[lem:fpt-ipp-correct\] \[alg:fpt-ipp\] is correct. 

Let $\mathcal P_{w,i} := \{ X \in {\mathcal{I}}\mid $ there is an [$(s,w)$-dipath]{} $P$ of length $i$ such that $V(P)=X \}$, for all $w \in V$ and $i \in [r-1]$. Observe that $\mathcal P_{w,i}$ is an $(i+1)$-family of independent sets.  We show by induction that after iteration $i$ of the for-loop in \[line:for-r\] the entry $T[w,i]$ is an $(r-i)$-representative of $\mathcal P_{w,i}$, for all $w \in V$ and $i \in [r-1]$. Then the correctness follows, since we check after each of these iterations whether $T[w,i]$ is non-empty (\[line:yes\]).  Observe that $\mathcal P_{s,0} = \{ s \}$ and $\mathcal P_{v,0} = \emptyset$ for all $v \in V \setminus \{s\}$. Hence, the entries of $T$ computed in \[line:init-start,line:init-end\] fulfill our induction hypothesis. 

Now let $i \in  [r-1]$ be the current iteration of the for-loop in \[line:for-r\] and assume that for all $j < i$ we have that $T[w,j]$ is an $(r-j)$-representative of $\mathcal P_{w,j}$, for all $w \in V$. Fix a vertex $w \in V$. We first show that if there is an $X \in T[i,w]$, then there is an [$(s,w)$-dipath]{} $P_w$ of length $i$ such that $X=V(P_w) \in {\mathcal{I}}$. Observe that in \[line:N-start,line:N-end\] we look at each possible predecessor $v\in V$ of $w$ in an [$(s,w)$-dipath]{} of length $i$, take each set $X' \in T[v,i-1]$ and check whether $X' \cup \{w\}$ is an independent set of size $i+1$. If this is the case, we add it to $\mathcal N_{w,i}$. After \[line:compress\], we have that $T[w,i] \subseteq \mathcal N_{w,i}$. Since $X' \in T[v,i-1]$, we know that there is an [$(s,v)$-dipath]{} $P_v$ of length $i-1$ with $X' = V(P)$. Thus, if there is an $X \in T[i,w]$, then there is an [$(s,w)$-dipath]{} $P_w$ of length $i$ such that $X=V(P_w) \in {\mathcal{I}}$

Now let $X \in \mathcal P_{w,i}$ and $Y \subseteq V(D)$ a set of vertices of size at most $r - i -1$ such that $X \cap Y = \emptyset$ and $X \uplus Y \in {\mathcal{I}}$. Hence, there is an [$(s,w)$-dipath]{} $P$ of length $i$ such that $V(P) = X$. Let $v$ be the predecessor of $w$ in $P$. Let $P_v$ be the [$(s,v)$-dipath]{} of length $i-1$ induced by $P$ without $w$. Hence, $V(P_v) \in \mathcal P_{v,i-1}$. Moreover, $V(P_v) \cap (Y \cup \{ v \}) = \emptyset$ and $V(P_v) \uplus (Y \cup \{ w \}) \in {\mathcal{I}}$. Since $T[v,i-1]$ is an $(r-i+1)$-representative family of $\mathcal P_{v,i-1}$, we know that there is an $\widehat{X} \in T[v,i-1]$ such that $\widehat{X} \cap (Y \cup \{ w \}) = \emptyset$ and $\widehat{X} \cup (Y \cup \{ w \}) \in {\mathcal{I}}$. In \[line:N-start,line:N-end\] we add $\widehat{X} \cup \{w \}$ to $\mathcal N_{w,i}$. Let $X' := \widehat{X} \cup \{w \}$ and note that $X' \cap Y = \emptyset$ and $X' \uplus Y \in {\mathcal{I}}$. Since $T[w,i]$ is an $(r-i)$-representative family of $\mathcal N_{w,i}$, we know that there is an $\widehat{X'} \in T[w,i]$ such that $\widehat{X'} \cap Y = \emptyset$ and $X' \uplus Y \in {\mathcal{I}}$. Thus, $T[w,i]$ is an $(r-i)$-representative of $\mathcal P_{w,i}$.

Next, we show that \[alg:fpt-ipp\] is actually a fixed-parameter algorithm parameterized by the length of a shortest witness. 

\[lem:fpt-ipp-time\] \[alg:fpt-ipp\] runs in time of $O(2^{\omega r}\cdot m)$ operations over $\mathbb F$, where $\mathbb F$ is the field of $A_M$, $r$ is the rank of the matroid, $m$ is the number of edges, and $\omega = 2.373$ is an upper-bound for the matrix multiplication exponent. 

Without loss of generality we assume to have a total ordering on $V$. We represent a subset of $V$ as a sorted string.  Hence, union and intersection of two sets of size at most $r$ takes $O(r)$ time.  We can thus look up and store sets of size at most $r$ in a trie in $O(r)$ time.  Note that we do not have the time to completely initialize the arrays of size $|V|$ in each trie node.  Instead, we will initialize each array cell of a trie node at its first access.  To keep track of the already initialized cells, we use *sparse sets* over $V$ which allows membership test, insertion, and deletion of elements in constant time [@BL93][^6]. 

We denote the *in-neighborhood* of a vertex $w$ by $N^-(w) := \{ v \in V \mid (v,w) \in E \}$. Furthermore, let $H_{i,w}$ be the running time of \[line:N-start,line:N-end\] in iteration $i$ of the for-loop in \[line:for-r\], and $R_{i,w}$ be the running time of \[line:compress\] in iteration $i$ of the for-loop in \[line:for-r\].  Then we can run \[alg:fpt-ipp\] in time of $O\left( \sum_{i=1}^{r-1} \sum_{w \in V} H_{i,w} + \sum_{i=1}^{r-1} \sum_{w \in V} R_{i,w} \right)$ operations over $\mathbb F$. Let $i \in [r-1]$ and $w \in V$. In the $i$-th iteration of the for-loop in \[line:for-r\], $|T[v,j]| \leq {r \choose j+1}$ for all $j < i$ and $v \in V$, since we used \[thm:eff-rep-fam\] in prior iterations.  Hence, $|\mathcal N_{w,i}| \leq {r \choose j+1} |N^-(w)|$ and $H_{i,w} \in O({r \choose j+1} |N^-(w)| \cdot r^\omega)$, because the independence test can be done via matrix multiplication.  Thus, $$\begin{aligned}
        &O\left( 
            \sum_{i=1}^{r-1} \sum_{w \in V} H_{i,w}
        \right)\\
        \iff &O\left( 
            \sum_{i=1}^{r-1} \sum_{w \in V} 
            |N^-(w)|{r \choose j+1} \cdot r^\omega
        \right)\\
        \iff &O\left( 
            \sum_{i=1}^{r-1} m {r \choose j+1} \cdot r^\omega
            mr^{3\omega} \sum_{i=1}^{r-1} {r \choose j+1} 
        \right)\\
        \iff &O\left( 
            2^{r+o(r)}m 
        \right). 
    \end{aligned}$$ Moreover, by \[thm:eff-rep-fam\], we have $$\begin{aligned}
        & O\left(   \sum_{i=1}^{r-1} \sum_{w \in V} R_{i,w} \right)\\
        \iff&   O\left( \sum_{i=1}^{r-1} \sum_{w \in V} 
        |N^-(w)| {r \choose i}{r \choose i+1}(i+1)^\omega +
        |N^-(w)| {r \choose i}{r \choose r-i-1}^{\omega-1}
        \right)\\
        \iff&   O\left( \sum_{i=1}^{r-1} \sum_{w \in V} 
        |N^-(w)| {r \choose i}{r \choose i+1}(i+1)^\omega +
        \sum_{i=1}^{r-1} \sum_{w \in V}
        |N^-(w)| {r \choose i}{r \choose r-i-1}^{\omega-1}
        \right)\\
        \iff&   O\left( \sum_{i=1}^{r-1}  
        m {r \choose i}{r \choose i+1}(i+1)^\omega +
        \sum_{i=1}^{r-1} 
        m {r \choose i}{r \choose r-i-1}^{\omega-1}
        \right)\\
            \iff&   O\left( rm (r+1)^{2\omega}  \sum_{i=1}^{r-1}  
        {r \choose i}{r \choose i+1} +
        rm
        \sum_{i=1}^{r-1} 
        {r \choose i}{r \choose r-i-1}^{\omega-1}
        \right)\\
                \iff&   O\left( rm (r+1)^{2\omega} 2^{2r} +
        rm
        2^{2r(\omega-1)}
        \right)\\
        \iff&   O\left(
            2^{2r+o(r)}m + 2^{\omega r + o(r)}m
        \right)\\
        \iff&   O\left(
            2^{\omega r+o(r)}m
        \right). 
        \end{aligned}$$

Thus, we can run \[alg:fpt-ipp\] in time of $O\left(2^{\omega r+o(r)}m\right) \in O\left(2^{\omega r}m\right)$ operations over $\mathbb F$.

Now, \[thm:fpt-ipp\] follows from \[lem:fpt-ipp-time,lem:fpt-ipp-correct\].  Finally, this equips us with the last piece towards the proof of \[thm:fpt-length\]. 

Let $I = ({\ensuremath{\mathcal{G}=(V, (E_i)_{i\in[{\ensuremath{\ell}}]})}\xspace},s,z,k,{\ensuremath{\Delta}})$ be an instance of [[<span style="font-variant:small-caps;">Short Restless Temporal $(s,z)$-Path</span>]{}]{}.  Note that \[alg:fpt-ipp\] is *parameter oblivious* thus does not know the length of shortest witness in advance.  Hence, start by $k=1$ and increase $k$ iteratively until the following procedure reports $I$ is a [*yes*]{}-instance or $k$ reaches $|V|$. In the latter case, we can conclude that $I$ is a [*no*]{}-instance. 

Now assume that $k$ is fixed.  To decide whether there is a witness of length $k$ of $I$ being a [*yes*]{}-instance, we first use \[lem:tpp-to-ipp\] to compute an instance $I' = (D,s,z,A_M)$ of [<span style="font-variant:small-caps;">Independent Path</span>]{} in $O(|{\ensuremath{\mathcal{G}}\xspace}|\cdot{\ensuremath{\Delta}})$ time, where we can compute one operation over the field $\mathbb F$ of $A_M$ in constant time and the matroid $M$ which is represented by $A_M$ is of rank $k+1$. Note that $I'$ is a [*yes*]{}-instance if and only if there is witness of length $k$ for $I$ being a [*yes*]{}-instance.  Second, we solve $I'$ by \[thm:fpt-ipp\] in $O(2^{\omega (k+1)}\cdot |{\ensuremath{\mathcal{G}}\xspace}|\cdot{\ensuremath{\Delta}})$ time. 

Thus, we have an overall running time of $O(5.181^k \cdot |{\ensuremath{\mathcal{G}}\xspace}|\cdot{\ensuremath{\Delta}})$.

FPT Results for Structural Paramerters
--------------------------------------

The fixed-parameter tractability result of \[thm:fpt-ipp\] has some interesting implications for structural parameterizations.  We can observe that any path of a graph can contain at most twice as many vertices as the vertex cover number of the graph (plus one), since we cannot visit two vertices outside of the vertex cover directly after another.  Essentially the same observation can be made in the temporal setting.  If we consider the vertex cover number $\text{vc}_\downarrow$ of the underlying graph, we can deduce that any restless temporal path can have length at most $2\text{vc}_\downarrow+1$. From a classification standpoint, we can improve this a little further by observing that the length of any restless temporal path is bounded by the length of any path of the underlying graph.  The length of a path in the underlying graph can be bounded by $2^{O(\text{td}_\downarrow)}$ [@ND12], where $\text{td}_\downarrow$ is the treedepth of the underlying graph.  Hence, we get the following observation. 

[<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}is fixed-parameter tractable when parameterized by the treedepth $\text{td}_\downarrow$ of the underlying graph. 

\[thm:probRestlessPath:W1hFVS\] implies that we presumably cannot hope to improve this result much, at least not from a classification standpoint. 

Conclusion {#sec:path:conclusion}
==========

In this work we have analyzed the (parameterized) computational complexity of [<span style="font-variant:small-caps;">Restless Temporal $(s,z)$-Path</span>]{}.  Other than its non-restless counterpart or the “walk-version”, this problem turns out to be computationally hard, even in quite restricted cases.  On the positive side, we give an FPT-algorithm to find short restless temporal paths and we could identify structural parameters of the underlying graph that allow for fixed-parameter algorithms. 

[^1]: Supported by the DFG, project FPTinP (NI 369/16). 

[^2]: Supported by the DFG, project MATE (NI 369/17). 

[^3]: This is a standard assumption in the *SIR-model* (Susceptible-Infected-Recovered), a canonical spreading model for diseases that give immunity upon recovery [@New18; @Bar16]. 

[^4]: For both algorithms, a representation of the original matroid must be given. 

[^5]: in the rank of the matroid

[^6]: The same tool set was also applied by @BTZ19.