---
abstract: 'Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable — in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are *robust* to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.'
author:
- Eugen Füchsle
- Hendrik Molter
- Rolf Niedermeier
- Malte Renken
bibliography:
- 'strings-long.bib'
- 'bibfile.bib'
title: 'Delay-Robust Routes in Temporal Graphs'
---

Introduction {#sec:intro}
============

Finding a path between two vertices in a graph is one of the most fundamental problems in graph algorithmics. In the rise in popularity of *temporal graphs* as a mathematical model @HotTopicHol15 [@HotTopicHS19; @HotTopicMic16; @HotTopicLVM18; @HotTopicCas+12], computing so-called *temporal paths* is one of the most important algorithmic problems in this area. Herein, a is a graph whose edges are present only at certain, known points in time. For our purposes, it is specified by a set $V$ of vertices and a set $E$ of time arcs, where each time arc $(v,w,t,\lambda) \in E$ consists of a *start vertex* $v$, an *end vertex* $w$, a *time label* $t$, and a traversal time $\lambda$; this means that there is a (direct) connection from $v$ to $w$ starting at time $t$ and arriving at time $t+\lambda$. Temporal graphs are prime models for many real-world networks: Social graphs, communication networks, and transportation networks are usually not static but vary over time.

The added dimension of time causes many aspects of connectivity to behave quite differently from static (i.e., non-temporal) graphs. In particular, the flow of goods or information through a temporal network has to respect time. More formally, it follows a *temporal walk* (or *path*, if every vertex is visited at most once), i.e., a sequence of time arcs $(v_i, w_i, t_i, \lambda_i)_{i=1}^{\ell}$ where $v_{i+1} = w_i$ and $t_{i+1} \geq t_i + \lambda_i$ for all $i < \ell$. While inheriting many properties of their static counterparts, temporal walks exhibit certain characteristics that add a new level of complexity to algorithmic problems centered around them. For example, temporal connectivity is not transitive: the existence of a temporal walk from vertex $u$ to $w$ and a temporal walk from $v$ to $w$ does not imply the existence of a temporal walk from $u$ to $w$. Furthermore, the temporal setting allows for several natural notions of an "optimal" temporal path @XuanFJ03.

As the finding of (optimal) temporal paths and walks constitutes the perhaps most important building block for (algorithmic) analysis of temporal networks, it has already been studied intensively @WuCKHHW16EffTempPath [@XuanFJ03]. However, the temporal setting allows to model further natural constraints on temporal walks and paths that do not have a counterpart in the static setting. For example, recently the study of the computational complexity of finding temporal walks and paths that are subject to some waiting time constraints has been initiated @TemporalPathsUnderWaitingTime [@BentertHNN20TempWalkWaitingTime].

In this work, we investigate another very natural yet still unstudied temporal path variant, namely so-called *delay-robust* temporal paths. Real-world networks are often not perfect: Scheduled connections may be canceled or delayed. This immediately brings up the natural issue of robustness. To the best of our knowledge, this issue has so far only been analyzed with respect to cancellations @Berman96Vuln, but not with respect to delays. We propose a model for delay-robust temporal paths and analyze natural structural and computational problems occurring in this context. Our main problem of interest is to determine whether there is a delay-robust temporal path between two vertices in a temporal graph.

<span>0.95</span> <span style="font-variant:small-caps;"><span><span style="font-variant:small-caps;">Delay-Robust Route</span></span></span>

\

<span>@lX@</span> **Input:** & A temporal graph $\mathcal{G} = (V,E)$, two vertices $s,z \in V$ and $x,\delta \in \mathbb{N}$.\
**Question:** & Is there an $x$-delay-robust route from $s$ to $z$ in ${\mathcal{G}}$?

It remains to say how *delay-robustness* is understood. Although different notions are conceivable, we consider a sequence of vertices (called a *route*) in a temporal graph to be *$x$-delay-robust*, if there is a temporal path visiting the vertices in this sequence even if up to $x$ time arcs are delayed by at most $\delta$. We give a formal definition in \[sec:prelims\].

This definition is motivated by the fact that changing the vertices may be costly for a number of reasons: storage or transhipment facilities may need to be newly allocated; if the new route passes through different jurisdictions, then new authorizations and documents have to be acquired; insurance policies might not cover alternative routes; the chosen packaging might no longer be adequate (e.g. when switching from rail to air transportation); or personnel might need to be moved. All these and many more issues are of much less concern when the chosen route can be kept and only the *schedule* has to be changed.

##### Related Work. {#related-work. .unnumbered}

Apart from the already mentioned work on finding temporal walks and paths, there has been extensive research on many other connectivity-related problems on temporal graphs @BussMNR20 [@Erlebach0K21; @KlobasMMNZ21]. Delays in temporal graphs have been considered as a modification operation to manipulate reachability sets @DBLP:conf/aaai/DeligkasP20 [@DBLP:journals/corr/MolTerRenkenZschoche]. The individual delay operation considered in the mentioned work delays a single time arc and is similar to our notion of delays. The deletion of time arcs @DBLP:journals/corr/MolTerRenkenZschoche [@EnrightMMZ19; @enright2018deleting], the deletion of vertices @staticExp1:journals/jcss/ZschocheFMN20 [@FluschnikMNRZ20; @staticExp2/DBLP:journals/jcss/KempeKK02], as well as reordering of time arcs @enright2021assigning have also been considered as temporal graph modification operations to manipulate the connectivity properties of the temporal graph. The corresponding computational problems in all mentioned work are NP-hard and can be also considered as computing "robustness measures" for the connectivity in temporal graphs.

In companion work @ForeseenUnforeseenDelays we investigate the related problem where we ask whether two vertices remain connected even if up to $x$ time arcs are delayed. Note that in this setting, the specific temporal path connecting the two vertices can visit different vertices for different delays. We show that this problem can be solved in polynomial time. We further investigate the problem variant where the delays occur dynamically during the "journey" from the start to the destination vertex. In this case the problem becomes PSPACE-complete if every vertex can be visited at most once and stays polynomial-time solvable, otherwise.

##### Our Contribution. {#our-contribution. .unnumbered}

We introduce the computational problem of finding routes that are robust under delays. We investigate its computational complexity with a focus on parameterized algorithms and hardness @DBLP:DowneyFellowsParamCompl [@DBLP:CyganEtAlParamAlgs].

We first give some structural results in \[ch:struct\_inv\], including that <span style="font-variant:small-caps;">Delay-Robust Path</span> is solvable in polynomial time if the underlying graph[^1] is a forest. In \[subsec:reduction\_framework\], we show that <span style="font-variant:small-caps;">Delay-Robust Path</span> is NP-hard even if the underlying graph has constant bandwidth, which implies that it also has constant treewidth. We further show that <span style="font-variant:small-caps;">Delay-Robust Path</span> is W\[1\]-hard when parameterized by the combination of the feedback vertex number of the underlying graph and the number of delays. In \[sec:algs\], we present our general algorithmic results where we explore how the polynomial-time algorithm for underlying forests can be generalized. We give a polynomial-time algorithm for the case where we have a constant number of delays. We further give two FPT algorithms: one for the underlying feedback edge set number as a parameter and one for the combination of the so-called *timed* feedback vertex number @TemporalPathsUnderWaitingTime and the number of delays as a parameter.

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

We abbreviate $\{1, 2, \dots, n\}$ as $[n]$ and $\{n, n+1, \dots, m\}$ as $[n, m]$. For any time arc $e = (v, w, t, \lambda_e)$, we denote the starting and ending vertices as $\operatorname{start}(e) = v$ an $\operatorname{end}(e) = w$, the time label as $\operatorname{t}(e) = t$, and the traversal time as $\operatorname{\lambda}(e) = \lambda_e$. Furthermore, for any vertex $v$, $\tau_v^+$ denotes the set of time steps where $v$ has outgoing time arcs, and $\tau_v^-$ denotes the time steps with incoming time arcs. We set $\tau_v := \tau_v^+ \cup \tau_v^-$.

Given a temporal graph ${\mathcal{G}}$, we denote by $T$ the maximum time label of all time arcs in ${\mathcal{G}}$. When removing all time information and directions from the time arcs of a temporal graph ${\mathcal{G}}= (V, E)$, the resulting (static & undirected) graph ${G_{\textnormal{u}}({\mathcal{G}})} = (V,E')$ with $E' = \{\{v,w\} \mid (v,w,t,\lambda) \in E\}$ is called the *underlying graph* of ${\mathcal{G}}$.

##### Delays.

We distinguish two different types of delays. Both are applied to a single time arc $e$ and delay it by a natural number $\delta$. A *starting delay* increases the time label $\operatorname{t}(e)$ by $\delta$ while a *traversal delay* increases the traversal time $\lambda(e)$ by $\delta$. In the example of a railway network, a starting delay would correspond to a delayed departure at a station whereas a traversal delay would describe a delay occurring on the way between two stations.

For a given set $D \subseteq E$ of *delayed arcs*, a sequence of time arcs $(v_i, w_i, t_i, \lambda_i)_{i=1}^\ell$ is called a $D$-starting-delayed temporal walk resp. a $D$-traversal-delayed temporal walk if it is a temporal walk in the temporal graph obtained from ${\mathcal{G}}$ by applying starting delays resp. traversal delays to all time arcs in $D$. (We omit $D$ as well as the type of delay when they are clear from context.) Note that a traversal-delayed temporal walk is always also a temporal walk in ${\mathcal{G}}$, which is not necessarily true for a starting-delayed temporal walk.

As an example consider the following temporal walk with edges labeled by $(\operatorname{t}(e), \operatorname{\lambda}(e))$:

\[every node/.style=vertex\] at (0,0) (a) <span>$a$</span>; (b) <span>$b$</span>; (c) <span>$c$</span>;

\(a) edge\[edge label=<span>$(1,1)$</span>\] (b) (b) edge\[edge label=<span>$(3,1)$</span>\] (c);

When delaying the first time arc by 1, i.e. when setting $\delta = 1$ and $D = \{(a, b, 1, 1)\}$, then this is also a starting-delayed as well as a traversal-delayed temporal walk: Due to the delay, the first time arc arrives in $b$ at time step $2+\delta=3$ which is no later than the departure of the second time arc. However, if we instead set $\delta = 2$ and $D = \{(a, b, 1, 1), (b, c, 3, 1)\}$, then it is still a starting-delayed temporal walk but no longer a traversal-delayed temporal walk, because the first time arc only reaches $b$ at time $4$.

We say a sequence $R$ of vertices forms a *(delayed) route* if there is a (delayed) temporal walk which *follows* $R$, that is, which visits exactly the vertices of $R$ in the given order. Generally, a temporal walk or route from vertex $s$ to vertex $z$ is also called a *temporal $(s,z)$-walk* or *$(s,z)$-route*. A *(delayed) temporal path* is a (delayed) temporal walk where no vertex is visited twice.

##### Robustness.

We say that a temporal route is *traversal-delay-robust* resp. *starting-delay-robust* for a given number $x$ of delays if it is a $D$-traversal-delayed resp. $D$-starting-delayed temporal route for all delay sets $D$ of size ${\left|D\right|} \leq x$. Of course, this also depends on the value of $\delta$. An example can be seen in \[fig:example\_drp\].

=\[circle, minimum size=16pt, draw, inner sep=1pt\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt\] at (0,0) (s) <span>$s$</span>; (a) <span>$a$</span>; (b) <span>$b$</span>; (c) <span>$c$</span>; (z) <span>$z$</span>;

\(s) edge node\[anchor=south,sloped\]<span>$\scriptstyle (3,1)$</span> (a); (a) edge node\[midway, anchor=north, sloped\]<span>$\scriptstyle (4,1)$</span> node\[midway, anchor=south, sloped\]<span>$\scriptstyle (8,1)$</span> (b); (b) edge node\[midway, anchor=south, sloped\]<span>$\scriptstyle (5,1)$</span> node\[midway, anchor=north, sloped\]<span>$\scriptstyle (9,1)$</span> (c); (c) edge node\[midway, anchor=south, sloped\]<span>$\scriptstyle (11,1)$</span> (z);

We now have all the ingredients for the formal definition of our main problem, <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>, as given in \[sec:intro\]. In this definition, we did not specify whether traversal- or starting-delay is used. The reason for that is that we will show in \[ch:struct\_inv\] that the distinction is meaningless because both problem variants are equivalent. In the meantime, however, we will refer to them as <span><span style="font-variant:small-caps;">TD-Delay-Robust Route</span></span> and <span><span style="font-variant:small-caps;">SD-Delay-Robust Route</span></span>.

Structural Results and Recognizing Robust Routes {#ch:struct_inv}
================================================

In this section, we derive some important properties of delay-robust routes.

Structural Results
------------------

We begin by investigating the distinction between walks and paths. Clearly, from any temporal walk one can obtain a temporal path by eliminating all circular subwalks. This leads to the following lemma, which holds for traversal as well as starting delays, and for all delay sizes $x$ and delay times $\delta$ and will come in handy later.

\[lemma:vwalk\_then\_vpath\] Let $s$ and $z$ be two vertices. If there is a delay-robust $(s,z)$-route, then there is a delay-robust $(s,z)$-route without repeated vertices.

If there is a delay-robust $(s,z)$-route $R = (v_i)_{i=1}^k$, then for each delay of size at most $x$ there is a delayed temporal walk traversing $v_1, v_2,\ldots, v_k$ in that order. Each of these delayed temporal walks can be turned into a delayed temporal walk by eliminating circular subwalks. All the delayed temporal paths obtained in this way follow the same sequence of vertices, making this sequence a delay-robust $(s,z)$-route without repeated vertices.

By virtue of \[lemma:vwalk\_then\_vpath\], we will subsequently assume routes to not contain repeated vertices.

Next, we turn towards proving the equivalence of <span><span style="font-variant:small-caps;">SD-Delay-Robust Route</span></span> and <span><span style="font-variant:small-caps;">TD-Delay-Robust Route</span></span>. We start with some important observations. The first one is that every traversal-delayed temporal walk is also a starting-delayed temporal walk.

\[lemma:td\_implies\_sd\] Let $P$ be a traversal-delayed temporal walk for some delay set $D$ and $\delta \in {\mathbb{N}}$. Then $P$ is also a starting-delayed temporal walk for $D$ and $\delta$.

Let $P = (v_i, w_i, t_i, \lambda_i)_{i=1}^\ell$. This means that $$t_i + \lambda_i + [e_i \in D] \cdot \delta \le t_{i+1}$$ for all $i \le \ell-1$, where $[e_i \in D] = \begin{cases} 1 & \text{if } e_i \in D \\ 0 & \text{otherwise} \end{cases}$ denotes the Iverson bracket. Thus $$t_i + \lambda_i + [e_i \in D] \cdot \delta \le t_{i+1} + [e_{i+1} \in D] \cdot \delta$$ which shows that $P$ is a starting-delayed temporal walk.

While the converse of \[lemma:td\_implies\_sd\] is generally not true, the following weaker statement holds.

\[lemma:minimal\_delay\_breaks\_starting\] Let $R$ be a route, $\delta \in {\mathbb{N}}$ and $D$ a minimal delay set such that $R$ is not a $D$-traversal-delayed route. Then $R$ is not a $D$-starting-delayed route either.

Suppose for contradiction that $R$ was a $D$-starting-delayed route. Then there is a $D$-starting-delayed temporal walk $P = (e_i)_{i=1}^\ell = (v_i, w_i, t_i, \lambda_i)_{i=1}^\ell$ that follows $R$, i.e., $$t_i + \lambda_i + [e_i \in D] \cdot \delta \le t_{i+1} + [e_{i+1} \in D] \cdot \delta$$ for all $i \leq \ell-1$. Since $R$ is not a traversal-delayed route, $P$ is not a traversal-delayed temporal path. Thus there exists an index $j \leq \ell-1$ with $$t_j + \lambda_j + [e_j \in D] \cdot \delta > t_{j+1}$$ and we may assume $j$ to be chosen maximally. This implies that $$t_{j+1} 
    <   t_j + \lambda_j + [e_j \in D] \cdot \delta
    \le t_{j+1} + [e_{j+1} \in D] \cdot \delta,$$ which in turn implies that $e_{j+1} \in D$. By maximality of $j$, $P' = (e_i)_{i=j+1}^\ell$ is a traversal-delayed temporal path. Thus, for any traversal-delayed temporal path $Q = (v_i, w_i, t'_i, \lambda'_i)_{i=1}^j$ following $(v_i)_{i=1}^{j+1}$, we must have $t'_j + \lambda'_j + [(v_j, w_j, t'_j, \lambda'_j) \in D]\cdot \delta > t_{j+1}$, for otherwise its concatenation with $P'$ would contradict the fact that $R$ is not a traversal-delayed route. Therefore, $R$ is also not a $D'$-traversal-delayed temporal vertex walk, where $D' = D \setminus \{e_{j+1}\}$. This contradicts the minimality of $D$.

Using \[lemma:td\_implies\_sd,lemma:minimal\_delay\_breaks\_starting\], we can now prove the following.

\[theorem:drp\_deltype\_equiv\] <span><span style="font-variant:small-caps;">TD-Delay-Robust Route</span></span> $=$ <span><span style="font-variant:small-caps;">SD-Delay-Robust Route</span></span>.

Let $\mathcal{G} = (V,E)$ be a temporal graph, $s,z \in V$ be a start and an end vertex, and $x,\delta \in {\mathbb{N}}$. If $({\mathcal{G}}, s, z, x, \delta)$ is a no-instance of <span><span style="font-variant:small-caps;">SD-Delay-Robust Route</span></span>, then for every $(s,z)$-route $R$, there exists a set $D$ of ${\left|D\right|} \leq x$ time arcs such that there is no $D$-starting-delayed temporal path following $R$. By \[lemma:td\_implies\_sd\], there is then also no $D$-traversal-delayed temporal path following $R$, thus $({\mathcal{G}}, s, z, x, \delta)$ is a no-instance of <span><span style="font-variant:small-caps;">TD-Delay-Robust Route</span></span>.

Conversely, if $({\mathcal{G}}, s, z, x, \delta)$ is a no-instance of <span><span style="font-variant:small-caps;">TD-Delay-Robust Route</span></span>, then for every $(s,z)$-route $R$ there exists a set $D$ of ${\left|D\right|} \leq x$ time arcs such that $R$ is no $D$-traversal-delayed route. We may assume $D$ to be minimal to that respect. Then \[lemma:minimal\_delay\_breaks\_starting\] gives us that $R$ is no $D$-starting-delayed route, making $({\mathcal{G}}, s, z, x, \delta)$ a no-instance of <span><span style="font-variant:small-caps;">SD-Delay-Robust Route</span></span>.

allows us now to drop the distinction between the two delay types and speak simply of <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>. For the remainder of this paper we will mostly work with traversal delays, for they are slightly easier to handle.

Recognizing Robust Routes {#subsec:drp_verification}
-------------------------

Since a route can be followed by an exponential number of different temporal walks, it is not immediately clear whether delay-robustness can be efficiently checked. The following theorem says that this is the case, and <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> is thus contained in <span><span class="nodecor">NP</span></span>.

\[thm:polyforest\] For any given $x, \delta \in {\mathbb{N}}$, one can determine in ${\mathcal{O}}(nmx^2 + m \log m)$ time whether a given route $R$ in a temporal graph ${\mathcal{G}}$ is $x$-delay-robust, where $n$ is the number of vertices of $R$ and $m$ is the number of time arcs connecting consecutive vertices of $R$.

also gives us a polynomial-time algorithm to solve <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> on temporal graphs with underlying forest: As any vertex pair $(s, z)$ is connected by at most one route, we only need to test the delay robustness of that route.

In the remainder of this section, we will prove \[thm:polyforest\]. The basic idea is that a route is delay-robust for a worst-case delay if and only if it is delay-robust for all delays. This worst-case delay can be computed in polynomial time using a dynamic program.

First, we introduce the term *earliest arrival time* for a given route. A route $R = (v_i)_{i=1}^k$ requires that there is at least one temporal path following $R$. The *earliest arrival time* is then the arrival time of the temporal path that arrives earliest. Formally, we define the earliest arrival time as follows. Let $\mathcal{P} = \{P_i\}_{i=1}^\ell$ be the set of temporal paths following $R$ with $P_i = (e^{(i)}_1, e^{(i)}_2, \ldots, e^{(i)}_{k-1})$. The *earliest arrival time* of $R$ then is defined as the earliest arrival time of any temporal path in $\mathcal{P}$, i.e., as $ \min \left\{ t(e^{(i)}_{k-1}) + \lambda(e^{(i)}_{k-1}) {\;\middle\vert\;}i \leq \ell \right\} $. Analogously, if $R = (v_i)_{i=1}^k$ is a delayed route for the delay set $D\subseteq E$ and delay time $\delta \in {\mathbb{N}}$, and if $\mathcal{P}$ as above is the set of delayed temporal paths following $R$, then the *earliest delayed arrival time* of $R$ is $\min \left\{  t(e^{(i)}_{k-1}) + \lambda(e^{(i)}_{k-1}) + [e^{(i)}_{k-1} \in D] \cdot \delta {\;\middle\vert\;}i \leq \ell \right\} $.

We then define the *worst-case arrival time* of a route $R = (v_i)_{i=1}^k$ for a given delay size $x$ and delay time $\delta$ as the maximum earliest delayed arrival time of $R$, taken over all delay sets $D$ with ${\left|D\right|} \leq x$. (If $R$ is not $x$-delay-robust, then we define the worst-case arrival time to be $\infty$.)

Now that we defined the worst-case arrival time, we show how to compute it. Let $R_j = (v_i)_{i=1}^j$ denote the prefix routes of $R$. The dynamic program computes table entries $A_{R_j}[y]$ iteratively for all $j \leq k$ and $y \leq x$, where $A_{R_j}[y]$ stores the worst-case arrival time of $R_j$ for $y$ delays.

We begin with the single-vertex route $R_1 = (v_1)$, setting $
    A_{R_1}[y] = 0
$ for all $y$ since the empty temporal path is always available to go from $v_1$ to $v_1$. Our goal is then to inductively compute $A_{R_j}$ from $A_{R_{j-1}}$.

Consider the situation where we want to get from $v$ to $w$ in a single step, starting at time $t$. Then the set of available time arcs is $
    E(v,w,t) = \{ (v,w,t',\lambda) \in E \mid t' \ge t \}
$. Suppose $E(v, w, t) = \{a_i\}_{i=1}^\ell$ where $\operatorname{t}(a_i) + \operatorname{\lambda}(a_i) \leq \operatorname{t}(a_{i+1}) + \operatorname{\lambda}(a_{i+1})$ for all $i$. Now if up to $y$ delays occur, then the latest time at which we will reach $w$ is $$\operatorname{\alpha}(v, w, t, y) := \min\{\operatorname{t}(a_1) + \operatorname{\lambda}(a_1) + \delta, \operatorname{t}(a_{y+1}) + \operatorname{\lambda}(a_{y+1})\}.$$ Here, the worst case occurs if $a_1$ through $a_y$ are all delayed.

Using this fact, we can now compute the table entries $A_{R_i}$ from $A_{R_{i-1}}$ as follows. $$\label{eq:table-recursion}
    A_{R_{i}}[y] = \max_{0\le y' \le y} \{ \operatorname{\alpha}(v_{i-1},v_i,A_{R_{i-1}}[y'],y-y') \}.$$ The idea here is that some number $y' \leq y$ of delays will occur between $v_{i-1}$ and $v_i$, while the other $y-y'$ delays can occur somewhere along $R_{i-1}$.

It remains to formally prove that $A_{R}[x]$ contains the solution to the <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> instance (\[lemma:drw-table-correct\]) and that it can be computed in the specified time (\[lemma:drp\_verif\_running\_time\]).

\[lemma:drw-table-correct\] Let ${\mathcal{G}}= (V,E)$ be a temporal graph, $R = (v_i)_{i=1}^k$ a route, and $j, y, \delta \in {\mathbb{N}}$. Then $A_{R_j}[y]$ as defined above is the worst-case arrival time of $R_j = (v_i)_{i=1}^j$ for up to $y$ delays. In particular, $R_j$ is delay-robust for $y$ delays if and only if $A_{R_j}[y] < \infty$.

We will prove this by induction. The base case $i=1$ is clear as mentioned above.

For the induction step, suppose that the statement holds for $j-1$. Let $t$ be the worst-case arrival time of $R_j$ and $D$ a delay set of size ${\left|D\right|} \leq y$ for which this delayed arrival time is attained. Define $y'$ to be the number of delays in $D$ that occur along $R_{j-1}$ and $t'$ as the delayed arrival time of $R_{j-1}$ for $D$.

We may assume $D'$ to be a delay set causing the worst-case arrival time of $R_{j-1}$ for up to $y'$ delays, because otherwise we could replace $D'$ with such a set $\tilde{D}$: Clearly, the earliest delayed arrival time of $R_j$ for the delay set $\tilde{D} \cup (D \setminus D')$ must be at least that for the delay set $D$.

Due to this, we know by induction hypothesis that $t'= A_{R_{j-1}}[y']$. Therefore $t = \operatorname{\alpha}(v_{j-1}, v_j, t', y - y') = \operatorname{\alpha}(v_{j-1}, v_j, A_{R_{j-1}}[y'], y - y') \leq A_{R_j}[y]$ by definition of $\operatorname{\alpha}$. But we also have $\operatorname{\alpha}(v_{j-1}, v_j, A_{R_{j-1}}[y'], y - y') \geq A_{R_j}[y]$ or else $D$ would not cause the worst-case arrival time. This proves the desired equality.

The running time of the dynamic program is as follows.

\[lemma:drp\_verif\_running\_time\] Let ${\mathcal{G}}$ be a temporal graph, $R = (v_i)_{i=1}^n$ be a route, and $x, \delta \in {\mathbb{N}}$. The dynamic program to compute $A_{R}[x]$ can be executed in ${\mathcal{O}}(nmx^2 + m \log m)$ time where $m$ is the number of time arcs connecting consecutive vertices of $R$.

We may assume that ${\mathcal{G}}=(V,E)$ contains no vertices outside of $R$, thus $n = {\left|V\right|}$ and $m = {\left|E\right|}$. First, the time arcs are sorted with respect to the arrival time in ${\mathcal{O}}(m \log m)$ time.

For the computation of $a(v,w,t,y)$ we need to filter all time arcs from $v$ to $w$ that start at time $t$ or later, obtaining $E(v,w,t)$ (in already sorted order). This can be done in ${\mathcal{O}}(m)$ time. Afterwards, we can compute $\operatorname{\alpha}(v,w,t,y)$ in ${\mathcal{O}}(y)$ time. Thus, ${\mathcal{O}}(m)$ time is needed overall to compute $a(v,w,t,y)$.

For the computation of a single table entry $A_{R_i}[y]$, the value of $a(v_{i-1},v_i,A_{R_{i-1}}[y'],y-y')$ is computed for all $y' \leq y$. This is done for all $i \leq n$ and $y \leq x$.

Hence, the overall running time is $
    {\mathcal{O}}(n m x^2 + m \log m)
    $.

Now \[thm:polyforest\] follows directly from \[lemma:drw-table-correct\] and \[lemma:drp\_verif\_running\_time\].

A Reduction Framework for <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> {#subsec:reduction_framework}
=======================================================================================================

In this section, we investigate the computational hardness of <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> with a particular attention to parameterized hardness with respect to "distance to forest" parameters. The goal is to lay out the ground for potential generalization of the algorithm presented in \[subsec:drp\_verification\]. We introduce a new problem <span><span style="font-variant:small-caps;">Multi-Colored Monotone SAT</span></span> in \[sec:mpcsat\] and design a polynomial-time reduction to <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>. We will use this as an intermediate problem for reductions from <span style="font-variant:small-caps;">3-SAT</span> and <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span> in \[subsec:applications\] to show <span><span class="nodecor">NP</span></span>-hardness and parameterized hardness results.

<span><span style="font-variant:small-caps;">Multi-Colored Monotone SAT</span></span> {#sec:mpcsat}
-------------------------------------------------------------------------------------

The problem <span><span style="font-variant:small-caps;">Multi-Colored Monotone SAT</span></span> is a <span style="font-variant:small-caps;">Satisfiability</span> variant where the variables are partitioned into "color classes" and only one variable from each color may be set to true. Furthermore, we do not make any assumptions on the Boolean formula other than that all variables appear non-negated. Formally, the we define the problem as follows.

<span>0.95</span> <span style="font-variant:small-caps;"><span><span style="font-variant:small-caps;">Multi-Colored Monotone SAT</span></span> (<span><span style="font-variant:small-caps;">MCMSAT</span></span>)</span>

\

<span>@lX@</span> **Input:** & Disjoint sets of variables $X_1, X_2, \ldots, X_n$ and a boolean formula $\Phi$ only consisting of positive literals and the operators $\wedge$ and $\vee$.\
**Question:** & Is there a satisfying truth assignment for $\Phi$ where exactly one variable from each $X_i$ for $i \in [n]$ is true?

We have the following theorem.

\[cor:poly\_red\_dj\_drp\] <span><span style="font-variant:small-caps;">MCMSAT</span></span> ${\le_{\textnormal{m}}^{\textnormal{poly}}}$ <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>.

We describe the reduction behind \[cor:poly\_red\_dj\_drp\] first, and subsequently prove its correctness in a sequence of lemmas.

\[t\] =\[circle, minimum size=16pt, draw, inner sep=1pt\] =\[draw=black\]

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0,0) (s1) <span>$s_1$</span>;

(x1) <span>$x_{1,1}^{(1)}$</span>; (x2) <span>$x_{1,1}^{(2)}$</span>;

(xxx1) <span>$x_{1,2}^{(1)}$</span>; (xxx2) <span>$x_{1,2}^{(2)}$</span>;

(xx1) <span>$x_{1,3}^{(1)}$</span>; (xx2) <span>$x_{1,3}^{(2)}$</span>; (s2) <span>$s_2$</span>;

(s1) edge node\[pos=0.4, anchor=south, rotate=35\]<span>$\scriptstyle 1$</span> (x1); (s1) edge node\[pos=0.4, anchor=south\]<span>$\scriptstyle 2$</span> (xxx1); (s1) edge node\[pos=0.4, anchor=north, rotate=-35\]<span>$\scriptstyle 3$</span> (xx1);

(x1) edge node\[anchor=south\]<span>$\scriptstyle 1, 6$</span> (x2); (xxx1) edge node\[anchor=south\]<span>$\scriptstyle 2, 5$</span> (xxx2); (xx1) edge node\[anchor=north\]<span>$\scriptstyle 3, 4$</span> (xx2);

(x2) edge node\[anchor=south, sloped\]<span>$\scriptstyle 1, 6, 7$</span> (s2); (xxx2) edge node\[anchor=south, \]<span>$\scriptstyle 2, 5, 7$</span> (s2); (xx2) edge node\[anchor=north, sloped\]<span>$\scriptstyle 3, 4, 7$</span> (s2);

(y1) <span>$x_{2,1}^{(1)}$</span>; (y2) <span>$x_{2,1}^{(2)}$</span>;

(yy1) <span>$x_{2,2}^{(1)}$</span>; (yy2) <span>$x_{2,2}^{(2)}$</span>; (s3) <span>$s_3$</span>;

(s2) edge node\[pos=0.4, anchor=south, sloped\]<span>$\scriptstyle 8$</span> (y1); (s2) edge node\[pos=0.4, anchor=north, sloped\]<span>$\scriptstyle 9$</span> (yy1);

(y1) edge node\[anchor=south\]<span>$\scriptstyle 8, 13$</span> (y2); (yy1) edge node\[anchor=north\]<span>$\scriptstyle 9, 12$</span> (yy2);

(y2) edge node\[anchor=south, sloped\]<span>$\scriptstyle 8, 13, 14$</span> (s3); (yy2) edge node\[anchor=north, sloped\]<span>$\scriptstyle 9, 12, 14$</span> (s3);

(z1) <span>$x_{3,1}^{(1)}$</span>; (z2) <span>$x_{3,1}^{(2)}$</span>;

(zz1) <span>$x_{3,2}^{(1)}$</span>; (zz2) <span>$x_{3,2}^{(2)}$</span>; (s4) <span>$s_4$</span>;

(s3) edge node\[pos=0.4, anchor=south, sloped\]<span>$\scriptstyle 15$</span> (z1); (s3) edge node\[pos=0.4, anchor=north, sloped\]<span>$\scriptstyle 16$</span> (zz1);

(z1) edge node\[anchor=south\]<span>$\scriptstyle 15, 20$</span> (z2); (zz1) edge node\[anchor=north\]<span>$\scriptstyle 16, 19$</span> (zz2);

(z2) edge node\[anchor=south, sloped\]<span>$\scriptstyle 15, 20, 21$</span> (s4); (zz2) edge node\[anchor=north, sloped\]<span>$\scriptstyle 16, 19, 21$</span> (s4);

(xnext) ; (xxnext) ; (s4) edge (xnext); (s4) edge (xxnext);

at (0,0) (a) ;

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0,0) (z0) <span>$s_4$</span>;

(y11) ; (y12) ; (z11) ; (z12) ; (z13) ;

(x11) at (\[shift=(<span>2ex,10ex</span>)\]y12) ; (x12) at (\[shift=(<span>-2ex,10ex</span>)\]z12) ;

(i1) ;

(a11) ; (a12) ;

(b11) ; (b12) ;

(z1) <span>$f_1$</span>;

(z0) edge node\[anchor=south, color=black, sloped\]<span>$\scriptstyle 1, 6$</span> (x11); (x11) edge node\[anchor=south, color=black\]<span>$\scriptstyle 1, 6$</span> (x12); (x12) edge node\[anchor=south, color=black, sloped\]<span>$\scriptstyle 1, 6$</span> (i1);

(z0) edge node\[anchor=north, color=black, sloped\]<span>$\scriptstyle 2, 5$</span> (y11); (y11) edge node\[anchor=north, color=black\]<span>$\scriptstyle 2, 5$</span> (y12); (y12) edge node\[anchor=north, color=black\]<span>$\scriptstyle 2, 5$</span> (z11);

(z11) edge node\[anchor=north, color=black\]<span>$\scriptstyle 8, 13$</span> (z12); (z12) edge node\[anchor=north, color=black\]<span>$\scriptstyle 8, 13$</span> (z13); (z13) edge node\[anchor=north, color=black, sloped\]<span>$\scriptstyle 8, 13$</span> (i1);

(i1) edge node\[anchor=south, color=black, sloped\]<span>$\scriptstyle 9, 12$</span> (a11); (a11) edge node\[anchor=south, color=black\]<span>$\scriptstyle 9, 12$</span> (a12); (a12) edge node\[anchor=south, color=black, sloped\]<span>$\scriptstyle 9, 12$</span> (z1);

(i1) edge node\[anchor=north, color=black, sloped\]<span>$\scriptstyle 15, 20$</span>(b11); (b11) edge node\[anchor=north, color=black\]<span>$\scriptstyle 15, 20$</span>(b12); (b12) edge node\[anchor=north, color=black, sloped\]<span>$\scriptstyle 15, 20$</span>(z1);

(xprev) ; (xxprev) ;

(xprev) edge (z0); (xxprev) edge (z0);

(xnext) ; (xxnext) ;

(z1) edge (xnext); (z1) edge (xxnext);

at (0,0) (a) ;

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0,0) (zm) <span>$f_1$</span>;

(x2a) <span>$f_{2,1}^{(a)}$</span>; (xx2a) <span>$f_{2,2}^{(a)}$</span>; (x2b) <span>$f_{2,1}^{(b)}$</span>; (xx2b) <span>$f_{2,2}^{(b)}$</span>;

(f2) <span>$f_2$</span>;

(x3a) <span>$f_{3,1}^{(a)}$</span>; (xx3a) <span>$f_{3,2}^{(a)}$</span>; (x3b) <span>$f_{3,1}^{(b)}$</span>; (xx3b) <span>$f_{3,2}^{(b)}$</span>;

(f3) <span>$f_3$</span>;

(zm) edge node\[anchor=south, sloped\]<span>$\scriptstyle 8, 13$</span> (x2a); (zm) edge node\[anchor=north, sloped\]<span>$\scriptstyle 9, 12$</span> (xx2a); (x2a) edge node\[anchor=south\]<span>$\scriptstyle 8, 13$</span> (x2b); (xx2a) edge node\[anchor=north\]<span>$\scriptstyle 9, 12$</span> (xx2b); (x2b) edge node\[anchor=south, sloped\]<span>$\scriptstyle 8, 13$</span> (f2); (xx2b) edge node\[anchor=north, sloped\]<span>$\scriptstyle 9, 12$</span> (f2);

(f2) edge node\[anchor=south, sloped\]<span>$\scriptstyle 15, 20$</span> (x3a); (f2) edge node\[anchor=north, sloped\]<span>$\scriptstyle 16, 19$</span> (xx3a); (x3a) edge node\[anchor=south\]<span>$\scriptstyle 15, 20$</span> (x3b); (xx3a) edge node\[anchor=north\]<span>$\scriptstyle 16, 19$</span> (xx3b); (x3b) edge node\[anchor=south, sloped\]<span>$\scriptstyle 15, 20$</span> (f3); (xx3b) edge node\[anchor=north, sloped\]<span>$\scriptstyle 16, 19$</span> (f3);

(xprev) ; (xxprev) ; (xprev) edge (zm); (xxprev) edge (zm);

Let $I = ((X_1, X_2, \ldots, X_n), \Phi)$ be an instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span>. We will construct a temporal graph ${\mathcal{G}}= (V, E)$ and an instance $I' = ({\mathcal{G}}, s,z, \delta, x)$ of <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> so that $I$ is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span> if and only if $I'$ is a yes-instance of ${\textsc{Delay-Robust Route}}{}$. All time arcs in ${\mathcal{G}}$ have a traversal time of 0. Thus, we abbreviate time arcs as $3$-tuples $(v,w,t)$. In figures we omit the traversal time and label arcs only with their time step.

Let $X_i = \{x_{i,1}, x_{i,2}, \ldots, x_{i, {\left|X_i\right|}}\}$ for all $i\in [n]$. Furthermore, let $m := \max_i {\left|X_i\right|}$ denote the largest cardinality of a variable set $X_i$. The temporal graph consists of chained *selection gadgets* for each variable set $X_i$, a recursively constructed *validation gadget* and chained *finalization gadgets* for each variable set $X_i$. The selection gadgets are used to select the variable from $X_i$ that is assigned to true, for each $i \in [n]$. Then the validation gadgets check whether the formula is satisfied under the selected truth assignment. If this is not the case, then a connection breaks at latest in the finalization gadgets and the target vertex can not be reached. The gadgets use an offset $o_i := (2m+1) \cdot (i-1)$. We set the delay time to $\delta = 1$ and the number of delays to $ x =2\cdot n-1$. \[fig:mcp\_drp\_all\_gadgets\] shows examples for all gadget types.

##### Selection Gadgets. {#selection-gadgets. .unnumbered}

The selection gadgets are used to select one variable $x_{i,a}$ from each set $X_i$. For each set $X_i$, we add a vertex $s_i$ to $V$ and one additional vertex $s_{n+1}$. For each set $X_i$ and each variable $x_{i,a} \in X_i$, we add the vertices $x_{i,a}^{(1)}$ and $x_{i,a}^{(2)}$ to $V$. Moreover, we add the following time arcs to $E$ so that there is one route from $s_i$ to $s_{i+1}$ for this variable $x_{i,a}$: $$s_i \xrightarrow{o_i+a} x_{i,a}^{(1)} \xrightarrow{o_i+a, o_{i+1}-a} x_{i,a}^{(2)} \xrightarrow{o_i+a, o_{i+1}-a, o_{i+1}} s_{i+1}$$ Taking this sub-route corresponds to setting the variable $x_{i,a}$ to true. Additionally, for each of the three underlying arcs we add a *dummy time arc* for each time step $t \in [o_{i+1}-1]$. If the sub-route $s_i \rightarrow x_{i,a}^{(1)} \rightarrow x_{i,a}^{(2)} \rightarrow s_{i+1}$ is chosen, then the worst-case arrival time from $s_1$ to $s_{i+1}$ is $o_i+a$ for $2\cdot i$ delays and $o_{i+1}-a = o_i + 2\cdot m +1 - a$ for $2\cdot i + 1$ delays. Any sub-route is a Pareto optimum: while one arrives earlier for $2\cdot i$ delays, another arrives earlier for $2\cdot i + 1$ delays. We will give a formal proof in \[lemma:selection\_gadgets\_arr\_time\]. An example for chained selection gadgets can be seen in \[fig:mcp\_drp\_sel\_gadget\].

##### Validation Gadgets. {#validation-gadgets. .unnumbered}

The validation gadgets are used to check whether the formula $\Phi$ is satisfied under the selected truth assignment. We will add a fresh vertex $f_1$ to $V$ which is the start of the validation gadgets. The validation gadget for $\Phi$ will be constructed with $s_{n+1}$ as a start vertex and $f_1$ as an end vertex. Given a start vertex $v$ and an end vertex $w$, we can recursively construct the validation gadget for a formula $\Phi$ in the following way:

1.  $\Phi = x_{i,a}$ is a single positive literal.

    We add two fresh vertices $\ell_{i,a}^{(1)}$ and $\ell_{i,a}^{(2)}$ to $V$. We add the following time arcs, so that there is a connection from $v$ to $w$: $$v \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(1)} \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(2)} \xrightarrow{o_i + a, o_{i+1} - a} w$$ Additionally for all three underlying arcs we add a *dummy time arc* for each time step $t \in [o_{n+1}-1] \setminus [o_i, o_{i+1}-1]$. We call this constructed part of the validation gadget a *literal gadget*. If the variable $x_{i,a}$ has been selected in the selection gadgets, then traversing this literal gadget does not affect the worst-case arrival time with respect to the number of delays. However, if $x_{i,a}$ has not been selected there is a delay that breaks the connection at latest in the finalization gadgets.

2.  $\Phi = \Phi_1 \wedge \Phi_2 \wedge \ldots \wedge \Phi_k$ is a conjunction of $k$ sub-formulae.

    We add a fresh vertex $c_i$ to $V$ for all $i \in [k-1]$. Then the validation gadgets for all sub-formulae $\Phi_i$ are constructed, with $c_{i-1}$ as the start and $c_{i}$ as the end vertex, where $c_{0} = v$ and $c_{k} = w$. Thus, the gadgets for the sub-formulae are connected in a row, and to traverse the temporal graph from $v$ to $w$ all gadgets for the sub-formulae have to be traversed.

3.  $\Phi = \Phi_1 \vee \Phi_2 \vee \ldots \vee \Phi_k$ is a disjunction of $k$ sub-formulae.

    We construct the validation gadgets for all sub-formulae $\Phi_i$ with $v$ as the start and $w$ as the end vertex. Thus, the gadgets for the sub-formulae are connected in parallel, and to traverse the temporal graph from $v$ to $w$ one gadget for a sub-formulae has to be traversed.

An example for a valid gadget can be seen in \[fig:mcp\_drp\_val\_gadget\].

##### Finalization Gadgets. {#finalization-gadgets. .unnumbered}

The finalization gadgets are similar to the selection gadgets for all sets $X_2$ to $X_n$. For each variable set $X_i$ for $i \in [2,n]$ we add a vertex $f_i$ to $V$. For each variable $x_{i,a} \in X_i$ we add the vertices $f_{i,a}^{(1)}$ and $f_{i,a}^{(2)}$ to $V$ and add the following time arcs: $$f_{i-1} \xrightarrow{o_i + a, o_{i+1}-a} f_{i,a}^{(1)} \xrightarrow{o_i + a, o_{i+1}-a} f_{i,a}^{(2)} \xrightarrow{o_i + a, o_{i+1}-a} f_i$$ Again for all three underlying arcs and each time step $t \in [o_{n+1}-1] \setminus [o_i, o_{i+1}-1]$ we add a dummy time arc. An example for finalization gadgets can be seen in \[fig:mcp\_drp\_final\_gadget\].

The start and end vertices for our <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>-instance are $s_1$ and $f_n$, respectively.

It remains to prove that the constructed <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> instance is equivalent to the given <span><span style="font-variant:small-caps;">Multi-Colored Monotone SAT</span></span> instance. To this end we will first show that the worst-case arrival time in $s_{n+1}$ (after traversing all selection gadgets) for $2 \cdot (i - 1)$ delays and $2 \cdot (i - 1) + 1$ delays is only affected by the path taken in the $i$-th selection gadget.

\[lemma:selection\_gadgets\_arr\_time\] Let $P$ be a route from $s_1$ to $s_{n+1}$. If the vertices $x_{i,a}^{(1)}$ and $x_{i,a}^{(2)}$ are traversed in $P$, then the worst-case arrival time in $s_{n+1}$ is $o_i + a$ for $2\cdot (i-1)$ delays and $o_{i+1} - a$ for $2\cdot (i-1) + 1$ delays.

We prove this by induction over the prefix-path from $s_1$ to $s_i$.

Since the path starts in $s_1$ no delays could have occurred. The starting time step is $o_1 = (2m + 1) \cdot(1-1) = 0$.

A path $P$ from $s_1$ to $s_{i}$ can be reached at time step $o_{i}$ with $2 \cdot (i-1)$ delays and $o_{i} + 1$ with $2 \cdot (i-1) + 1$ delays. For any $j < i$ the arrival times for $2 \cdot (j-1)$ and $2 \cdot (j-1)+1$ delays are $o_j + a$ and $o_{j+1}-a$ respectively depending on which vertices $x_{j,a}^{(1)}$ and $x_{j,a}^{(2)}$ are taken on the path $P$ in the $j$-th variable gadget.

First we show, that delaying a dummy time arc is never a strict worst-case. Considering the $i$-th selection gadget there are dummy time arcs for all time steps $t \in [o_{i}-1]$. Thus, they are only available if less than $2 \cdot (i-1)$ delays occurred in the previous selection gadgets since this leads to an arrival of at most $o_{j+1}-a \in [o_{i}-1]$ for any $j < i$ and $a \in [m]$.

*Case 1.* Assume there was a worst-case delay of size $2 \cdot (j-1)$ for some $j<i$. The worst-case arrival time in the $i$-th variable gadget is $o_j + a$ for some $a \in [m]$. Delaying the dummy time arc at $o_j + a$ will result in an arrival time at $o_j + a + 1$, however, the worst-case arrival time in the $i$-th selection gadget was already $o_{j+1}-a$ for $2 \cdot (j-1)+1$ delays which is at least as late since $o_{j+1}-a = o_j + 2m + 1 - a \ge o_j + a + 1$ for any $a \in [m]$.

*Case 2.* Assume there was a worst-case delay of size $2 \cdot (j-1) + 1$ for some $j<i$. The worst-case arrival time in the $i$-th variable gadget is $o_{j+1} - a$ for some $a \in [m]$. Delaying the dummy time arc at $o_{j+1} - a$ will result in an arrival time at $o_{j+1} - a + 1$, however, the worst-case arrival time in the $i$-th selection gadget was already at least $o_{j+1}$ for $2 \cdot (j-1)+1$ delays which is at least as late for any $a \in [m]$.

Thus, in order to have an affect on the arrival time with delays in the i-th variable gadget $2 \cdot (i-1)$ delays need to have occurred yielding an arrival time of $o_{i}$ so that no dummy time arcs are available. Note, that although a worst-case delay of size $2 \cdot (i-1) + 1$ leads to an arrival time of $o_i + 1$, the outgoing time arcs at $s_i$ are not before time $o_i+1$, and thus lead to an arrival at time $o_i+1$ also for $2 \cdot (i-1)$ delays in later vertices. Thus, we only need to consider a delay of size $2 \cdot (i-1)$. The following table shows how the arrival times for a worst-case delay when traversing the vertices that correspond to the variable $x_{i,a}$. Hence, the time arcs $$s_i \xrightarrow{o_i+a} x_{i,a}^{(1)} \xrightarrow{o_i+a,o_{i+1}-a} x_{i,a}^{(2)} \xrightarrow{o_i+a,o_{i+1}-a, o_{i+1}} s_{i+1}$$ are used. It can be easily seen that there are no strictly worse ones. Delayed arcs are marked in red (delays are already applied) and non delayed time arcs that are taken are marked green.

              \# Delays                                                                                                           Worst-Case Delay                                                                                                <span>Arrival Time</span>
  ---------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------
     <span>$2 \cdot (i-1)$</span>     $s_i \xrightarrow{{\color{green!50!black}o_i+a}} x_{i,a}^{(1)} \xrightarrow{{\color{green!50!black}o_i+a},o_{i+1}-a} x_{i,a}^{(2)} \xrightarrow{{\color{green!50!black}o_i+a},o_{i+1}-a,o_{i+1}} s_{i+1}$           $o_i + a$
   <span>$2 \cdot (i-1)$ + 1</span>       $s_i \xrightarrow{{\color{red}o_i+a+1}} x_{i,a}^{(1)} \xrightarrow{o_i+a,{\color{green!50!black}o_{i+1}-a}} x_{i,a}^{(2)} \xrightarrow{o_i+a,{\color{green!50!black}o_{i+1}-a},o_{i+1}} s_{i+1}$              $o_{i+1} - a$
       <span>$2 \cdot i$</span>                $s_i \xrightarrow{{\color{red}o_i+a+1}} x_{i,a}^{(1)} \xrightarrow{o_i+a,{\color{red}o_{i+1}-a+1}} x_{i,a}^{(2)} \xrightarrow{o_i+a,o_{i+1}-a,{\color{green!50!black}o_{i+1}}} s_{i+1}$                    $o_{i+1}$
     <span>$2 \cdot i + 1$</span>                  $s_i \xrightarrow{{\color{red}o_i+a+1}} x_{i,a}^{(1)} \xrightarrow{o_i+a,{\color{red}o_{i+1}-a+1}} x_{i,a}^{(2)} \xrightarrow{o_i+a,o_{i+1}-a,{\color{red}o_{i+1}+1}} s_{i+1}$                       $o_{i+1} + 1$

For the last $n$-th variable gadget if $2 \cdot (n-1)$ delays occurred there is only one delay remaining (since the number of allowed delays $x=2\cdot n-1$). Thus, if $x_{n,a}^{(1)}$ and $x_{n,a}^{(2)}$ are traversed, an arrival in $z_0$ for $2 \cdot (n-1)$ and $2 \cdot (n-1)+1$ delays is possible at time steps $o_n + a$ and $o_{n+1} - a$ respectively.

Additionally, we observe that if there is a satisfying assignment for $\Phi$, then there is a path through the validation gadgets that only traverses sub-gadgets corresponding to variables from that satisfying assignment:

\[obs:sat\_ass\_true\_lits\] Let there be a truth assignment where exactly one variable from each $X_i$ for all $i \in [n]$ is set to true. This assignment satisfies $\Phi$ if and only if there is a temporal path from $s_n$ to $f_1$ (through the validation gadgets) that only traverses validation sub-gadgets that belong to variables chosen in that assignment.

This directly follows from the construction of the validation gadgets and the semantics of a boolean formula: If $\Phi$ is a single literal, then the validation gadget is a single literal gadget. If $\Phi$ is a conjunction, then the sub-gadgets for the sub-formulae are connected in a row, so that all need to be traversed. If $\Phi$ is a disjunction, then the sub-gadgets for the sub-formulae are connected in parallel, so that one of them needs to be traversed.

Now we will look at the literal gadgets that are traversed after the selection gadgets. If only literal gadgets are traversed that correspond to variables selected in the selection gadgets, then it will not affect the worst-case arrival time with respect to the number of delays.

\[lemma:arrival\_time\_unchanged\_sat\_lit\] Let $P$ be a route from $s_1$ to any vertex $z$ of any literal gadget. Suppose for every literal gadget $$v \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(1)} \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(2)} \xrightarrow{o_i + a, o_{i+1} - a} w$$ traversed by $P$ that $P$ also traverses the vertex $x_{i,a}$ corresponding to that literal. Then, for any number of delays, the worst-case arrival times of $P$ at $z$ and at $s_{n+1}$ are equal.

Assume $v, \ell_{i,a}^{(1)}, \ell_{i,a}^{(2)}, w$ as above are the vertices of the last literal gadget traversed by $P$. Without loss of generality we assume $z = w$. By induction on the number of literal gadgets, we may assume that $P$ reaches $v$ and $s_{n+1}$ at the same time (for any number of delays). Thus, due to \[lemma:selection\_gadgets\_arr\_time\] the arrival time in $v$ is $o_j + a_j$ for $2 \cdot (j-1)$ delays and $o_{j+1} - a_j$ for $2 \cdot (j-1) + 1$ delays for all $j \in [n]$ where $x_{j, a_j}$ is the selected variable from $X_j$, and $a_i = a$ due to our assumption.

For all delays not of size $2 \cdot (i-1)$ or $2 \cdot (i-1) + 1$ there is a dummy time arc in the literal gadget for the arrival time in $v$, and thus a delay is not a strict worst-case. (see proof of \[lemma:selection\_gadgets\_arr\_time\]).

For a delay of size $2 \cdot (i-1)$ the arrival time in $v$ is $o_i + a$. By applying one additional delay in the literal gadget the arrival in $\ell_{i,a}^{(1)}$ is delayed to $o_i + a + 1$ enforcing to take the time arc at $o_{i+1} - a$ to reach $\ell_{i,a}^{(2)}$. However, this is exactly the worst-case arrival time in $v$ with $2 \cdot (i-1) + 1$ delays. Thus, if the additional delay occurred in the selection gadget, then the arrival time would be as late. By applying a second additional delay when taking the time arc at $o_{i+1} - a$ to reach $\ell_{i,a}^{(2)}$ one is enforced to take the next dummy time arc $\ell_{i,a}^{(2)} \xrightarrow{o_{i+1}} w$ to reach $w$. However, this is even a better arriving time compared to the case that $2 \cdot i$ delays have occurred in the selection gadgets.

For a delay of size $2 \cdot (i-1) + 1$ the arrival time in $v$ is $o_{i+1} - a$. By applying one additional delay in the literal gadget the arrival in $\ell_{i,a}^{(1)}$ is delayed to $o_{i+1} - a + 1$ enforcing to take the time arc at $o_{i+1}$ to reach $\ell_{i,a}^{(2)}$. However, this is even a better arriving time compared to the case that $2 \cdot i$ have occurred in the selection gadgets.

\[t\] =\[circle, minimum size=16pt, draw, inner sep=1pt\] =\[draw=black\]

This is enough to show that the <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>-instance and the <span><span style="font-variant:small-caps;">MCMSAT</span></span>-instance are equivalent:

\[lemma:mcpsat-reduction\] $((X_1, X_2, \ldots, X_n), \Phi)$ is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span> if and only if the instance $({\mathcal{G}}, s_1,f_n, \delta = 1, x=2\cdot n-1)$ is a yes-instance for <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>.

 

Let there be a truth assignment that satisfies $\Phi$, where exactly one variable from each $X_i$ for all $i \in [n]$ is set to true. Let $x_{i,a_i}$ be the variable chosen from $X_i$ in that satisfying assignment. We choose the route $P_s$ through the selection gadgets from $s_1$ to $s_{n+1}$ that goes through all $x_{i,a_i}^{(1)}$ and $x_{i,a_i}^{(2)}$. Now due to \[obs:sat\_ass\_true\_lits\] there is a temporal path $P_v$ that traverses the validation gadgets from $s_{n+1}$ to $f_1$ that only traverses literal gadgets of variables selected in the selection gadgets. Hence, $P_s \circ P_v$ is delay-robust and the arrival times with respect to the number of delays in $s_{n+1}$ are the same as in $f_{1}$ due to \[lemma:selection\_gadgets\_arr\_time\] and \[lemma:arrival\_time\_unchanged\_sat\_lit\]. Now for the finalization gadgets we choose the route $P_f$ going through the vertices $f_{i,a_i}^{(1)}$ and $f_{i,a_i}^{(2)}$ for all $i \in [2,n]$. It can be seen that the sub-paths in the finalization gadgets $$f_{i-1} \xrightarrow{o_i + a_i, o_{i+1}-a_i} f_{i,a_i}^{(1)} \xrightarrow{o_i + a_i, o_{i+1}-a_i} f_{i,a_i}^{(2)} \xrightarrow{o_i + a_i, o_{i+1}-a_i} f_i$$ are similar to the satisfied literal gadgets. Thus, the traversal of the finalization gadget does not worsen the arrival time with respect to the number of delays. Therefore, $P_s \circ P_v \circ P_f$ is a delay-robust route from $s_1$ to $f_n$ for any delay of size at most $2 \cdot n - 1$ and $\delta = 1$.

Assume there does not exist a truth assignment where exactly one variable from each $X_i$ for all $i \in [n]$ is set to true that satisfies $\Phi$. Thus, due to \[obs:sat\_ass\_true\_lits\] for any assignment all paths through the validation gadgets traverse at least one literal gadget corresponding to an unsatisfied literal. Therefore, for any path $P$ from $s_1$ to $f_1$ traversing the selection and validation gadgets there is an $i \in [n]$ so that $P$ traverses a literal gadget $$v \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(1)} \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(2)} \xrightarrow{o_i + a, o_{i+1} - a} w$$ while in the $i$-th selection gadget the vertices $s_i \rightarrow x_{i,b}^{(1)} \rightarrow x_{i,b}^{(2)} \rightarrow s_{i+1}$ are traversed with $a \ne b$. Without loss of generality let this be the first unsatisfied literal gadget. By doing a case distinction we can show, that with only $2 \cdot (i-1) + 1$ delays an arrival of at least $o_{i+1}$ in $w$ can be enforced.

If $a < b$, then due to \[lemma:selection\_gadgets\_arr\_time\] and \[lemma:arrival\_time\_unchanged\_sat\_lit\], there is a delay of size $2 \cdot (i-1)$ yielding an arrival time of $o_i + b$ in $v$. Since $a < b$ implies $o_i + a < o_i + b$ the time arc $v \xrightarrow{o_i + a} \ell_{i,a}^{(1)}$ cannot be taken. The next possible time arc is $v \xrightarrow{o_{i+1} - a} \ell_{i,a}^{(1)}$. By delaying that arc the arrival in $\ell_{i,a}^{(1)}$ is at $o_{i+1} - a$ and to reach the next vertices $\ell_{i,a}^{(2)}$ and $w$ the dummy time arc at $o_{i+1}$ needs to be taken. Note that the total number of delays used is $2 \cdot (i-1) + 1$.

If $a > b$, then due to \[lemma:selection\_gadgets\_arr\_time\] and \[lemma:arrival\_time\_unchanged\_sat\_lit\], there is a delay of size $2 \cdot (i-1) + 1$ yielding an arrival time of $o_{i+1} - b$ in $v$. Since $a > b$ implies $o_{i+1} - a < o_{i+1} - b$ none of the time arcs $v \xrightarrow{o_i + a, o_{i+1} - a} \ell_{i,a}^{(1)}$ can be taken. The next possible time arc is the dummy time arc at $o_{i+1}$ which leads to an arrival time of $o_{i+1}$ in $w$ using $v \xrightarrow{o_{i+1}} \ell_{i,a}^{(1)} \xrightarrow{o_{i+1}} \ell_{i,a}^{(2)} \xrightarrow{o_{i+1}} w$.

Note that there are no dummy time arcs for $o_{n+1}$. Thus, the connection breaks in the literal gadget if $i = n$. Since the arrival time in $w$ is $o_{i+1}$ for $2 \cdot (i-1) + 1$ delays, the arrival time in $f_{i}$ is at least $o_{i+1}$ for $2 \cdot (i-1) + 1$ delays. Now by applying 2 additional delays in the $(i+1)$-st finalization gadget $$f_{i} \xrightarrow{{\color{red}o_{i+1} + a \rightarrow o_{i+1} + a+1}} f_{i+1,a}^{(1)} \xrightarrow{{\color{gray}o_{i+1} + a}, {\color{red}o_{i+2}-a \rightarrow o_{i+2}-a+1}} f_{i+1,a}^{(2)} \xrightarrow{{\color{gray}o_{i+1} + a, o_{i+2}-a}, o_{i+2}} f_{i+1}$$ the arrival time in $f_{i+1}$ is $o_{i+2}$ with a total of $2 \cdot i + 1$ delays. (Red labels indicate a delay, gray labels cannot be taken due to a previous delay.) This can be repeated until the last finalization gadget where one arrives earliest at $o_n$ with $2\cdot(n-2)+1$ delays used, and thus two delays left. Similar as before two delays can be applied, but for the $n$-th finalization gadget there is no dummy time arc of time step $o_{n+1}$, and thus the connection breaks with a total of $2\cdot (n-1) + 1 = 2 \cdot n - 1$ delays. Hence, there is no delay-robust path from $s_1$ to $f_n$ with $2 \cdot n - 1$ delays and $\delta = 1$, and thus the instance is a no-instance.

An example how the delay breaks when an unsatisfied literal-gadget is traversed can be seen in \[fig:unsat\_lit\_red\_demo\]. We now show that the reduction can be performed in polynomial time.

\[lem:redptime\] Given an instance $((X_1, X_2, \ldots, X_n), \Phi)$ of <span><span style="font-variant:small-caps;">MCMSAT</span></span> with $m = \max_i {\left|X_i\right|}$ and $\ell$ the number of literals in $\Phi$, the temporal graph ${\mathcal{G}}$ can be constructed in polynomial time with respect to $n, m$ and $\ell$.

The graph ${\mathcal{G}}$ contains the ${\mathcal{O}}(n)$ vertices $s_1, s_2, \ldots, s_n$ and $f_2, f_3, \ldots, f_n$. For each $i \in [n]$ and $x_{i,a} \in X_i$ there are two additional vertices in the selection and finalization gadgets each resulting in ${\mathcal{O}}(n \cdot m)$ vertices. Furthermore, each variable $x_{i,a} \in X_i$ for each $i \in [n]$ introduces at most $3 \cdot o_{n+1} \in {\mathcal{O}}(n \cdot m)$ time arcs giving a total of ${\mathcal{O}}(n^2 \cdot m^2)$ time arcs. Each literal in $\Phi$ introduces at most four new vertices in ${\mathcal{G}}$ and at most $3 \cdot o_{n+1} \in {\mathcal{O}}(n \cdot m)$ time arcs. Thus, the validation gadget introduces ${\mathcal{O}}(\ell)$ vertices and ${\mathcal{O}}(\ell \cdot n \cdot m)$ time arcs. In total, ${\mathcal{G}}$ has ${\mathcal{O}}(\ell + n \cdot m)$ vertices and ${\mathcal{O}}(\ell \cdot n \cdot m + n^2 \cdot m^2)$ time arcs. The temporal graph can be constructed by iterating over the variables and clauses once.

Hence, we have constructed a valid polynomial-time reduction and \[cor:poly\_red\_dj\_drp\] follows from \[lemma:mcpsat-reduction,lem:redptime\].

Applications of the Framework {#subsec:applications}
-----------------------------

Next, we use our previous result that <span><span style="font-variant:small-caps;">MCMSAT</span></span> ${\le_{\textnormal{m}}^{\textnormal{poly}}}$ <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> (\[cor:poly\_red\_dj\_drp\]) to show that <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> is <span><span class="nodecor">NP</span></span>-complete even if the underlying graph has bandwidth 3. The *bandwidth* $\textnormal{bw}(G)$ of a graph $G$ is the smallest number $b$ such that the vertices of $G$ can be placed at distinct integer points along a line so that the length of the longest edge is $b$. The bandwidth of a graph upper-bounds both the graph's pathwidth and treewidth @sorgeWellerGraphHierarchy. Formally, we show the following result by using an appropriate polynomial-time reduction from the <span><span class="nodecor">NP</span></span>-complete <span><span style="font-variant:small-caps;">3-SAT</span></span> problem @Karp72NPComplete to <span><span style="font-variant:small-caps;">MCMSAT</span></span>.

\[theorem:drp\_paranp\] <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> is NP-complete for all fixed $\delta\ge 1$, maximum traversal times $\lambda_{\max}\ge 0$, and bandwidths of the underlying graph $\textnormal{bw}({G_{\textnormal{u}}({\mathcal{G}})})\ge 3$ .

Let $\Phi$ be an instance of <span><span style="font-variant:small-caps;">3-SAT</span></span> with the variables $x_1, x_2, \ldots, x_n$. We will construct an instance $((X_1, X_2, \ldots, X_n), \Phi')$ of <span><span style="font-variant:small-caps;">MCMSAT</span></span> that is a yes-instance if and only if $\Phi$ is a yes-instance of <span><span style="font-variant:small-caps;">3-SAT</span></span>. The construction is straightforward. Let $X_i = \{x_i, \bar{x}_i\}$ for all $i \in [n]$. Note, that in this case $\bar{x}_i$ is a variable and not a negative literal. Furthermore, $\Phi' = \Phi$, but any negative literal $\bar{x}_i$ from $\Phi$ corresponds to the variable $\bar{x}_i$, and thus is not negated in $\Phi'$. The formula $\Phi'$ only contains the operators $\wedge$ and $\vee$ since $\Phi$ is in conjunctive normal form. Hence, $\Phi'$ is a valid formula for the problem <span><span style="font-variant:small-caps;">MCMSAT</span></span>.

\[lemma:3sat\_to\_djpsat\] $\Phi$ is a yes-instance of <span><span style="font-variant:small-caps;">3-SAT</span></span> if and only if $((X_1, X_2, \ldots, X_n), \Phi')$ is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span>.

 

Assume $\Phi$ is a yes-instance of <span><span style="font-variant:small-caps;">3-SAT</span></span>. Hence, there is a truth assignment $\hat{x}_1, \hat{x}_2, \ldots, \hat{x}_n$ with $\hat{x}_i \in \{x_i, \bar{x}_i \}$ that satisfies $\Phi$. For <span><span style="font-variant:small-caps;">MCMSAT</span></span> exactly one variable from each set $X_i$ with $i \in n$ has to be set to true. If $\hat{x}_i = x_i$, then we set $x_i \in X_i$ to true, and thus $\bar{x}_i \in X_i$ is false. If $\hat{x}_i = \bar{x}_i$, then we set $\bar{x}_i \in X_i$ to true, and thus $x_i \in X_i$ is false. Hence, for any literal in $\Phi$ the corresponding positive literal in $\Phi'$ is evaluated to the same truth-value. This also implies that $\Phi$ and $\Phi'$ are evaluated to the same truth-value since the literals are linked by conjunctions and disjunctions in the same way. Since $\Phi$ is satisfied, the variable selection from the sets $X_i$ with $i \in [n]$ also satisfies $\Phi'$.

Assume $((X_1, X_2, \ldots, X_n), \Phi')$ is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span>. Thus, there is a truth assignment that sets exactly one variable from each set $X_i$ with $i \in [n]$ to true. Let $\hat{x}_i$ be the selected variable from $X_i$. We will also use this assignment for our <span><span style="font-variant:small-caps;">3-SAT</span></span>-instance: If $\hat{x}_i = x_i$, then we assign $x_i$ to true, otherwise to false. Hence, a positive literal in $\Phi$ is evaluated to true if and only if the corresponding literal in $\Phi$ is evaluated to true. This also implies that $\Phi'$ and $\Phi$ are evaluated to the same truth-value since the literals are linked by conjunctions and disjunctions in the same way. Since $\Phi'$ is satisfied under the selected variables the truth assignment also satisfies $\Phi$.

\[t\] =\[circle, minimum size=16pt, draw, inner sep=1pt\] =\[draw=black\]

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0.0, 0) (sel1s) ; at (2.7, 0) (sel1z) ; at (0.9, 0.5) (sel101) ; at (1.8, 0.5) (sel102) ; (sel1s) edge (sel101); (sel101) edge (sel102); (sel102) edge (sel1z); at (0.9, -0.5) (sel111) ; at (1.8, -0.5) (sel112) ; (sel1s) edge (sel111); (sel111) edge (sel112); (sel112) edge (sel1z); at (5.4, 0) (sel2z) ; at (3.6, 0.5) (sel201) ; at (4.5, 0.5) (sel202) ; (sel1z) edge (sel201); (sel201) edge (sel202); (sel202) edge (sel2z); at (3.6, -0.5) (sel211) ; at (4.5, -0.5) (sel212) ; (sel1z) edge (sel211); (sel211) edge (sel212); (sel212) edge (sel2z); at (7.2, 0) (sel3s) ; at (9.9, 0) (sel3z) ; at (8.1, 0.5) (sel301) ; at (9.0, 0.5) (sel302) ; (sel3s) edge (sel301); (sel301) edge (sel302); (sel302) edge (sel3z); at (8.1, -0.5) (sel311) ; at (9.0, -0.5) (sel312) ; (sel3s) edge (sel311); (sel311) edge (sel312); (sel312) edge (sel3z); (sel2z) – node\[auto=false\]<span>**…**</span> (sel3s); at (10.8, 0.5) (sel3zd0) ; (sel3z) edge (sel3zd0); at (10.8, 0.0) (sel3zd1) ; (sel3z) edge (sel3zd1); at (10.8, -0.5) (sel3zd2) ; (sel3z) edge (sel3zd2);

at (0,0) (a) ;

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0.0, 0) (val1s) ; at (2.7, 0) (val1z) ; at (0.9, 0.75) (val101) ; at (1.8, 0.75) (val102) ; (val1s) edge (val101); (val101) edge (val102); (val102) edge (val1z); at (0.9, 0.0) (val111) ; at (1.8, 0.0) (val112) ; (val1s) edge (val111); (val111) edge (val112); (val112) edge (val1z); at (0.9, -0.75) (val121) ; at (1.8, -0.75) (val122) ; (val1s) edge (val121); (val121) edge (val122); (val122) edge (val1z); at (5.4, 0) (val2z) ; at (3.6, 0.75) (val201) ; at (4.5, 0.75) (val202) ; (val1z) edge (val201); (val201) edge (val202); (val202) edge (val2z); at (3.6, 0.0) (val211) ; at (4.5, 0.0) (val212) ; (val1z) edge (val211); (val211) edge (val212); (val212) edge (val2z); at (3.6, -0.75) (val221) ; at (4.5, -0.75) (val222) ; (val1z) edge (val221); (val221) edge (val222); (val222) edge (val2z); at (7.2, 0) (val3s) ; at (9.9, 0) (val3z) ; at (8.1, 0.75) (val301) ; at (9.0, 0.75) (val302) ; (val3s) edge (val301); (val301) edge (val302); (val302) edge (val3z); at (8.1, 0.0) (val311) ; at (9.0, 0.0) (val312) ; (val3s) edge (val311); (val311) edge (val312); (val312) edge (val3z); at (8.1, -0.75) (val321) ; at (9.0, -0.75) (val322) ; (val3s) edge (val321); (val321) edge (val322); (val322) edge (val3z); (val2z) – node\[auto=false\]<span>**…**</span> (val3s); at (-0.9, 0.75) (val1sd0) ; (val1sd0) edge (val1s); at (-0.9, 0.0) (val1sd1) ; (val1sd1) edge (val1s); at (-0.9, -0.75) (val1sd2) ; (val1sd2) edge (val1s); at (10.8, 0.75) (val3zd0) ; (val3z) edge (val3zd0); at (10.8, 0.0) (val3zd1) ; (val3z) edge (val3zd1); at (10.8, -0.75) (val3zd2) ; (val3z) edge (val3zd2);

at (0,0) (a) ;

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0.0, 0) (fin1s) ; at (2.7, 0) (fin1z) ; at (0.9, 0.5) (fin101) ; at (1.8, 0.5) (fin102) ; (fin1s) edge (fin101); (fin101) edge (fin102); (fin102) edge (fin1z); at (0.9, -0.5) (fin111) ; at (1.8, -0.5) (fin112) ; (fin1s) edge (fin111); (fin111) edge (fin112); (fin112) edge (fin1z); at (5.4, 0) (fin2z) ; at (3.6, 0.5) (fin201) ; at (4.5, 0.5) (fin202) ; (fin1z) edge (fin201); (fin201) edge (fin202); (fin202) edge (fin2z); at (3.6, -0.5) (fin211) ; at (4.5, -0.5) (fin212) ; (fin1z) edge (fin211); (fin211) edge (fin212); (fin212) edge (fin2z); at (7.2, 0) (fin3s) ; at (9.9, 0) (fin3z) ; at (8.1, 0.5) (fin301) ; at (9.0, 0.5) (fin302) ; (fin3s) edge (fin301); (fin301) edge (fin302); (fin302) edge (fin3z); at (8.1, -0.5) (fin311) ; at (9.0, -0.5) (fin312) ; (fin3s) edge (fin311); (fin311) edge (fin312); (fin312) edge (fin3z); (fin2z) – node\[auto=false\]<span>**…**</span> (fin3s); at (-0.9, 0.5) (fin1sd0) ; (fin1sd0) edge (fin1s); at (-0.9, 0.0) (fin1sd1) ; (fin1sd1) edge (fin1s); at (-0.9, -0.5) (fin1sd2) ; (fin1sd2) edge (fin1s);

\[Proof of \[theorem:drp\_paranp\]\] We now obtain \[theorem:drp\_paranp\] from \[lemma:3sat\_to\_djpsat\], observing that the reduction can clearly be performed in polynomial time, and by taking a closer look at the <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>-instance resulting from the reductions. A <span><span style="font-variant:small-caps;">3-SAT</span></span>-instance $\Phi$ is reduced to a <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>-instance $({\mathcal{G}}, s_1, f_n, \delta = 1, 2\cdot n-1)$ (with <span><span style="font-variant:small-caps;">MCMSAT</span></span> as an intermediate problem). A visualization of the resulting temporal graph ${\mathcal{G}}$ can be seen in \[fig:3sat\_drp\_red\_graph\]. In each selection and finalization gadget there are two parallel paths starting and ending in the same vertex with two intermediate vertices for both parallel paths. The validation gadget consist of chained gadgets for each clause. For each clause gadget there are three parallel paths (one for each literal) starting and ending in the same vertex with two intermediate vertices per parallel path. Hence, the bandwidth of the underlying graph ${G_{\textnormal{u}}({\mathcal{G}})}$ is $3$. Furthermore, the delay $\delta = 1$ and the maximum traversal time $\lambda_{\max} = \max_\lambda \{(v,w,t, \lambda) \in E\} = 0$.

Next, we show <span><span class="nodecor">W\[1\]</span></span>-hardness of <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> for the feedback vertex set of the underlying graph, the length of a delay-robust temporal path, and the number of delays combined. To this end, we give a parameterized polynomial-time reduction from <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span> @MCC_W1hardness to <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>. Again we use <span><span style="font-variant:small-caps;">MCMSAT</span></span> as an intermediate problem and use \[cor:poly\_red\_dj\_drp\]. Formally, we show the following result.

\[theorem:drp\_w1hardness\] <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> is <span><span class="nodecor">W\[1\]</span></span>-hard with respect to $x + L + f$ where $x$ is the number of delays, $L$ is the length of a longest $s$-$z$ path in ${G_{\textnormal{u}}({\mathcal{G}})}$, and $f$ is the feedback vertex number of ${G_{\textnormal{u}}({\mathcal{G}})}$.

Given a $k$-partite graph (each partition of another color), <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span> asks whether there the graph contains clique of size $k$. <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span> is <span><span class="nodecor">W\[1\]</span></span>-hard when parameterized by the number of partitions $k$ @MCC_W1hardness.

<span>0.95</span> <span style="font-variant:small-caps;"><span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span></span>

\

<span>@lX@</span> **Input:** & A graph $G = (V,E)$ with $V = V_1 \uplus V_2 \uplus \ldots \uplus V_k$.\
**Question:** & Is there a set of vertices $C \subseteq V$ so that $\forall v,w \in C: v\ne w \Rightarrow \{v,w\} \in E$ and ${\left|C\right|} = k$?

Let $V_i = \{v_{i,1}, v_{i,2}, \ldots, v_{i, {\left|V_i\right|}}\}$. Furthermore, let $E_{i,j}$ denote the set of edges between the partitions $V_i$ and $V_j$. We construct a <span><span style="font-variant:small-caps;">MCMSAT</span></span>-instance $((X_1, X_2, \ldots, X_k), \Phi)$ that is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span> if and only if $G = (V_1 \uplus V_2 \uplus \ldots \uplus V_k, E)$ is a yes-instance of <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span>. We define $X_i = \{x_{(i,j)} \mid v_{i,j} \in V_i\}$ to have a variable for each vertex in the partition $V_i$. Setting a variable $x_{(i,j)}$ to true corresponds to selecting this vertex for the clique. (Note that <span><span style="font-variant:small-caps;">MCMSAT</span></span> asks for exactly one true variable in each set $X_i$ which ensures than only one vertex from each partition is selected.) Now we construct $\Phi$ to ensure that in each pair of different partitions the selected vertices in those partitions are connected by an edge: $$\Phi = \bigwedge_{1 \le i < j \le k} \left( \bigvee_{\{v_{i,a}, v_{j,b}\} \in E_{i,j}} x_{i,a} \wedge x_{j,b} \right)$$

\[lemma:mcc\_to\_djpsat\] $(G = (V_1 \uplus V_2 \uplus \ldots \uplus V_k, E))$ is a yes-instance of <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span> if and only if $((X_1, X_2, \ldots, X_k), \Phi)$ is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span>.

 

Assume $(G = (V_1 \uplus V_2 \uplus \ldots \uplus V_k, E))$ is a yes-instance of <span><span style="font-variant:small-caps;">Multi-Colored Clique</span></span>. This means that there is a subset of vertices $C \subseteq V$ with ${\left|C\right|} = k$ so that $\forall v,w \in C: v \ne w \implies \{v,w\} \in E$ holds. Since the partitions are pairwise disjoint and ${\left|C\right|} = k$ there is exactly one vertex in $C$ from each partition. Let this vertex be denoted as $v_{i,a_i}$ for each partition $V_i$. For the <span><span style="font-variant:small-caps;">MCMSAT</span></span>-instance we set the corresponding variable $x_{i,a_i}$ to true. It can be seen that $\Phi$ is satisfied. For all $1 \le i < j \le k,$ the disjunction $$\bigvee_{\{v_{i,a}, v_{j,b}\} \in E_{i,j}} x_{i,a} \wedge x_{j,b}$$ is satisfied, since there is an edge $\{v_{i,a}, v_{j,b}\} \in E_{i,j}$ (due to our assumption that we have a clique) and the corresponding variables $x_{i,a}$ and $x_{j,b}$ are both set to true.

Assume $((X_1, X_2, \ldots, X_k), \Phi)$ is a yes-instance of <span><span style="font-variant:small-caps;">MCMSAT</span></span>. Thus, there is a truth assignment that assigns exactly one variable from $X_i$ for $i \in [k]$ to true that satisfies $\Phi$. Let $x_{i,a}$ be the variable set to true in $X_i$. We select the corresponding vertex $v_{i,a}$ to be in a set $C$. Since there are $k$ true variables, we have ${\left|C\right|} = k$ and each vertex in $C$ from a different partition. Because $\Phi$ is satisfied for all $1 \le i < j \le k$ the disjunction $$\bigvee_{\{v_{i,a}, v_{j,b}\} \in E_{i,j}} x_{i,a} \wedge x_{j,b}$$ is satisfied. Hence, there exists one pair of variables $x_{i,a}$ and $x_{j,b}$ that are both true, and there is an edge $\{v_{i,a}, v_{j,b}\} \in E_{i,j}$ between the corresponding vertices. These vertices $v_{i,a}$ and $v_{j,b}$ are both in $C$. Thus, $C$ is a clique.

=\[circle, minimum size=16pt, draw, inner sep=1pt\] =\[draw=black\]

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0.0, 0) (sel1s) ; at (2.0999999999999996, 0) (sel1z) ; at (0.7, 1.0) (sel101) ; at (1.4, 1.0) (sel102) ; (sel1s) edge (sel101); (sel101) edge (sel102); (sel102) edge (sel1z); at (0.7, 0.5) (sel111) ; at (1.4, 0.5) (sel112) ; (sel1s) edge (sel111); (sel111) edge (sel112); (sel112) edge (sel1z); at (0.7, -0.5) (sel121) ; at (1.4, -0.5) (sel122) ; (sel1s) edge (sel121); (sel121) edge (sel122); (sel122) edge (sel1z); at (0.7, -1.0) (sel131) ; at (1.4, -1.0) (sel132) ; (sel1s) edge (sel131); (sel131) edge (sel132); (sel132) edge (sel1z); (sel1s) – node\[auto=false\]<span>**…**</span> (sel1z); at (4.199999999999999, 0) (sel2z) ; at (2.8, 1.0) (sel201) ; at (3.5, 1.0) (sel202) ; (sel1z) edge (sel201); (sel201) edge (sel202); (sel202) edge (sel2z); at (2.8, 0.5) (sel211) ; at (3.5, 0.5) (sel212) ; (sel1z) edge (sel211); (sel211) edge (sel212); (sel212) edge (sel2z); at (2.8, -0.5) (sel221) ; at (3.5, -0.5) (sel222) ; (sel1z) edge (sel221); (sel221) edge (sel222); (sel222) edge (sel2z); at (2.8, -1.0) (sel231) ; at (3.5, -1.0) (sel232) ; (sel1z) edge (sel231); (sel231) edge (sel232); (sel232) edge (sel2z); (sel1z) – node\[auto=false\]<span>**…**</span> (sel2z); at (5.6, 0) (sel3s) ; at (7.699999999999999, 0) (sel3z) ; at (6.3, 1.0) (sel301) ; at (7.0, 1.0) (sel302) ; (sel3s) edge (sel301); (sel301) edge (sel302); (sel302) edge (sel3z); at (6.3, 0.5) (sel311) ; at (7.0, 0.5) (sel312) ; (sel3s) edge (sel311); (sel311) edge (sel312); (sel312) edge (sel3z); at (6.3, -0.5) (sel321) ; at (7.0, -0.5) (sel322) ; (sel3s) edge (sel321); (sel321) edge (sel322); (sel322) edge (sel3z); at (6.3, -1.0) (sel331) ; at (7.0, -1.0) (sel332) ; (sel3s) edge (sel331); (sel331) edge (sel332); (sel332) edge (sel3z); (sel3s) – node\[auto=false\]<span>**…**</span> (sel3z); (sel2z) – node\[auto=false\]<span>**…**</span> (sel3s); at (8.399999999999999, 1.0) (sel3zd0) ; (sel3z) edge (sel3zd0); at (8.399999999999999, 0.5) (sel3zd1) ; (sel3z) edge (sel3zd1); at (8.399999999999999, -0.5) (sel3zd2) ; (sel3z) edge (sel3zd2); at (8.399999999999999, -1.0) (sel3zd3) ; (sel3z) edge (sel3zd3);

at (0,0) (a) ;

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0.0, 0) (val1s) ; at (4.199999999999999, 0) (val1z) ; at (0.7, 1.0) (val101) ; at (1.4, 1.0) (val102) ; at (2.0999999999999996, 1.0) (val103) ; at (2.8, 1.0) (val104) ; at (3.5, 1.0) (val105) ; (val1s) edge (val101); (val101) edge (val102); (val102) edge (val103); (val103) edge (val104); (val104) edge (val105); (val105) edge (val1z); at (0.7, 0.5) (val111) ; at (1.4, 0.5) (val112) ; at (2.0999999999999996, 0.5) (val113) ; at (2.8, 0.5) (val114) ; at (3.5, 0.5) (val115) ; (val1s) edge (val111); (val111) edge (val112); (val112) edge (val113); (val113) edge (val114); (val114) edge (val115); (val115) edge (val1z); at (0.7, -0.5) (val121) ; at (1.4, -0.5) (val122) ; at (2.0999999999999996, -0.5) (val123) ; at (2.8, -0.5) (val124) ; at (3.5, -0.5) (val125) ; (val1s) edge (val121); (val121) edge (val122); (val122) edge (val123); (val123) edge (val124); (val124) edge (val125); (val125) edge (val1z); at (0.7, -1.0) (val131) ; at (1.4, -1.0) (val132) ; at (2.0999999999999996, -1.0) (val133) ; at (2.8, -1.0) (val134) ; at (3.5, -1.0) (val135) ; (val1s) edge (val131); (val131) edge (val132); (val132) edge (val133); (val133) edge (val134); (val134) edge (val135); (val135) edge (val1z); (val1s) – node\[auto=false\]<span>**…**</span> (val1z); at (5.6, 0) (sel3s) ; at (9.799999999999999, 0) (sel3z) ; at (6.3, 1.0) (sel301) ; at (7.0, 1.0) (sel302) ; at (7.699999999999999, 1.0) (sel303) ; at (8.399999999999999, 1.0) (sel304) ; at (9.1, 1.0) (sel305) ; (sel3s) edge (sel301); (sel301) edge (sel302); (sel302) edge (sel303); (sel303) edge (sel304); (sel304) edge (sel305); (sel305) edge (sel3z); at (6.3, 0.5) (sel311) ; at (7.0, 0.5) (sel312) ; at (7.699999999999999, 0.5) (sel313) ; at (8.399999999999999, 0.5) (sel314) ; at (9.1, 0.5) (sel315) ; (sel3s) edge (sel311); (sel311) edge (sel312); (sel312) edge (sel313); (sel313) edge (sel314); (sel314) edge (sel315); (sel315) edge (sel3z); at (6.3, -0.5) (sel321) ; at (7.0, -0.5) (sel322) ; at (7.699999999999999, -0.5) (sel323) ; at (8.399999999999999, -0.5) (sel324) ; at (9.1, -0.5) (sel325) ; (sel3s) edge (sel321); (sel321) edge (sel322); (sel322) edge (sel323); (sel323) edge (sel324); (sel324) edge (sel325); (sel325) edge (sel3z); at (6.3, -1.0) (sel331) ; at (7.0, -1.0) (sel332) ; at (7.699999999999999, -1.0) (sel333) ; at (8.399999999999999, -1.0) (sel334) ; at (9.1, -1.0) (sel335) ; (sel3s) edge (sel331); (sel331) edge (sel332); (sel332) edge (sel333); (sel333) edge (sel334); (sel334) edge (sel335); (sel335) edge (sel3z); (sel3s) – node\[auto=false\]<span>**…**</span> (sel3z); (val1z) – node\[auto=false\]<span>**…**</span> (sel3s); at (-0.7, 1.0) (val1sd0) ; (val1sd0) edge (val1s); at (-0.7, 0.5) (val1sd1) ; (val1sd1) edge (val1s); at (-0.7, -0.5) (val1sd2) ; (val1sd2) edge (val1s); at (-0.7, -1.0) (val1sd3) ; (val1sd3) edge (val1s); at (10.5, 1.0) (sel3zd0) ; (sel3z) edge (sel3zd0); at (10.5, 0.5) (sel3zd1) ; (sel3z) edge (sel3zd1); at (10.5, -0.5) (sel3zd2) ; (sel3z) edge (sel3zd2); at (10.5, -1.0) (sel3zd3) ; (sel3z) edge (sel3zd3);

at (0,0) (a) ;

\[b\]

\[auto, &gt;=stealth',shorten &lt;=1pt, shorten &gt;=1pt, state/.style=<span>alter, scale=0.75, draw, minimum size=8cm</span>\] =\[draw=black,-&gt;,shorten &lt;=1.5pt, shorten &gt;=1.5pt\]

at (0.0, 0) (fin1s) ; at (2.0999999999999996, 0) (fin1z) ; at (0.7, 1.0) (fin101) ; at (1.4, 1.0) (fin102) ; (fin1s) edge (fin101); (fin101) edge (fin102); (fin102) edge (fin1z); at (0.7, 0.5) (fin111) ; at (1.4, 0.5) (fin112) ; (fin1s) edge (fin111); (fin111) edge (fin112); (fin112) edge (fin1z); at (0.7, -0.5) (fin121) ; at (1.4, -0.5) (fin122) ; (fin1s) edge (fin121); (fin121) edge (fin122); (fin122) edge (fin1z); at (0.7, -1.0) (fin131) ; at (1.4, -1.0) (fin132) ; (fin1s) edge (fin131); (fin131) edge (fin132); (fin132) edge (fin1z); (fin1s) – node\[auto=false\]<span>**…**</span> (fin1z); at (4.199999999999999, 0) (fin2z) ; at (2.8, 1.0) (fin201) ; at (3.5, 1.0) (fin202) ; (fin1z) edge (fin201); (fin201) edge (fin202); (fin202) edge (fin2z); at (2.8, 0.5) (fin211) ; at (3.5, 0.5) (fin212) ; (fin1z) edge (fin211); (fin211) edge (fin212); (fin212) edge (fin2z); at (2.8, -0.5) (fin221) ; at (3.5, -0.5) (fin222) ; (fin1z) edge (fin221); (fin221) edge (fin222); (fin222) edge (fin2z); at (2.8, -1.0) (fin231) ; at (3.5, -1.0) (fin232) ; (fin1z) edge (fin231); (fin231) edge (fin232); (fin232) edge (fin2z); (fin1z) – node\[auto=false\]<span>**…**</span> (fin2z); at (5.6, 0) (fin3s) ; at (7.699999999999999, 0) (fin3z) ; at (6.3, 1.0) (fin301) ; at (7.0, 1.0) (fin302) ; (fin3s) edge (fin301); (fin301) edge (fin302); (fin302) edge (fin3z); at (6.3, 0.5) (fin311) ; at (7.0, 0.5) (fin312) ; (fin3s) edge (fin311); (fin311) edge (fin312); (fin312) edge (fin3z); at (6.3, -0.5) (fin321) ; at (7.0, -0.5) (fin322) ; (fin3s) edge (fin321); (fin321) edge (fin322); (fin322) edge (fin3z); at (6.3, -1.0) (fin331) ; at (7.0, -1.0) (fin332) ; (fin3s) edge (fin331); (fin331) edge (fin332); (fin332) edge (fin3z); (fin3s) – node\[auto=false\]<span>**…**</span> (fin3z); (fin2z) – node\[auto=false\]<span>**…**</span> (fin3s); at (-0.7, 1.0) (fin1sd0) ; (fin1sd0) edge (fin1s); at (-0.7, 0.5) (fin1sd1) ; (fin1sd1) edge (fin1s); at (-0.7, -0.5) (fin1sd2) ; (fin1sd2) edge (fin1s); at (-0.7, -1.0) (fin1sd3) ; (fin1sd3) edge (fin1s);

\[Proof of \[theorem:drp\_w1hardness\]\] To obtain \[theorem:drp\_w1hardness\] from \[lemma:mcc\_to\_djpsat\] we will look at the <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>-instance $({\mathcal{G}}, s_1, f_k, \delta=1, 2\cdot k - 1)$ that results from the reduction. First, observe that the reduction can be performed in polynomial time. We can immediately see that the number of allowed delays $2\cdot k - 1$ is upper-bounded by a function depending only in $k$. The temporal graph ${\mathcal{G}}$ is visualized in \[fig:mcc\_drp\_red\_graph\]. In this figure a set of feedback vertices is highlighted in cyan. One can see that the number of cyan feedback vertices is $2\cdot k + \binom{k}{2} - 2$: For each of the $k$ selection gadgets and each of the $k-1$ finalization gadgets there is one cyan vertex. For each of the $\binom{k}{2}$ chained sub-gadgets in the validation gadget there is one cyan vertex plus one additional cyan vertex. Two vertices where double counted since the start and end of the validation gadget where already counted in the selection and finalization gadget respectively. Hence, the feedback vertex number is upper-bounded by a function in $k$. Furthermore, we can see that all possible paths from $s_1$ (green vertex) to $f_k$ (red vertex) have a fixed length of $3 \cdot (2k-1) + 6 \cdot \binom{k}{2}$ which is also upper-bounded by a function in $k$.

The presented hardness result show that we presumably cannot generalize \[thm:polyforest\] to an FPT-result for parameters such as the treewidth of the underlying graph or the feedback vertex number of the underlying graph.

Parameterized Algorithms {#sec:algs}
========================

In \[subsec:reduction\_framework\], we presented several hardness results. Here, we present our algorithmic results for general input graphs which can be seen as different ways to generalize \[thm:polyforest\]. We start with an XP-algorithm for the number of delays as a parameter and then present two FPT-algorithms for "distance to forest" parameters.

Number of Delays {#sec:drp_fpt_delay_tau}
----------------

In what follows, we present an algorithm similar to Dijkstra's algorithm @dijkstra1959note. Starting at the source vertex $s$, it finds all optimal temporal $(s,v)$-routes by expanding each optimum by one step per iteration. However, as we have seen in the polynomial-time reductions in \[subsec:reduction\_framework\], there can be many $(s,z)$-routes that are Pareto-optimal with respect to the arrival time for a given number of delays. We use the dynamic program from \[thm:polyforest\] to extend the paths by a single time arc. Our main result of this section is that <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> admits an <span><span class="nodecor">XP</span></span>-algorithm with respect to the number $x$ of delays. \[theorem:drp\_w1hardness\] implies that we presumably cannot improve this to an FPT result for this parameter. Formally, we show the following.

\[theorem:drp\_xp\_x\] <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> can be solved in $
    \mathcal{O}({\left|V\right|}^3 \cdot {\left|E\right|}^{2x} \cdot x^2)
    $ time, where $x$ is the number of allowed delays.

For each route, its *arrival time vector* $\vec{t} = (t_0, t_1, \ldots, t_x)$ is a vector of $x+1$ time steps where $t_y$ is the worst-case arrival time for $y$ delays. We define a partial order $\preceq$ to compare arrival time vectors. For $\vec{t} = (t_0, t_1, \ldots, t_x)$ and $\vec{t'} = (t'_0, t'_1, \ldots, t'_x)$, set $\vec{t} \preceq \vec{t'}$ if and only if $t_y \le t'_y$ for all $y \leq x$. This partial order can be used to decrease the set of prefix paths that need to be considered due to the following observation.

\[obs:preceq\_arrival\_time\] Let ${\mathcal{G}}= (V,E)$ be a temporal graph, let $s,v,z \in V$ be three vertices, and $P_1$ and $P_2$ be two delay-robust $(s,v)$-routes with the arrival time vectors $\vec{t}_1 \preceq \vec{t}_2$. If there is a delay-robust $(s,z)$-route $P$ so that $P = P_2 \circ P'$, then $P_1 \circ P'$ is also a delay-robust route. Additionally, if there is a delay-robust $(s,v)$-route, then there is one whose arrival time vector is minimal among all $(s,v)$-routes.

Since for any delay one can arrive earlier in vertex $v$ by using the route $P_1$ compared to $P_2$, replacing the prefix $P_2$ by $P_1$ still guarantees delay-robustness.

We define a table $A$ with entries for every vertex of ${\mathcal{G}}$. The table entry $A[v]$ contains a set of arrival time vectors for $(s,v)$-routes. We will only store vectors that are minimal with respect to $\preceq$, since we do not need to consider others due to \[obs:preceq\_arrival\_time\]. Thus, the set $A[v]$ will represent the Pareto front of routes from $s$ to $v$.

Furthermore, we define a priority queue $Q$ that contains tuples $(v,\vec{t})$ of vertices and arrival time vectors. The queue is sorted according by the arrival time vectors according to $\preceq$. The queue elements $(v, \vec{t})$ contain the prefix routes from where a search should be expanded.

We initialize the table $A$ as follows: $$A[v] = 
    \begin{cases}
        \{ (0, \ldots, 0) \}, & \text{if } v = s\\
        \emptyset, & \text{otherwise.}
    \end{cases}$$

The start vertex $s$ can always be reached through the empty path. For all other vertices there is initially no route stored. Furthermore, we initialize the queue $Q$ with the tuple $(s, (0, \ldots, 0))$.

To compute the table entries we repeatedly pop the first element $(v, \vec{t})$ from $Q$ and propagate possible delay-robust routes from there. If $(v, \vec{t})$ is in the queue, then this means that there is a delay-robust $(s,v)$-route $P$ with the arrival time vector $\vec{t}$.

Let $\text{next}_v := \{ w \mid (v,w,t,\lambda) \in V \}$ denote the set of vertices reachable from $v$ by a single time arc. For all $w \in \text{next}_v$, we compute the arrival time vector $\vec{t'} = (t'_0, t'_1, \dots, t'_x)$ of $P' = P \circ (w)$ using the dynamic program described in \[subsec:drp\_verification\]: The arrival time vector of $P'$ is simply the table row $A_{P'}$ and $P'$ is $y$-delay-robust if and only if $A_{P'}[y] < \infty$.

As an optimization, we can round up the arrival time entries to the next time step in $\tau_{w}^+$, i.e. replace $t'_y$ by $$\hat{t'_y} = \min_{t} \{ t \in \tau_{w}^+  \mid t \ge t'_y \}$$. This rounding does not change the delay-robustness of any route since no temporal walk can leave $w$ between time $t'_y$ and $\hat{t'_y}$.

If $P'$ is $x$-delay-robust, then we can add $\vec{t'}$ to the set $A[w]$, unless $A[w]$ already contains a smaller arrival time vector. We then delete all $\vec{t''}$ with $\vec{t'} \preceq \vec{t''}$ from $A[w]$ and also remove the corresponding elements $(w, \vec{t''})$ from the queue $Q$. Finally, we insert $(w,\vec{t'})$ into $Q$.

Once the queue $Q$ is empty, we have investigated all $x$-robust prefix routes that might eventually lead to $z$. There is then a delay-robust $(s,v)$-route if and only if $A[z] \neq \emptyset$.

To analyze the running time we need to count the number of items of the queue being processed.

\[lemma:drp\_fpt\_x\_time\] Let ${\left|\tau_{\max}^+\right|} = \max_{v \in V} {\left|\tau_{v}^+\right|}$ be the maximum number of distinct time steps, where a single vertex has outgoing time arcs. The algorithm has a running time of $$\mathcal{O}\left({\left|V\right|}^2 \cdot {\left|\tau_{\max}^+\right|}^x \cdot \left({\left|E\right|} \cdot x^2 + {\left|V\right|} \cdot {\left|\tau_{\max}^+\right|}^x \cdot x\right) + {\left|E\right|} \cdot \log {\left|E\right|}\right).$$

Since we round the arrival time up to the next largest time step, where a vertex has outgoing time arcs, the earliest arrival time for $x$ delays can be one of at most ${\left|\tau_{v}^+\right|} \le {\left|\tau_{\text{max}}^+\right|}$ distinct arrival times. Hence, for any vertex $v$, there are at most ${\left|\tau_{v}^+\right|}^x$ distinct arrival time vectors and therefore ${\left|A[v]\right|} \in \mathcal{O}({\left|\tau_{v}^+\right|}^x)$. Furthermore, ${\left|Q\right|} \in \mathcal{O}({\left|V\right|} \cdot {\left|\tau_{v}^+\right|}^x)$.

Given a delay-robust path $P = (s, \ldots, v)$ with arrival time vector $\vec{t}$, the single step computation whether for a successor vertex $w$ the path $P \circ (w)$ is delay-robust, is done the same way as in the verification algorithm in \[subsec:drp\_verification\]. Hence, the time arcs are first sorted with respect to the arrival time in $\mathcal{O}({\left|E\right|} \cdot \log {\left|E\right|})$ time. The single step computation itself takes $\mathcal{O}({\left|E\right|} \cdot x^2)$ time (see \[lemma:drp\_verif\_running\_time\]). This single step computation is done for all successor vertices of $v$, which are at most ${\left|V\right|}$ many. Having computed a delay-robust path $P \circ (w)$ with arrival time vector $\vec{t'}$ we need to check whether we can add it to $A[w]$ and the priority queue. To do so, all (at most ${\left|\tau_{\text{max}}^+\right|}^x$) entries in $A[w]$ are checked against $\vec{t'}$ which takes $\mathcal{O}({\left|\tau_{\text{max}}^+\right|}^x \cdot x)$ time. If the found path is a Pareto optimum, then it can be added to the priority queue and worse items can be removed in $\mathcal{O}({\left|V\right|} \cdot {\left|\tau_{\text{max}}^+\right|}^x \cdot x)$ time (if naively implemented as a linked list). Thus, for any pair $(v,\vec{t})$ popped from the priority queue the algorithm consumes $$\begin{aligned}
        & \mathcal{O}\left({\left|V\right|} \cdot \left({\left|E\right|} \cdot x^2 + {\left|\tau_{\text{max}}^+\right|}^x \cdot x + {\left|V\right|} \cdot {\left|\tau_{\text{max}}^+\right|}^x \cdot x\right)\right) \\
        ={}& \mathcal{O}\left({\left|V\right|} \cdot \left({\left|E\right|} \cdot x^2 + {\left|V\right|} \cdot {\left|\tau_{\text{max}}^+\right|}^x \cdot x\right)\right)
    \end{aligned}$$ time steps.

For any path $P = (s, \ldots, v)$ with arrival time vector $\vec{t}$ and a computed $P \circ (w)$ with arrival time vector $\vec{t'}$ we have $\vec{t} \preceq \vec{t'}$. Hence, the front elements of the priority queue are always Pareto optima and a total of at most ${\left|V\right|} \cdot {\left|\tau_{\text{max}}^+\right|}^x$ elements are processed in the single step routine.

This gives an overall running time of $$\mathcal{O}\left({\left|V\right|}^2 \cdot {\left|\tau_{\text{max}}^+\right|}^x \cdot \left({\left|E\right|} \cdot x^2 + {\left|V\right|} \cdot {\left|\tau_{\text{max}}^+\right|}^x \cdot x\right) + {\left|E\right|} \cdot\log {\left|E\right|}\right).$$

The correctness of the algorithm follows from \[lemma:drw-table-correct\] and \[obs:preceq\_arrival\_time\].

\[lem:XPcorrectness\] The described algorithm solves <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>.

Given a route $P = (s, \ldots, v)$, we compute for a successor vertex $w$ of $v$ whether the route $P \circ (w) = (s, \ldots, v, w)$ is delay-robust for any delay up to size $x$ and its associated arrival time vector. This is done by the dynamic program introduced in \[subsec:drp\_verification\] and its correctness is proven in \[lemma:drw-table-correct\]. This is done for all successor vertices of $v$. Any newly found delay-robust path is added to the priority queue $Q$, if there is no better path with respect to $\preceq$ and the same end vertex. Additionally, no item $(v,\vec{t})$ is removed from the queue without computing paths for the successor vertices of $v$, if there is no better path with respect to $\preceq$ and the end vertex $v$. Hence, all delay-robust routes from $s$ are found that are optimal with respect to $\preceq$. Due to \[obs:preceq\_arrival\_time\], this is enough to find out if there is a delay-robust path from vertex $s$ to any vertex $v$.

\[theorem:drp\_xp\_x\] now directly follows from \[lemma:drp\_fpt\_x\_time\] and \[lem:XPcorrectness\] together with the observation that ${\left|\tau_{\text{max}}^+\right|} \le {\left|E\right|}$.

Timed Feedback Vertex Number
----------------------------

In this section, we explore another way to generalize \[thm:polyforest\]. We present an FPT algorithm for the so-called *timed feedback vertex number* (introduced by Casteigts et al. @TemporalPathsUnderWaitingTime) and the number $x$ of delays combined. Intuitively, the timed feedback vertex number is the minimum number of "vertex appearances" that need to be removed from the temporal graph to turn its underlying graph into a forest. Formally, it is defined as follows.

Let ${\mathcal{G}}$ be a temporal graph and $X\subseteq V\times[T]$ a set of *vertex appearances*. Then we write ${\mathcal{G}}-X:= (V, E')$, where $E'=E\setminus \{(v,w,t,\lambda)\mid (v,t)\in
X \lor (w,t)\in X\}$. A *timed feedback vertex set* of ${\mathcal{G}}$ is a set $X\subseteq V\times[T]$ of vertex appearances such that ${G_{\textnormal{u}}({\mathcal{G}}-X)}$ is cycle-free. The *timed feedback vertex number* of a temporal graph ${\mathcal{G}}$ is the minimum cardinality of a timed feedback vertex set of ${\mathcal{G}}$.

\[thm:tfvn\] <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> can be solved in $2^{{\mathcal{O}}(x f \log f)} \cdot ({\left|V\right|} + {\left|E\right|})^{{\mathcal{O}}(1)}$ time, where $f$ is the timed feedback vertex number of the underlying graph.

In the following, we give a description of the main steps of the algorithm we use to obtain the above result. The algorithm follows a simple "guess and check"-approach.

1.  Compute a minimum timed feedback vertex set $X$ of the input graph using an algorithm provided by Casteigts et al. @TemporalPathsUnderWaitingTime.

2.  Let $\hat{X}=\{v\mid (v,t)\in X\}$. Iterate over all partitions $\hat{X}_0\uplus\hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3=\hat{X}$ of $\hat{X}$. We distinguish two types of neighbors of a vertex. A neighbor connected by a time arc that is preserved in ${\mathcal{G}}- X$ is called a "forest neighbor", while other neighbors are called "feedback neighbors". Intuitively, in this step we guess for each vertex whether its predecessor resp. successor in the route is a feedback neighbor or a forest neighbor, leading to the following four cases:

    -   The route does not contain $v$ or the predecessor and successor of $v$ in the route are forest neighbors of $v$ (then $v\in\hat{X}_0$),

    -   the predecessor of $v$ in the route is a forest neighbor $v$, and the successor of $v$ in the route is a feedback neighbor of $v$ (then $v\in\hat{X}_1$),

    -   the predecessor of $v$ in the route is a feedback neighbor $v$, and the successor of $v$ in the route is a forest neighbor of $v$ (then $v\in\hat{X}_2$), or

    -   the predecessor and successor of $v$ in the route are feedback neighbors of $v$ (then $v\in\hat{X}_3$).

3.  Iterate over all orders on $\hat{X}_1\cup\hat{X}_2\cup\hat{X}_3$. Intuitively, in this step we guess in which order the vertices appear in the route.

4.  Let ${\hat{T}}=\{t, t+\delta \mid \exists w\in V : (w,t)\in X\} \cup \{\infty\}$ be the *relevant* time steps. For each vertex $v \in \hat{X}_1\cup\hat{X}_2\cup\hat{X}_3$, iterate over all *delay profiles* $(t_1, t_2, \ldots, t_x)\in {\hat{T}}^{x}$. Intuitively, here we guess for each delay size $i$ the smallest relevant time $t_i$ which is at least the worst-case arrival time at $v$.

5.  Use \[thm:polyforest\] to find route segments that respect the guessed delay profiles between consecutive vertices in $\hat{X}_1\cup\hat{X}_2\cup\hat{X}_3$ and which can be combined to an $x$-delay-robust $(s,z)$-route.

We first give a more detailed description of the last step of the algorithm. Let ${\hat{T}}=\{t,t+\delta \mid \exists v\in V : (v,t)\in X\} \cup \{\infty\}$ be the set of relevant time steps. Let $\{v_1,v_2,\ldots, v_{f'}\}=\hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3$ be the order of the vertices of the current iteration and $\vec{v}_1,\vec{v}_2,\ldots, \vec{v}_{f'}\in {\hat{T}}^{x}$ the corresponding delay profiles. For a vertex $v\in \hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3$, the *delay profile* $\vec{v}=(t_1, t_2, \ldots, t_x)\in  {\hat{T}}^{x}$ specifies, for each delay size $i$, the earliest relevant time step $t_i$ that upper-bounds the worst-case arrival time at $v$.

Now we want to be able to check for every consecutive pair of vertices $v_i,v_{i+1}$ with $i\in[f'-1]$ whether there is a route connecting them that respects both of their delay profiles. To do this, we use a subroutine to solve the following problem:

Given an $(s,z)$-route $R$ and delay profiles $\vec{s}=(t^{(s)}_1, t^{(s)}_2, \ldots, t^{(s)}_{x})$, $\vec{z}=(t^{(z)}_1, t^{(z)}_2, \ldots, t^{(z)}_{x})$, is it true for all $j$ that $t_j$ is the smallest relevant time step which, for all $i \leq j$, upper-bounds the worst-case arrival time at $z$ for $j-i$ delays when starting at $s$ at time $t_i$?

It is easy to observe that this problem can be solved with $O(f^2)$ applications of \[thm:polyforest\]. From now on, let $\text{checkRoute}(R,\vec{s},\vec{z})\rightarrow \{\texttt{true},\texttt{false}\}$ denote a subroutine answering the above question.

Now we go back to our original problem of checking whether there is a route connecting the vertices in $\hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3$. For each $i \leq f' - 1$ there are four possible cases:

-   $v_i\in\hat{X}_1\cup\hat{X}_3$ and $v_{i+1}\in\hat{X}_1$: This means that the successor of $v_i$ is a feedback set neighbor and the predecessor of $v_{i+1}$ is a forest neighbor.

    Let $N :=\{v\mid \exists t, \lambda: (v_i,v,t,\lambda)\in E\wedge (v_i,t)\in X\}$. For each $u\in N$, there is a unique $(u, v_{i+1})$-route $R'$ in ${\mathcal{G}}- X$. Construct $R  = (v_i) \circ R'$ and check whether $\text{checkRoute}(R,\vec{v}_i,\vec{v}_{i+1})=\texttt{true}$.

-   $v_i\in\hat{X}_1\cup\hat{X}_3$ and $v_{i+1}\in\hat{X}_2\cup\hat{X}_3$: This means that the successor of $v_i$ is a feedback neighbor and the predecessor of $v_{i+1}$ is also a feedback neighbor.

    Let $N:=\{v\mid \exists t, \lambda: (v_i,v,t,\lambda)\in E\wedge (v_i,t)\in X\}$ and $N' :=\{v\mid \exists t, \lambda: (v,v_{i+1},t,\lambda)\in E\wedge (v_{i+1},t)\in X\}$. For each $(u,u')\in N \times N'$, there is a unique $(u,u')$-route $R'$ in ${\mathcal{G}}- X$. Set $R = (v_i) \circ R' \circ (v_{i+1})$ and check whether $\text{checkRoute}(R,\vec{v}_i,\vec{v}_{i+1})=\texttt{true}$.

-   $v_i\in\hat{X}_2$ and $v_{i+1}\in\hat{X}_1$: This means that the successor of $v_i$ is a forest neighbor and the predecessor of $v_{i+1}$ is also a forest neighbor.

    There is a unique $(v_i, v_{i+1})$-route $R$ in ${\mathcal{G}}- X$. We check whether $\text{checkRoute}(R,\vec{v}_i,\vec{v}_{i+1})=\texttt{true}$.

-   $v_i\in\hat{X}_2$ and $v_{i+1}\in\hat{X}_2\cup\hat{X}_3$: This means that the successor of $v_i$ is a forest neighbor and the predecessor of $v_{i+1}$ is a feedback neighbor.

    Let $N:=\{v\mid \exists t, \lambda: (v,v_{i+1},t,\lambda)\in E\wedge (v_{i+1},t)\in X\}$. For each $u \in N$, there is a unique $(v_i, u)$-route $R'$ in ${\mathcal{G}}- X$. Construct from this the route $R = R' \circ (v_{i+1})$. We check whether $\text{checkRoute}(R,\vec{v}_i,\vec{v}_{i+1})=\texttt{true}$.

Finally, we check (using $\text{checkRoute}$) whether there is a route from $s$ to $v_1$ that respects the delay profile of $v_1$ and whether there is a route from $v_{f'}$ to $z$ for the delay profile of $v_{f'}$.

If, for any choices of $v_1, \dots, v_{f'}$ and $\vec{v_1}, \dots, \vec{v_{f'}}$, all of the above checks succeed, then we have found a solution. Otherwise we conclude that there is no solution.

Next, we show that we obtain the claimed running time bound. We analyze the running time of each of the steps of the algorithm.

1.  Computing a minimum timed feedback vertex set takes $2^{{\mathcal{O}}(f)}\cdot(|V|+|E|)^{{\mathcal{O}}(1)}$ time @TemporalPathsUnderWaitingTime.

2.  There are ${\mathcal{O}}(4^f)$ partitions $\hat{X}_0\uplus\hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3=\hat{X}$ of $\hat{X}$.

3.  There are ${\mathcal{O}}(f!)$ possible orderings for $\hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3$.

4.  There are $f^{{\mathcal{O}}(x f)}$ delay profiles combinations for the vertices in $\hat{X}_1\uplus\hat{X}_2\uplus\hat{X}_3$ to consider.

5.  For each complete guessing step, the check in the last step of the algorithm can be performed in polynomial time.

It follows that we obtain the claimed running time bound.

Finally, we briefly sketch out why our algorithm is correct. To this end, observe that if the checking step of the algorithm succeeds for a given guess, then ${\mathcal{G}}$ contains an $x$-delay-robust $(s,z)$-route. For the other direction, assume that ${\mathcal{G}}$ contains an $x$-delay-robust $(s,z)$-route $R$. We guess which vertices of $\hat{X}$ are visited by $R$ and in which order. Furthermore, we guess the delay profiles for all vertices $v\in\hat{X}$ that are visited by $R$. Now we know that all checks must succeed, otherwise we obtain a contradiction to the existence of $R$.

Underlying Feedback Edge Number
-------------------------------

In this section, we show that <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> admits an <span><span class="nodecor">FPT</span></span>-algorithm with respect to the feedback edge number of the underlying graph. Given a (static) undirected graph $G = (V,E)$, a feedback edge set $F \subseteq E$ is a set of edges, so that $G-F$ is acyclic. The *feedback edge number* is the cardinality of a minimum feedback edge set of $G$. Formally, we show the following.

\[corr:drp\_fpt\_feedbackedge\] <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> can be solved in $2^{{\mathcal{O}}(f)} \cdot ({\left|V\right|} \cdot {\left|E\right|} \cdot x^2) + {\mathcal{O}}({\left|E\right|} \cdot \log {\left|E\right|})$ time, where $f$ is the feedback edge number of the underlying graph.

Casteigts et al. @TemporalPathsUnderWaitingTime designed an <span><span class="nodecor">FPT</span></span>-algorithm for the so-called <span style="font-variant:small-caps;">Restless Temporal Path</span> parameterized by the feedback edge number of the underlying graph. This algorithm can be applied to <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span> as well with minor modifications.

The <span><span class="nodecor">FPT</span></span>-algorithm as given by Casteigts et al. @TemporalPathsUnderWaitingTime consist of four steps (only the last step needs adaptation to our problem):

1.  Exhaustively remove vertices with degree $\le 1$ from ${G_{\textnormal{u}}({\mathcal{G}})}$ (except $s$ and $z$).

2.  Compute a minimum feedback edge set $F$ of ${G_{\textnormal{u}}({\mathcal{G}})}$. Let $f := {\left|F\right|}$.

3.  Let $V^{\ge 3}$ denote all vertices of ${G_{\textnormal{u}}({\mathcal{G}})}$ with degree at least three. Partition the forest ${G_{\textnormal{u}}({\mathcal{G}})} - F$ into a set of maximal paths $\mathcal{P}$ with endpoints in $F \cup V^{\ge 3} \cup \{s,z\}$, and intermediate vertices all of degree 2. It holds that ${\left|\mathcal{P}\right|} \in {\mathcal{O}}(f)$.

4.  Any $(s,z)$-route in $G$ can be formed with feedback edges $F$ and paths from $\mathcal{P}$. Enumerate all at most $2^{{\mathcal{O}}{(k)}}$ $(s,z)$-routes and check (using \[thm:polyforest\]) if any of them forms a $x$-delay-robust $(s,z)$-route.

Denote by $G = (V, E') = {G_{\textnormal{u}}({\mathcal{G}})}$ the underlying graph. Clearly it can be computed in ${\mathcal{O}}({\left|{\mathcal{G}}\right|})$ time. In step 1, vertices of degree $\le 1$ (except $s$ and $z$) can be removed safely, since they can never be part of an $(s,z)$-route. This step is possible in ${\mathcal{O}}(|V|)$ time. In step 2, the minimum feedback vertex set $F$ can be obtained by computing a spanning tree $S$ of $G$ in ${\mathcal{O}}({\left|G\right|})$ time, and taking $F = E' \setminus S$. A key observation that is used in step 3 is that ${\left|V^{\ge 3}\right|}$, the number of vertices of degree 3 and higher, in a graph without any vertex of degree 1 can be upper-bounded by $2\cdot f$ @BentertDKNN20BetweennessCentrality. Since $s$ and $z$ can have degree one and can not be removed from ${\mathcal{G}}$ the actual upper bound is $2\cdot f + 2$. (The deletion of a degree one vertex will lower the degree of exactly one other vertex in $G$, and thus the deletion will only decrease the cardinality of $V^{\ge 3}$ by at most one.) Thus, ${\left|F \cup V^{\ge 3} \cup \{s,z\}\right|} \in {\mathcal{O}}(f)$ which are the endpoints of the paths $\mathcal{P}$. Since ${G_{\textnormal{u}}({\mathcal{G}})} - F$ is a forest we have ${\left|\mathcal{P}\right|} \in {\mathcal{O}}(f)$. The feedback edges and the paths $\mathcal{P}$ can be used to build all $(s,z)$-paths of $G$. Hence, the number of possible $(s,z)$-paths is bounded through the number of subsets of $F$ and $\mathcal{P}$, which is itself in $2^{{\mathcal{O}}(f)}$. We can now test for any $(s,z)$-path in $G$ whether it forms a robust route by using the dynamic program from \[subsec:drp\_verification\]. This requires an initial sorting of all time arcs in ${\mathcal{O}}({\left|E\right|} \log {\left|E\right|})$ time, plus ${\mathcal{O}}({\left|V\right|} \cdot {\left|E\right|} \cdot x^2)$ time per path. This leads to an overall time complexity of $2^{{\mathcal{O}}(f)} \cdot {\left|V\right|} \cdot {\left|E\right|} \cdot x^2 + {\mathcal{O}}({\left|E\right|} \log {\left|E\right|})$.

Conclusion
==========

We modeled a naturally motivated path-finding problem taking into account delays by means of (algorithmic) temporal graph theory. For our central problem, <span><span style="font-variant:small-caps;">Delay-Robust Route</span></span>, we found computational hardness already for some tree-like underlying (static) graphs. While having provided a few encouraging parameterized tractability results, we leave plenty of room for further investigations into this direction. In particular, we left open what happens for the special case when the number of time labels per edge is bounded from above (in parameterized complexity terms, taking this as a parameter). Recall that our central hardness reduction needs many time labels. Moreover, the parameters vertex cover number or timed feedback vertex set number @TemporalPathsUnderWaitingTime (as a single parameter) deserve investigations as well. Rather from a modeling perspective, one might vary the basic problem by e.g. considering a *global* delay budget or other variations of the delay concept.

[^1]: The *underlying graph* of a temporal graph is the undirected static graph obtained by connecting all vertices that are connected by a time arc.

{'source': 'arXiv_out/2201'}