# Parameterized Restless Temporal Path

Justine Cauvi, Laurent Viennot

► To cite this version:

Justine Cauvi, Laurent Viennot. Parameterized Restless Temporal Path. FCT 2025 - 25th International Symposium on Fundamentals of Computation Theory, Sep 2025, Wroclaw, Poland. hal-05144137

HAL Id: hal-05144137

https://inria.hal.science/hal-05144137v1

Submitted on 7 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Parameterized Restless Temporal Path*

Justine Cauvi¹,² and Laurent Viennot¹

¹Inria, DI ENS, Paris, France

²École Normale Supérieure de Lyon, Lyon, France

July 4, 2025

**Abstract**

Recently, Bumpus and Meeks introduced a purely temporal parame-
ter, called vertex-interval-membership-width, which is promising for the
design of fixed-parameter tractable (FPT) algorithms for vertex reach-
ability problems in temporal graphs. We study this newly introduced
parameter for the problem of restless temporal paths, in which the wait-
ing time at each node is restricted. In this article, we prove that, in the
interval model, where arcs are present for entire time intervals, finding a
restless temporal path is NP-hard even if the vertex-interval-membership-
width is equal to three. We exhibit FPT algorithms for the point model,
where arcs are present at specific points in time, both with uniform delay
one and arbitrary positive delays. In the latter case, this comes with a
slight additional computational cost.

**Keywords:** Temporal graphs, restless temporal paths, parameterized algorithms, interval-membership-width

<footnote>*This work was supported by the French ANR projects ANR-22-CE48-0001 (TEM-POGRAL), ANR-24-CE48-4377 (GODASse) and ANR-23-PEIA-005 (REDEEM).</footnote>
# 1 Introduction

A static graph represents relationships (the edges) between entities (the nodes). However, in many real-world applications, those relationships are time-related. For instance, there is a bus at time $τ$ from stop A to stop B in a public transit network, Alice calls Bob from time $τ$ to $τ'$ in a phone call network or Alice follows Bob at time $τ$ in a social network. This kind of networks are modeled by temporal graphs. In a temporal graph, time information is associated to each edge, such as the appearance time, the delay (time it takes to traverse the edge). Depending on the application, different models can represent a temporal network [7, 15]. In the simplest model called point model here, each edge appears at given points in time [2, 9, 21]. In the more complex model called interval model here, edges are available for entire time intervals [5, 19]. From these models arise many classical problems that have been well studied [2, 5, 9, 13, 16, 20, 22]. Connectivity in this context is more naturally grasped by temporal walks, that is, walks where edges are traversed one after another in time. Thus, a prominent problem is to find a temporal path, which is a temporal walk in which each node is visited at most once [5, 27]. An interesting variant is to find a $\Delta$-restless temporal path (or walk) [4, 8]. In a $\Delta$-restless temporal path, the waiting time at a node cannot exceed a given value $\Delta$. This notion of path is related to the detection of a chain of infections from an individual to another in the SIR (Susceptible-Infected-Recovered) model [3, 17, 23]. In this model, an individual becomes immune upon recovery. The restricted waiting time in this case is the time before an individual becomes immune after infection. Another application of this problem is in the context of public transit networks, in which an individual does not want to wait at a stop for too long.

In the point model, Casteigts, Himmel, Molter and Zschoche [8] showed that deciding whether there is a restless temporal path from a node to another is NP-complete. This motivates the design of temporal parameters that bring tractability to the problem. Bumpus and Meeks [6] introduced a novel parameter called vertex-interval-membership-width which is promising for the design of fixed parameter tractable (FPT for short) algorithms for reachability problems in temporal graphs. Intuitively, it measures the maximum number of active nodes at a given time where a node is considered active during the full interval between the first appearance of one of its incident edges and the last such appearance. Despite the recent interest in this new parameter, no FPT algorithm for the restless temporal path problem has been proposed for it so far. This article presents such an algorithm.

## 1.1 Related Work

Casteigts, Himmel, Molter and Zschoche [8] showed several parameterized algorithms and hardness results on restless temporal path in the point model. Among others, they showed that it is fixed-parameter tractable for three different parameters: the number of hops of the temporal path, the feedback edge number of the underlying graph and the timed feedback vertex number which is a temporal version of the feedback vertex number they introduced in the article. Thejaswi, Lauri and Gionis [26] also presented an FPT algorithm for restless temporal path with respect to the number of hops, among other results. Zschoche [29] proposed a randomized $O(4^{k-d}|G|^{O(1)})$ algorithm to decide
whether there is a restless temporal path from *s* to *t* in *G* of length at most *k*, where *d* is the minimum length of a temporal *st*-path. The parameter we study here is not bounded by any of the parameters used so far for the design of algorithms for restless temporal path (and vice versa).

Note that computing a restless temporal walk between two nodes (rather
than a temporal path) can be done in polynomial time in the point model
as shown by Himmel, Nichterlein and Niedermeier [4]. However, Orda and
Rom [24] proved that finding a restless temporal walk is NP-hard in the interval
model.

Bumpus and Meeks [6] introduced the interval-membership-width parameter which captures the temporal aspect of the graph (unlike parameters such as the feedback edge number of the underlying graph). They worked with the point model and showed that determining if a temporal graph is temporally Eulerian (i.e. admits a temporal circuit visiting each underlying edge exactly once) is FPT when parameterized by the interval-membership-width. They obtained an FPT algorithm parameterized by the maximum number of times per edge for a problem of Akrida, Mertzios and Spirakis [1]. They also studied a problem of vertex reachability called MinReachDelete, which remains NP-hard even with bounded interval-membership-width. They thus introduced a vertex-variant of their parameter, the vertex-interval-membership-width, that brings tractability to the problem. Enright, Meeks and Molter [11] showed that counting the number of temporal paths between a given pair of nodes is FPT for the vertex-interval-membership-width. Hand, Enright and Meeks [14] presented an FPT algorithm, also with respect to the vertex-variant, for a problem called Temporal Firefighter. Christodoulou, Crescenzi, Marino, Silva and Thilikos [10] recently modified the definition of (vertex)-interval-membership-width by considering the evolution of the connected components of the temporal graph and studied several temporal problems parameterized by the new parameters. These variants are bounded by their respective counterparts, and can even be arbitrarily smaller. In particular, they translate the results of [6] for the temporal Eulerian trail and [14] for the firefighter problem to their refined parameters.

## 1.2 Contributions

One of the objectives in the field of temporal graphs is to find relevant parame-
ters that bring tractability to temporal problems. Our work consists in investi-
gating the new parameters introduced by Bumpus and Meeks [6] for the prob-
lem of restless temporal path. We show that the vertex-interval-membership-
width parameter is not bounded by any of the parameters previously studied
for the design of FPT algorithms for the problem of restless temporal path
(those considered in [8, 29]). We exhibit the NP-hardness of restless temporal
path in the point model with uniform delay one even if the graph has interval-
membership-width equal to three, which implies that there is no FPT algorithm
parameterized by the interval-membership-width if P≠NP. We provide an FPT
algorithm parameterized by the vertex-interval-membership-width in this model
and adapt it in the case of arbitrary positive delays. The time complexity of
these algorithms is O(M2^k k) and O(M2^k k(k + log M)), respectively, where M
is the number of timed edges and k is the vertex-interval-membership-width.
They do not require knowledge of the value of k. Moreover, the complexity
bounds still hold if k is the variant of the parameter proposed in [10]. Finally,
we prove the hardness of restless temporal path in the interval model even if
the vertex-interval-membership-width is equal to three.

1.3 Structure of the Paper

Section 2 introduces the notations and provides the necessary definitions. In Section 3, we focus on the point model with uniform delay one (which corresponds to the classical strict setting), while Section 4 deals with the case of arbitrary positive delays. Section 5 focuses on the interval model.

2 Preliminaries

2.1 Temporal Graphs

In what follows, we introduce the definition of a temporal graph in the point
model as well as useful notions and notations in this model. We call a temporal
graph in this model a point temporal graph. The adapted definitions for the
interval model are presented in the corresponding section for ease of reading.

A point temporal graph $G = (V, E)$ consists of a set of nodes $V$ and a set of timed arcs $E \subseteq V \times V \times \mathbb{N} \times \mathbb{N}_{>0}$. Informally, a timed arc $(u, v, \tau, \delta) \in E$ means that if we are at node $u$ at time exactly $\tau$, we can arrive at $v$ at time $\tau + \delta$ by taking the timed arc $(u, v, \tau, \delta)$. Time $\tau$ is called the appearance time (also departure time) of the timed arc $(u, v, \tau, \delta)$. Time $\tau + \delta$ is called the arrival time of $(u, v, \tau, \delta)$. The value $\delta$ is called the delay. Note that the timed arcs are directed. We assume that both $V$ and $E$ are finite. The lifetime of a point temporal graph $G = (V, E)$ is defined as $\Lambda = \max\{\tau + \delta \mid (u, v, \tau, \delta) \in E\}$.

Let $\mathcal{T}(E) = \{\tau \in \mathbb{N} \mid \exists(u, v, \tau, \delta) \in E\}$ be the set of appearance times of $G$.
We define $E_{\tau} = \{(u, v, \tau, \delta) \in E\}$, the set of timed arcs appearing at time $\tau$.
The underlying graph of a point temporal graph $G = (V, E)$ is the static directed
graph $G_{\downarrow} = (V, E_{\downarrow})$ with $E_{\downarrow} = \{(u, v) \in V^2 \mid \exists \tau \in \mathbb{N}, \delta \in \mathbb{N}_{>0}, (u, v, \tau, \delta) \in E\}$.

Let $\llbracket i, j \rrbracket$ denote the set of integers $k$ such that $i \le k \le j$ for $i, j \in \mathbb{N}$. If $i > j$, the set is empty. A temporal st-walk of length $\ell$ from $s = v_0$ to $t = v_\ell$ in a point temporal graph $G = (V, E)$ is a sequence of timed arcs $W = (v_{i-1}, v_i, \tau_i, \delta_i)_{i \in \llbracket 1, \ell \rrbracket}$ such that for all $i \in \llbracket 1, \ell-1 \rrbracket$, $\tau_i + \delta_i \le \tau_{i+1}$. This is a temporal path if $v_i \ne v_j$ for $i \ne j$, $i, j \in \llbracket 0, \ell \rrbracket$. The arrival time of $W$ is $\tau_\ell + \delta_\ell$. For $i \in \llbracket 1, \ell-1 \rrbracket$, the waiting time at an intermediate node $v_i$ is defined as $\tau_{i+1} - (\tau_i + \delta_i)$. Let $V(W)$ denote the set of vertices of $W$, that is $V(W) = \{v_0, \dots, v_\ell\}$.

In a Δ-restless temporal st-path, the waiting time at any intermediate node
on the path is at most Δ:

**Definition 1.** A temporal path (or walk) $(v_{i-1}, v_i, \tau_i, \delta_i)_{i \in \llbracket 1, \ell \rrbracket}$ in a point tem-
poral graph $G = (V, E)$ is Δ-restless if $\tau_{i+1} - (\tau_i + \delta_i) \le \Delta$ for all $i \in \llbracket 1, \ell-1 \rrbracket$.

Figure 1 gives an example of a 2-restless temporal path.

We assume that a point temporal graph $G = (V, E)$ is given as input as a list
of timed arcs sorted by non-decreasing appearance time, which we also denote
$E$ for simplicity. We denote by $M = |E|$ the number of timed arcs. Finally, we
consider the following decision problem:
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of the notion of restless temporal path. A tuple $(\tau, \delta)$ next to an arrow indicates the departure time $\tau$ and the delay $\delta$ of a timed arc. For instance, there is a timed arc $(s, u, 1, 1)$ and a timed arc $(u, t, 5, 2)$. The path from $s$ to $t$ consisting of the sequence of timed arcs $(s, u, 1, 1)$, $(u, v, 4, 2)$, $(v, t, 6, 1)$ is a 2-restless temporal st-path. In this point temporal graph, there is no 1-restless temporal st-path.</figcaption></figure>

**Problem 1.** POINT-RESTLESS-TEMPORAL-PATH: Given a point temporal graph $G = (V, E)$, a source node $s \in V$, a target node $t \in V$ and a waiting time $\Delta \in \mathbb{N}$, is there a $\Delta$-restless temporal path from $s$ to $t$ in $G$?

A point temporal graph $G = (V, E)$ is said to have uniform delay one if each timed arc has delay one, that is $\forall(u, v, \tau, \delta) \in E$, $\delta = 1$. Note that a symmetric point temporal graph with uniform delay one (that is if $(u, v, \tau, 1)$ is a timed arc of $G$ then the reverse timed arc $(v, u, \tau, 1)$ is also a timed arc of $G$) corresponds to an undirected temporal graph without delay in the classical strict setting where appearance times are required to strictly increase along a temporal walk. In the following, when working with a point temporal graph with uniform delay one, we omit the delay for the sake of simplicity and write a timed arc $(u, v, \tau)$ instead of $(u, v, \tau, 1)$.

## 2.2 The Interval-Membership-Width Parameters

In this section, we adapt to our context the two parameters introduced in [6] for a simpler temporal graph model without delays, namely the interval-membership-width and the vertex-interval-membership-width.

We say that an arc $(u, v) \in E_{\downarrow}$ of the underlying graph is active over time $\tau$ if there is a timed arc $(u, v, \tau_0, \delta_0) \in E$ whose appearance time $\tau_0$ is before or at $\tau$ and a timed arc $(u, v, \tau_1, \delta_1) \in E$ whose arrival time $\tau_1 + \delta_1$ is after or at $\tau$, that is if $\tau^{min}(u, v) \le \tau \le \tau^{max}(u, v)$ with:

$$ \tau^{min}(u, v) = \min\{\tau \in \mathbb{N} \mid \exists \delta \in \mathbb{N}_{>0}, (u, v, \tau, \delta) \in E\}, \\ \tau^{max}(u, v) = \max\{\tau + \delta \in \mathbb{N} \mid (u, v, \tau, \delta) \in E\}. $$

**Definition 2.** Given a point temporal graph $G = (V, E)$ with lifetime $\Lambda$ and $\tau \in [0, \Lambda]$, we define $F_{\tau}^a$ as the set of arcs that are active over time $\tau$, that is:

$$ F_{\tau}^{a} = \{(u, v) \in E_{\downarrow} \mid \tau^{min}(u, v) \le \tau \le \tau^{max}(u, v)\} $$

The arc-interval-membership-width $imw(G)$ is the maximum number of arcs active over any time, that is $imw(G) = \max_{\tau \in [0, \Lambda]} |F_{\tau}^a|$. For the sake of brevity, we will call this parameter the arc-IM-width.
Let us now define the vertex-variant of the arc-IM-width. We say that a node $u \in V$ is active over time $\tau$ if there is a timed arc $(v, w, \tau_0, \delta_0) \in E$ with $v = u$ or $w = u$ whose appearance time $\tau_0$ is before or at $\tau$ and a timed arc $(x, y, \tau_1, \delta_1) \in E$ with $x = u$ or $y = u$ whose arrival time $\tau_1 + \delta_1$ is after or at $\tau$, that is if $\tau^{min}(u) \le \tau \le \tau^{max}(u)$ with:

$$ \tau^{min}(u) = \min\{\tau \in \mathbb{N} | \exists v \in V, \delta \in \mathbb{N}_{>0}, (u, v, \tau, \delta) \in E \text{ or } (v, u, \tau, \delta) \in E\}, $$

$$ \tau^{max}(u) = \max\{\tau + \delta \in \mathbb{N} | \exists v \in V, (u, v, \tau, \delta) \in E \text{ or } (v, u, \tau, \delta) \in E\} $$

**Definition 3.** Given a point temporal graph $G = (V, E)$ with lifetime $\Lambda$ and $\tau \in [0, \Lambda]$, we define $F_{\tau}^v$, written $F_{\tau}$ for simplicity, as the set of nodes that are active over time $\tau$, that is:

$$ F_{\tau} = \{u \in V | \tau^{min}(u) \le \tau \le \tau^{max}(u)\} $$

The vertex-interval-membership-width $vimw(G)$ is the maximum number of nodes active over any time, that is $vimw(G) = \max_{\tau \in [0, \Lambda]} |F_{\tau}|$. For the sake of brevity, we will call this parameter the vertex-IM-width.

This parameter is not bounded by any of the parameters used in [8, 29] for the design of algorithms for the restless temporal path problem. See Appendix A for details.

Note that $\tau^{min}(u)$ and $\tau^{max}(u)$ for all $u \in V$ can be computed in $O(M)$ time from the list of timed arcs.

# 3 Point Model with Uniform Delay One (Classical Strict Setting)

We first rule out the possibility of an FPT algorithm for restless temporal path parameterized by arc-IM-width:

**Proposition 1.** POINT-RESTLESS-TEMPORAL-PATH is NP-hard, even if the input point temporal graph has arc-IM-width equal to three and uniform delay one.

This proposition is obtained by adapting the reduction in [8]. For the sake of completeness, we give it in Appendix B.

Our main result is an FPT algorithm parameterized by vertex-IM-width:

**Theorem 1.** When the input point temporal graph $G = (V, E)$ has uniform delay one, POINT-RESTLESS-TEMPORAL-PATH can be solved in $O(Mk2^k)$ deterministic time, where $k$ is the vertex-IM-width of $G$.

This result is the consequence of the algorithm we will now present. In the following, we want to compute the set of nodes reachable from a source $s$ via a $\Delta$-restless temporal path in a point temporal graph with uniform delay one, parameterized by the vertex-IM-width. Define the trace of a temporal path at time $\tau$ as the set of active nodes over $\tau$ it contains:

**Definition 4.** The trace of a temporal path $P$ at time $\tau$ is the set $V(P) \cap F_{\tau}$.
For ease of informal explanation, we might refer to a trace *S* without specifying a time τ if the specific time is not relevant in the explanation. Note that *F*<sub>τ</sub> can be viewed as a separator in the sense that any temporal *uv*-path where *u* is active before τ (that is τ<sup>max</sup>(*u*) < τ) and *v* is active after τ (that is τ<sup>min</sup>(*v*) > τ) must go through a node of *F*<sub>τ</sub>.

The main idea of the algorithm is to scan timed arcs in order of appearance
time τ while maintaining, for each node u, the traces of all Δ-restless su-paths.
For each such trace, we store the last arrival time of a Δ-restless temporal su-
path. Note that this information is sufficient to determine if a scanned timed
arc (u, v, τ) can extend a Δ-restless temporal path with such a trace. More
precisely, for each node u, L[u] stores a list of couples (S, σ) where S is the
trace of a Δ-restless su-path using timed arcs scanned so far, and σ is the last
arrival time of such a path with trace S. When scanning all timed arcs (u, v, τ)
with same appearance time τ, we update a similar list L'[v] of traces that can be
obtained with Δ-restless temporal paths ending with such timed arcs (u, v, τ).
Specifically, for a couple (S, σ) in L[u], we check if v /∈ S to respect the property
of temporal path and if τ − σ ≤ Δ to respect the Δ-restless constraint. We then
merge lists associated to each node and clean them to remove duplicates and to
update traces according to which nodes are active over time τ. See Algorithm 1
for a detailed pseudo-code.

To prove the correctness of the algorithm, we introduce the following notations. Let $\mathcal{T}(E) = \{\tau_1, \dots, \tau_T\}$ with $\tau_1 < \dots < \tau_T$. We define $E^i = \{(u, v, \tau) \in E \mid \tau \le \tau_i\}$, the set of timed arcs whose appearance time is less than or equal to $\tau_i$, for $i \in [1, T]$. Finally, let $G^i = (V, E^i)$. In the following $L_i[u]$ denotes $L[u]$ just after processing time $\tau_i$. Let $L_i^S[u]$ be the set of traces in $L_i[u]$, that is $L_i^S[u] = \{S \mid \exists(S, \sigma) \in L_i[u]\}$. Given $S \in L_i^S[u]$, the time associated to $S$ is the unique time $\tau_S^i$ such that $(S, \tau_S^i) \in L_i[u]$. Finally, for $i \in [1, T]$ and $u \in V$, let $\tau_i^u$ be the last appearance time of a timed arc to $u$ before or at $\tau_i$, that is $\tau_i^u = \max\{\sigma \mid \exists(w, u, \sigma) \in E^i\}$. We can now state the following.

**Lemma 1.** For all $i \in [1, T]$, $u \in V$,

* $L_i^S[u]$ is the set of traces at time $\tau_i^u$ of all Δ-restless temporal su-paths in $G^i$;

* $\forall S \in L_i^S[u]$, its associated time $\tau_S^i$ is the last arrival time of a Δ-restless temporal su-path in $G^i$ with trace $S$ at time $\tau_i^u$.

*Proof.* The proof is by induction on *i*. When processing all timed arcs with appearance time $\tau_1$, we add to $L'[v]$ the couple $(\{s, v\}, \tau_1 + 1)$ for each timed arc $(s, v, \tau_1)$ with $v \neq s$. Thus, this is true for $i=1$.

Suppose that this is true for *i* with $1 \le *i* \le *T* - 1$ and let us prove that this is true for *i* + 1. Let *v* ∈ *V*. If there is no timed arc to *v* with appearance time $\tau_{i+1}$, then $L[v]$ is not modified and we have $L_{i+1}^S[v] = L_i^S[v]$ and thus $L_{i+1}^S[v]$ is the set of traces at time $\tau_{i+1}^v = \tau_i^v$ of all Δ-restless temporal sv-paths in $G^{i+1}$.

Let us now suppose that there is at least one timed arc to v with appearance time $\tau_{i+1}$. Consider any Δ-restless temporal sv-path *P* ending with such a timed arc (u, v, $\tau_{i+1}$). Its prefix $P_{pre}$ (i.e. the path *P* without the last timed arc) is in $G^i$ since the graph has positive delays. By induction hypothesis, $P_{pre}$ is associated to a trace *S* at time $\tau_i^u$ in $L_i^S[u]$ and the associated time $\tau_S^i$ is the last arrival time of a Δ-restless temporal su-path $P_{max}$ in $G^i$ with trace
<caption>**Algorithm 1** Δ-restless temporal path</caption>

**Require:** A point temporal graph $G = (V, E)$ with uniform delay one with $E$ sorted by increasing departure time, a source $s \in V$, a maximum waiting time $\Delta$

**Ensure:** A table *Reachable* such that *Reachable*[v] = True if and only if there is a Δ-restless temporal path from s to v

1: *Reachable*[s] := True, *Reachable*[v] := False for all $v \in V \setminus \{s\}$

2: Compute the set $\mathcal{T}(E) = \{\tau_1, \dots, \tau_T\}$ of appearance times, with $\tau_1 < \dots < \tau_T$

3: Compute $E_{\tau} = \{(u, v, \tau, \delta) \in E\}$, $V_{\tau}^{-} = \{v \in V \mid \exists(u, v, \tau) \in E_{\tau}\}$ for all $\tau \in \mathcal{T}(E)$

4: Compute $\tau^{max}(u)$ for all $u \in V$

5: **for all** $\tau \in \mathcal{T}(E)$ in increasing order **do**

6: $L[s] := [(\{s\}, \tau)] \quad \triangleright \text{ We can start at } s \text{ at any time}$

7: **for all** $(u, v, \tau) \in E_{\tau}$ **do**

8: **for all** $(S, \sigma) \in L[u]$ **do**

9: **if** $v \notin S$ and $\tau - \sigma \le \Delta$ **then**

10: $S' := (S \cap F_{\tau}) \cup \{v\}$ \quad $\triangleright$ Note that $u \in S \cap F_{\tau}$

11: Add $(S', \tau + 1)$ to $L'[v]$

12: *Reachable*[v] := True

13: **for all** $v \in V_{\tau}^{-}$ **do**

14: Append $L'[v]$ to $L[v]$

15: $L'[v] := \emptyset$

16: **CLEANUP**($v, \tau$)

17: **procedure** **CLEANUP**($v, \tau$) \quad $\triangleright$ Given a node $v \in V$ and a time $\tau$

18: **for all** $(S, \sigma) \in L[v]$ **do**

19: Remove from $S$ all $u$ such that $\tau^{max}(u) < \tau$

20: Sort $L[v]$ according to the first coordinate (sets are sorted lexicographically)

21: For each $S$ such that there is a $(S, \sigma) \in L[v]$, keep only the couple $(S, \sigma)$ with maximal $\sigma$

$S$ at time $\tau_i^u$. In Line 9 of Algorithm 1, we check that we can extend the path associated to each corresponding couple $(S, \sigma) \in L[u]$ with $(u, v, \tau_{i+1})$: the condition $\tau - \sigma \le \Delta$ ensures that the maximum waiting time at $u$ is respected and the condition $v \notin S$ ensures that the extended walk is still a path. Indeed, if $v$ was already on the path, it would be in the trace $S$ by induction hypothesis since $v$ is active over time $\tau_{i+1}$. If the two conditions are satisfied, we add $((S \cap F_{\tau}) \cup \{v\}, \tau + 1)$ to $L'[v]$. Moreover, keeping for each $S \in L_i^S[u]$ only the last arrival time of a Δ-restless temporal *su*-path in $G^i$ with trace $S$ at time $\tau_i^u$ suffices. Indeed, consider two Δ-restless temporal *su*-paths $P_1$ and $P_2$ in $G^i$ with trace $S$ at time $\tau_i^u$ with respective arrival time $\sigma_1$ and $\sigma_2$, with $\sigma_2 > \sigma_1$. If we can extend the Δ-restless temporal path $P_1$ with a timed arc $(u, w, \tau_{i+1})$, then we can also extend $P_2$ with the same timed arc as the waiting time at $u$ will be smaller in the extension of $P_2$. Thus, after processing all the arcs with appearance time $\tau_{i+1}$ (Line 12), for each Δ-restless temporal *sv*-path $P$ with arrival time $\tau_{i+1} + 1$, there is a couple $(S', \tau_{i+1} + 1)$ in $L'[v]$ where $S'$ is the trace of $P$ at time $\tau_{i+1}^v = \tau_{i+1}$. We add $L'[v]$ to $L[v]$ Line 14. Finally, the calls to
the auxiliary function CLEANUP ensure that all sets in $L[v]$ contain only nodes in $F_{\tau_{i+1}}$ (Line 19) and that we keep for each $S$ only the couple (and only one copy of this couple) with maximal associated $\sigma$ (Line 21). Thus, the hypothesis is satisfied for $i+1$.

□

Theorem 1 is a consequence of the following.

**Proposition 2.** *Algorithm 1 computes the set of nodes reachable from a source s via a $\Delta$-restless temporal path in a point temporal graph G with uniform delay one in $O(Mk2^k)$ deterministic time, where k is the vertex-IM-width of G.*

*Proof.* The correctness follows immediately from Lemma 1.

Regarding the time complexity, let us first observe that, after a call to `CLEANUP(v, τ)` for $v \in V$ and $\tau \in \mathbb{N}$, we have that the size of $L[v]$ is at most $2^k$. Indeed, the sets $S$ in $L[v]$ after `CLEANUP` are all subsets of $F_\tau$ (Line 19). Thus, there are at most $2^k$ different subsets in $L[v]$. Moreover, we keep only one couple $(S, \sigma)$ for each set $S$ (Line 21). With this, Lines 9-12 are executed $O(M2^k)$ times. Computing $S \cap F_\tau$ for a trace $S$ (Line 10) and checking the condition $v \notin S$ (Line 9) take $O(k)$ time. Indeed, $S \cap F_\tau$ can be done by scanning the set $S$ and for each $u \in S$, checking if $\tau \le \tau^{max}(u)$.

Computing $E_\tau$, $V_\tau^-$ for each $\tau \in \mathcal{T}(E)$ and $\tau^{max}(u)$ for each $u \in V$ (Lines 2, 3 and 4) can be done in $O(M)$ time.

Let us now analyze the cost of cleaning up. Let us denote $M_\tau^v$ the number of timed arcs to $v$ with appearance time $\tau$, that is $M_\tau^v = |\{u \in V \mid (u, v, \tau) \in E\}|$. When processing a node $v$ at Line 13, the size of $L[v]$ after appending $L'[v]$ to $L[v]$ (Line 14) is at most $2^k + 2^k M_\tau^v$. Then, in `CLEANUP(v, τ)`, the cost of removing nodes that are not active over time $\tau$ (Line 19) and sorting the list (Line 20) is $O(k2^k M_\tau^v)$, using the lexicographic sort from [25] for Line 20. Thanks to this sorting, we can execute Line 21 in $O(2^k M_\tau^v)$ time by scanning the list and keeping one couple with maximum $\sigma$ for each $S$. Thus, the total cost of `CLEANUP()` calls is $O(\sum_{\tau \in \mathcal{T}(E)} \sum_{v \in V} k2^k M_\tau^v) = O(k2^k M)$. □

**Remark 1.** *The complexity still holds if $k$ is the refined parameter of [10]. Indeed, this parameter considers the maximum number of active nodes in a connected component of the underlying graph of any $G^i$. In Algorithm 1, the traces we consider are indeed included in the connected component of $s$.*

**Remark 2.** *A $\Delta$-restless temporal path from $s$ to a node $v \in V$ can be retrieved in $O(\ell k(k + \log M))$ time, where $\ell$ is the length of the path and $k$ is the vertex-IM-width of the point temporal graph. This requires additional instructions in Algorithm 1 that are executed in $O(M2^k k(k + \log M))$ deterministic time. The general idea is to store, for each trace $S$ of a $\Delta$-restless temporal path $P$ arriving at $v$ at time $\tau$, the predecessor $u$ of $v$ on the path, the arrival time $\sigma$ of the prefix of $P$ and the trace of the prefix at time $\sigma$. A detailed explanation is given in Appendix C.*

**Remark 3.** *In the function `CLEANUP(v, τ)` for $v \in V \setminus \{s\}$, we can also remove from $L[v]$ the couples $(S, \sigma)$ such that $\tau - \sigma > \Delta$ as we know that they will not be useful to extend a $\Delta$-restless temporal path.*
**Remark 4.** Note that our time complexity can be expressed in terms of the lifetime $\Lambda \ge T$ as $M \le k^2T$, where $k$ is the vertex-IM-width of $G$. Indeed, there are at most $k^2$ timed arcs with the same appearance time. The time complexity obtained is $O(k^32^k\Lambda)$.

**Remark 5.** Note that we can adapt our algorithm to the non-strict setting which corresponds to all timed arcs having delay zero. Indeed, it suffices to add $(S', \tau)$ instead of $(S', \tau + 1)$ at Line 11, and to repeat $|V_{\tau}^-|$ times Lines 7-16 as a temporal path in $(V, E_{\tau})$ has length at most $|V_{\tau}^-|$. As there are at most $k$ active nodes over time $\tau$, we have $|V_{\tau}^-| \le k$. Therefore, the overall complexity rises by no more than a factor $k$.

# 4 Point Model with Arbitrary Positive Delays

We now generalize the previous result for point temporal graphs with arbitrary (positive) delays:

**Theorem 2.** POINT-RESTLESS-TEMPORAL-PATH can be solved in $O(Mk2^k(k + \log M))$ deterministic time, where $k$ is the vertex-IM-width of the graph.

Again, we want to compute the set of nodes reachable from a source $s$ via a $\Delta$-restless temporal path in a point temporal graph, parameterized by the vertex-IM-width. Algorithm 1 cannot be easily adapted to arbitrary delays. The reason is that it implicitly assumes that all timed arcs with appearance time less than $\tau$ have arrival time at most $\tau$. This does not hold anymore for arbitrary delays. Note that scanning timed arcs in order of arrival time instead of appearance time leads to a similar problem.

To deal with this, we adapt the previous algorithm by storing all possible arrival times at a node $v$ for each possible trace $S$ in a self-balancing binary search tree. $L[v]$ now contains couples $(S, T_S)$ with $S$ a trace and $T_S$ the associated tree. When we try to extend a $\Delta$-restless temporal $su$-path with trace $S$ by adding a timed arc $(u, v, \tau, \delta)$, we first look at the last arrival time $\sigma \le \tau$ at $u$ with trace $S$ in the corresponding tree. If we can extend the path, then we add $\tau + \delta$ to $T_S^v$ if this time is not already in it, where $T_S^v$ is the tree associated to trace $S' = (S \cap F_\tau) \cup \{v\}$ in $L[v]$ (if there is no such tree, we create one that contains only $\tau + \delta$). After processing a timed arc with appearance time $\tau$, we clean up to update traces according to which nodes are active over time $\tau$. When performing this clean up, we might have several traces that become the same trace $S'$ after removing the nodes that are not active over time $\tau$. We thus need to merge the associated trees to have all the possible arrival times associated to trace $S'$. The detailed pseudo-code (Algorithm 2) as well as the analysis and useful remarks are available in Appendix D.

# 5 Hardness Result for the Interval Model

It is straightforward to extend the definitions of arc-IM-width and vertex-IM-width to an interval model of temporal graph where arcs are present during intervals of time. We show in Appendix E that, in this interval model, there
is no FPT algorithm parameterized by the corresponding variant of the vertex-
IM-width unless $P = NP$. The idea is to reduce SUBSET-SUM to RESTLESS-
TEMPORAL-PATH in an interval temporal graph of constant vertex-IM-width.
This is possible because the interval model allows to encode temporal graphs
that would have exponentially many edges if converted to the point model. In
particular, our reduction uses intervals of exponential length.

References

[1] Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Christoforos Raptopoulos. The temporal explorer who returns to the base. *Journal of Computer and System Sciences*, 120:179-193, 2021. doi:10.1016/j.jcss. 2021.04.001.

[2] Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Viktor Zama-
raev. Temporal Vertex Cover with a Sliding Time Window. In *45th Inter-
national Colloquium on Automata, Languages, and Programming (ICALP 2018)*, volume 107 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 148:1–148:14. Schloss Dagstuhl – Leibniz-Zentrum für In-
formatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.148.

[3] A.L. Barabási. *Network Science*. Cambridge University Press, 2016.

[4] Matthias Bentert, Anne-Sophie Himmel, André Nichterlein, and Rolf Niedermeier. Efficient computation of optimal temporal walks under waiting-time constraints. *Appl. Netw. Sci.*, 5(1):73, 2020. doi:10.1007/S41109-020-00311-0.

[5] B. Buixuan, A.ferreira, and A.jarry. Computing shortest, fastest, and fore-
most journeys in dynamic networks. *International Journal of Foundations
of Computer Science*, 14, 11 2011. doi:10.1142/S0129054103001728.

[6] Benjamin Merlin Bumpus and Kitty Meeks. Edge Exploration of Temporal Graphs. *Algorithmica*, 85(3):688-716, August 2022. doi:10.1007/s00453-022-01018-7.

[7] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola San-
toro. Time-Varying Graphs and Dynamic Networks. volume 27, 11 2010.
doi:10.1007/978-3-642-22450-8_27.

[8] Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding Temporal Paths Under Waiting Time Constraints. *Algorithmica*, 83(9):2754-2802, September 2021. doi:10.1007/s00453-021-00831-w.

[9] Arnaud Casteigts, Joseph G. Peters, and Jason Schoeters. Temporal Cliques Admit Sparse Spanners. In *46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)*, volume 132 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 134:1–134:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.134.
[10] Filippos Christodoulou, Pierluigi Crescenzi, Andrea Marino, Ana Silva, and Dimitrios M. Thilikos. Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional. In Adele Anna Rescigno and Ugo Vaccaro, editors, *Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, Ischia, Italy, July 1-3, 2024, Proceedings*, volume 14764 of Lecture Notes in Computer Science, pages 247-258. Springer, 2024. doi:10.1007/978-3-031-63021-7\_19.

[11] Jessica Enright, Kitty Meeks, and Hendrik Molter. Counting Temporal Paths. In *40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)*, volume 254 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 30:1-30:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.STACS.2023.30.

[12] Michael L. Fredman, Janos Komlos, and Endre Szemeredi. Storing a sparse table with $O(1)$ worst case access time. In *23rd Annual Symposium on Foundations of Computer Science (sfcs 1982)*, pages 165-169, 1982. doi: 10.1109/SFCS.1982.39.

[13] Roman Haag, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Feedback edge sets in temporal graphs. *Discrete Applied Mathematics*, 307:65-78, 01 2022. doi:10.1016/j.dam.2021.09.029.

[14] Samuel D. Hand, Jessica Enright, and Kitty Meeks. Making Life More Confusing for Firefighters. In *11th International Conference on Fun with Algorithms (FUN 2022)*, volume 226 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 15:1-15:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.FUN.2022.15.

[15] Petter Holme. Modern temporal network theory: a colloquium. *The European Physical Journal B*, 88(9), September 2015. doi:10.1140/epjb/e2015-60657-4.

[16] David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and Inference Problems for Temporal Networks. *Journal of Computer and System Sciences*, 64(4):820-842, 2002. doi:10.1006/jcss.2002.1829.

[17] William Ogilvy Kermack and A. G. McKendrick. A contribution to the mathematical theory of epidemics. *Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character*, 115(772):700-721, August 1927. doi:10.1098/rspa.1927.0118.

[18] Donald E. Knuth. *The art of computer programming, volume 3: (2nd ed.)* sorting and searching. Addison Wesley Longman Publishing Co., Inc., USA, 1998.

[19] Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. Stream Graphs and Link Streams for the Modeling of Interactions over Time. *Social Network Analysis and Mining*, 8, 10 2018. doi:10.1007/s13278-018-0537-7.

[20] George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs. *Journal of Computer and System Sciences*, 137:1-19, 2023. doi:10.1016/j.jcss.2023.04.005.
[21] Othon Michail. An Introduction to Temporal Graphs: An Algorithmic Perspective. *Internet Mathematics*, 12, 03 2015. doi:10.1007/978-3-319-24024-4_18.

[22] Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. *Theoretical Computer Science*, 634:1-23, 2016. doi: 10.1016/j.tcs.2016.04.006.

[23] M. Newman. *Networks*. OUP Oxford, 2018.

[24] Ariel Orda and Raphael Rom. Traveling without waiting in time-dependent networks is NP-hard. Technical report, Technion - Israel Institute of Technology, Haifa, Israel 32000, March 1989.

[25] Robert Paige and Robert E. Tarjan. Three Partition Refinement Algorithms. *SIAM Journal on Computing*, 16(6):973-989, 1987. doi: 10.1137/0216062.

[26] Suhas Thejaswi, Juho Lauri, and Aristides Gionis. Restless reachability problems in temporal graphs, 2025. doi:10.1007/s10115-025-02405-6.

[27] Huanhuan Wu, James Cheng, Yiping Ke, Silu Huang, Yuzhen Huang, and Hejun Wu. Efficient Algorithms for Temporal Path Computation. *IEEE Transactions on Knowledge and Data Engineering*, 28(11):2927-2942, 2016. doi:10.1109/TKDE.2016.2594065.

[28] Tim Zeitz. NP-hardness of shortest path problems in networks with non-FIFO time-dependent travel times. *Information Processing Letters*, 179:106287, 2023. doi:10.1016/j.ipl.2022.106287.

[29] Philipp Zschoche. Restless Temporal Path Parameterized Above Lower Bounds. In *40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)*, volume 254 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 55:1-55:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.STACS.2023.55.
A Comparison between the Vertex-IM-Width and
the Parameters in [8, 29]

Let us first recall the three parameters used in [8]. They designed FPT algo-
rithms for the restless temporal path problem parameterized by the number of
hops of the temporal path, the feedback edge number of the underlying graph
and the timed feedback vertex number. The feedback edge number of a graph
is the minimum number of edges one needs to delete in order to remove all
cycles. As the restless temporal path problem is W[1]-hard when parameterized
by the feedback vertex number of the underlying graph (one deletes vertices
instead of edges), they introduced the timed feedback vertex number. Let us
first define this parameter in our context. Removing a timed node (v, τ) from a
point temporal graph means removing all the timed arcs to v with arrival time
τ and all the timed arcs from v with departure time τ. The timed feedback
vertex number is the minimum number of timed nodes to be removed so that
the underlying graph of the obtained point temporal graph does not contain any
cycle. In the sequel, the three feedback parameters refer to the feedback edge
number of the underlying graph, the feedback vertex number of the underlying
graph and the timed feedback vertex number.

**Claim.** *There exists point temporal graphs for which the three feedback param-
eters are all equal to zero while the vertex-IM-width is unbounded.*

Simply consider a family of directed acyclic graphs without any isolated node
such that every timed arc has the same appearance time. The three feedback
parameters of such a point temporal graph are trivially equal to 0 while the
vertex-IM-width is equal to the number of nodes.

**Claim.** *There exists a family of point temporal graphs for which the vertex-IM-width is equal to two while the three feedback parameters are unbounded.*

Consider the symmetric point temporal graph with uniform delay one in
Figure 2. The constructed point temporal graph $G = (V, E)$ is as follows:

$V = \{u_0, \dots, u_{k-1}, v_0, \dots, v_{k-1}\};$

$\forall i \in [0, k-1], (u_i, v_i, 2i) \in E \text{ and } (v_i, u_i, 2i) \in E;$

$\bullet \forall i \in [0, k-2], (u_i, u_{i+1}, 2(i+1)) \in E, (u_{i+1}, u_i, 2(i+1)) \in E, (v_i, v_{i+1}, 2(i+1)) \in E \text{ and } (v_{i+1}, v_i, 2(i+1)) \in E.$

It is clear that the three feedback parameters of the point temporal graph are
unbounded.

Finally, the vertex-IM-width is equal to two. Indeed, we have that, for
$i \in [0, k-2]$, $u_i$ and $v_i$ are only active over times $2i$, $2i+1$, $2(i+1)$ and
$2(i+1)+1$. The nodes $u_{k-1}$ and $v_{k-1}$ are active over times $2(k-1)$ and
$2(k-1)+1$.

**Remark 6.** If we consider POINT-RESTLESS-TEMPORAL-PATH instances with $s = u_0$ and $t = u_{k-1}$, the number of hops of a temporal st-path is also unbounded.

Recall that Zschoche [29] proposed a randomized $O(4^{\ell-d}|G|^{O(1)})$ algorithm
for SHORT-RESTLESS-TEMPORAL-PATH in which one needs to decide whether
there is a restless temporal path from $s$ to $t$ in $G$ of length at most $\ell$, where $d$
is the minimum length of a temporal st-path.
<figure><img src="image_3.png" /><figcaption>Figure 2: Illustration of the constructed symmetric point temporal graph with uniform delay one. The number next to a line between node x and node y corresponds to the appearance time of the timed arcs from x to y and from y to x.</figcaption></figure>

**Claim.** *There exists a family of SHORT-RESTLESS-TEMPORAL-PATH instances for which $ℓ-d$ is unbounded while the vertex-IM-width is equal to three.*

We simply consider the point temporal graph of Figure 2 in which we add a node $w$ and the timed arcs $(u_0, w, 0)$ and $(w, u_{k-1}, 2(k-1))$. If we consider the instance with $s = u_0$, $t = u_{k-1}$ and $ℓ = k$, then we have that $ℓ-d$ is unbounded while the vertex-IM-width is equal to three.

## B Proof of Proposition 1

*Proof.* The reduction presented by Casteigts, Himmel, Molter and Zschoche in [8] is from the NP-complete problem EXACT (3,4)-SAT. In this problem, we are given a formula $\phi$ in conjunctive normal form, with each clause having exactly 3 literals and each variable appearing in exactly 4 clauses and we are asked whether the formula is satisfiable. We present an adaptation of the construction proposed in the article. Let $\phi$ be an instance of EXACT (3,4)-SAT with $n$ variables and $m$ clauses. Consider the following constructed point temporal graph $G = (V, E)$, with uniform delay one:

* $V = \{s_0, s_1, \dots, s_{n+1}\} \cup \{c_1, \dots, c_{m+1}\} \cup \{x_i^k | i \in [1, n], k \in [1, 4]\} \cup \{\bar{x}_i^k | i \in [1, n], k \in [1, 4]\}$;

* The source is $s = s_0$ and the target is $t = c_{m+1}$;

* For $i \in [0, n-1]$, we have the timed arcs $(s_i, x_{i+1}^1, 10i)$ and $(s_i, \bar{x}_{i+1}^1, 10i)$;

* For $i \in [1, n]$, $k \in [1, 3]$, we have the timed arcs $(x_i^k, x_i^{k+1}, 10(i-1)+2k)$ and $(\bar{x}_i^k, \bar{x}_i^{k+1}, 10(i-1)+2k)$;

* For $i \in [1, n]$, we have the timed arcs $(x_i^4, s_i, 10i-2)$ and $(\bar{x}_i^4, s_i, 10i-2)$;

* We have the timed arcs $(s_n, s_{n+1}, 10n)$ and $(s_{n+1}, c_1, 10n+2)$;

* For each clause $c_j$ with $j \in [1, m]$, if the variable $x_i$ (or $\bar{x}_i$) is present in $c_j$ and it is its $k$-th occurrence in $\phi$, we add the timed arcs $(c_j, x_i^k, 10n+4j)$ and $(x_i^k, c_{j+1}, 10n+4j+2)$ (or $(c_j, \bar{x}_i^k, 10n+4j)$ and $(\bar{x}_i^k, c_{j+1}, 10n+4j+2)$).

An illustration of this construction is presented in Figure 3.
<figure><img src="image_4.png" /><figcaption>Figure 3: Illustration of the constructed point temporal graph of Proposition 1. The number next to an arrow corresponds to the appearance time of the timed arc. Here, the clause $c_j$ of the formula $\phi$ is $c_j = \bar{x}_1 \lor \bar{x}_2 \lor x_n$ where $x_1$ appears for the third time, $x_2$ for the first time and $x_n$ for the fourth time.</figcaption></figure>

By adapting the proof in [8], we have that $\phi$ is satisfiable if and only if there is a $\Delta$-restless temporal path from $s$ to $t$ with $\Delta = 1$.

Let us now prove that the arc-IM-width of the constructed point temporal graph is less than or equal to 3. First, observe that for each $(u, v) \in E_{\downarrow}$, there is a unique $\tau_{uv}$ such that $(u, v, \tau_{uv}) \in E$, with $\tau_{uv}$ even. Thus, each $(u, v) \in E_{\downarrow}$ is active only over time $\tau_{uv}$ and $\tau_{uv} + 1$ by definition. Then, for $\tau \le 10n + 3$, the number of arcs active over time $\tau$ is at most 2 and for $\tau \ge 10n + 4$, it is at most 3 as the number of literals in a clause is exactly 3.

Note that the vertex-IM-width is at least $4n$. Indeed, each variable appears in exactly 4 clauses, thus for $i \in [1, n]$ and $k \in [1, 4]$, there is a timed arc to either $x_i^k$ or $\bar{x}_i^k$ with appearance time greater than $10n + 2$. As there is a timed arc to $x_i^k$ and a timed arc to $\bar{x}_i^k$ with appearance time smaller than $10n - 2$, $F_{10n}$ contains at least $4n$ nodes. $\square$

## C Retrieving Paths

When we extend a $\Delta$-restless temporal su-path with trace $S$ and arrival time $\sigma$ by a timed arc $(u, v, \tau)$ (Line 11 of Algorithm 1), we store information in a table *Arr* and a self-balancing binary search tree *Parent* in order to recover the path. More precisely, we add to *Parent* the association $((v, \tau+1, S'), (u, \sigma, S))$, where *S'* is the trace of the extended path at time $\tau$, and *Arr*[v] now contains $(\tau+1, S')$. The total cost of these two new instructions is $O(M2^k k(k+\log M))$. Indeed, the number of couples added to *Parent* is at most $M2^k$ so adding such couples takes $O(k \log(M2^k)) = O(k(k+\log M))$ time overall. The factor $k$ comes from the fact that we need to compare tuples that contain sets of size at most $k$. To do so, we use the lexicographic order and represent the sets as a sorted list of elements (adding a node $v$ to a set $S$ can be performed in $O(k)$ time).
When Reachable[v] = True, to retrieve a Δ-restless temporal path from s to v in G we first get Arr[v] = (τ', S'). Recall that, by the correctness of the algorithm, this means that we can reach v from s by a Δ-restless temporal path P in G with arrival time τ' such that the trace of P at time τ' − 1 is S'. Then, we find a tuple (u, σ, S) such that ((v, τ', S'), (u, σ, S)) is in Parent in O(k(k+log M)) time. This gives us the predecessor u of v in P, σ the arrival time of the prefix of P (without the last arc (u, v, τ' − 1)) and S = V(P) \ {v} ∩ Fσ − 1 is the trace of the prefix at time σ − 1. By the correctness of the algorithm, there is an element in Parent with the first tuple being (u, σ, S). We thus retrieve the predecessor of u in P and so on until we reach s.

We believe that the complexity of retrieving a path can be reduced to $O(\ell)$ by using perfect hashing [12] and coding the traces over $k$ bits (when $k$ and $\log n$ take $O(1)$ memory words).

D Point Model with Arbitrary Positive Delays:
Formal Description

We generalize Proposition 2 by providing Algorithm 2 below and obtain the
following.

**Proposition 3.** *Algorithm 2 computes the set of nodes reachable from a source s via a Δ-restless temporal path in a point temporal graph G in O(M2^k k(k + log M)) deterministic time, where k is the vertex-IM-width of G. Moreover, a Δ-restless temporal path from s to a node v can be retrieved in O(\ell k(k + log M)) deterministic time, where \ell is the length of the path.*

Proof. We have the following invariant: after processing time $\tau \in \mathcal{T}(E)$, the nodes $v \in V \setminus \{s\}$ with Reachable[$v$] = True are the nodes with an incoming timed arc whose departure time is less than or equal to $\tau$ (that is an arc $(u, v, \tau', \delta)$ with $\tau' \le \tau$) and such that there is a $\Delta$-restless temporal path from $s$ whose last timed arc is such an incoming timed arc. The proof of this statement follows similar arguments to the previous case with uniform delay one and is omitted here for brevity. The correctness of the algorithm follows from this invariant.

Regarding the time complexity, the number of times in a tree $T_S$ associated
to a node $u$ and a trace $S$ is bounded by $\delta^{-}(u) = |\{(x, y, \tau, \delta) \in E | y = u\}|$, the
in-degree of $u$, as the number of different arrival times at $u$ is bounded by the
number of incoming timed arcs of $u$. Thus, adding a time in a tree (Lines 9, 16
and 29) and the operation *Search* (Line 12) are in $O(\log M)$ time.

Note that at any point in the algorithm, the number of couples in the self-
balancing binary search tree $L[v]$ is at most $2 \cdot 2^k$. Indeed, $CLEANUPDELAY(v, \tau)$
ensures that the number of couples is at most $2^k$ by keeping only nodes that are
active over time $\tau$ for each trace. Then, when dealing with a timed arc $(u, v, \tau, \delta)$,
we add at most $2^k$ couples in $L[v]$ (Line 19) and immediately after we call
$CLEANUPDELAY(v, \tau)$. Thus, adding or deleting a couple to $L[v]$ (Lines 19, 26
and 31) and checking if there is a couple $(S', T_{S'})$ in $L[v]$ for a given $S'$ (Lines 15
and 27) can be done in $O(k \log(2^k)) = O(k^2)$ time. The factor $k$ comes from
the fact that we need to compare sets. To do so, we use the lexicographic order
and represent the sets as a sorted list of elements (adding a node $v$ to a set $S$
<caption>**Algorithm 2** Δ-restless temporal path with arbitrary (positive) delays</caption>

**Require:** A point temporal graph $G = (V, E)$ with $E$ sorted by increasing departure time, a source $s \in V$, a maximum waiting time $\Delta$

**Ensure:** A table *Reachable* such that *Reachable*[v] = True if and only if there is a Δ-restless temporal path from s to v

1: *Reachable*[s] := True, *Reachable*[v] := False for all $v \in V \setminus \{s\}$
2: Compute the set $\mathcal{T}(E) = \{\tau_1, \dots, \tau_T\}$ of appearance times, with $\tau_1 < \dots < \tau_T$
3: Compute $E_\tau = \{(u, v, \tau, \delta) \in E\}$ for each $\tau \in \mathcal{T}(E)$
4: Compute $\tau^{max}(u)$ for all $u \in V$
5: $T_{\{s\}}$ is an empty self-balancing binary search tree
6: $L[s]$ is a self-balancing binary search tree containing the couple $(\{s\}, T_{\{s\}})$
7: $L[v]$ is an empty self-balancing binary search tree for all $v \in V \setminus \{s\}$
8: **for all** $\tau \in \mathcal{T}(E)$ in increasing order **do**
9: Add $\tau$ to the tree $T_{\{s\}}$ associated to $\{s\}$ in $L[s] \triangleright$ We can start at $s$ at any time
10: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $(u, v, \tau, \delta) \in E_\tau$ **do**
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** $(S, T_S) \in L[u]$ **do**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\sigma := \text{Search}(T_S, \tau) \triangleright \text{Search}(T, \tau)$ returns the maximal $\sigma \le \tau$ in the tree $T$
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $v \notin S$ and $\tau - \sigma \le \Delta$ **then**
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S' := (S \cap F_\tau) \cup \{v\}$ &nbsp;&nbsp;&nbsp;&nbsp;$\triangleright$ Note that $u \in S \cap F_\tau$
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** there is a couple $(S', T_{S'}) \in L[v]$ **then**
16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $\tau + \delta$ to $T_{S'}$ if not already in it
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$T_{S'}$ is a self-balancing binary search tree containing time $\tau + \delta$
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $(S', T_{S'})$ to $L[v]$
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\*Reachable\*[$v$] := True
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;CLEANUPDELAY($v, \tau$)
22: &nbsp;&nbsp;&nbsp;&nbsp;**procedure** CLEANUPDELAY($v, \tau$) &nbsp;&nbsp;&nbsp;&nbsp;$\triangleright$ Given a node $v \in V$ and a time $\tau$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** $(S, T_S) \in L[v]$ **do**
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S' = S \cap F_\tau$
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $S' \neq S$ **then**
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Delete $(S, T_S)$ from $L[v]$
27: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** there is a couple $(S', T_{S'}) \in L[v]$ **then**
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** $\sigma \in T_S$ **do**
29: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $\sigma$ to $T_{S'}$ if not already in it
30: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $(S', T_S)$ to $L[v]$
can be performed in $O(k)$ time). Thus, the total cost of these operations is in $O(M2^k k^2)$ time.

Let us now analyze the cost of merging trees Lines 28-29. Let us bound the number of times we copy a time in a tree (Line 29). To do this, we bound the number of times a given time $\tau + \delta$ added to $T_{S_0}$ Line 16 or 18 is copied in another tree Line 29 of the `CLEANUPDELAY` procedure. It is copied from the tree $T_S$ to the tree $T_{S'}$ each time we remove nodes from $S$ Line 24. As $S_0$ contains at most $k$ nodes, the number of times this given time $\tau + \delta$ is copied is at most $k$. Finally, the total number of additions to a tree at Line 16 or 18 is at most $M2^k$. Thus, the total cost of adding at Line 29 is in $O(M2^k k \log M)$ time. Hence, the total cost of the algorithm is in $O(M2^k k(k + \log M))$ time.

Finally, the path retrieval works as before. □

**Remark 7.** When processing time $\tau$ we can remove times that are now useless in the trees. More precisely, we can remove the times $\sigma$ such that $\tau - \sigma > \Delta$. To remove such times in a self-balancing binary search tree such as an AVL tree or a red-black tree, we use the Split operation in $O(\log M)$ time (see e.g. [18]).

## E Hardness Result for the Interval Model

An interval temporal graph $G^{int} = (V, E^{int})$ consists of a set of nodes $V$ and a set of interval timed arcs $E^{int} \subseteq V \times V \times \mathbb{N} \times \mathbb{N} \times \mathbb{N}_{>0}$ such that, for every $(u, v, \tau, \tau', \delta) \in E^{int}$, we have $\tau' \ge \tau$. Informally, an interval timed arc $(u, v, \tau, \tau', \delta) \in E^{int}$ means that if we are at node $u$ at time $\tau_{dep} \in [\tau, \tau']$, we can arrive at $v$ at time $\tau_{dep} + \delta$ by taking the interval timed arc. The interval $[\tau, \tau']$ is called the appearance interval of $(u, v, \tau, \tau', \delta)$. The value $\delta$ is called the delay. Again, the interval timed arcs are directed. The lifetime of an interval temporal graph $G^{int} = (V, E^{int})$ is defined as $\Lambda^{int} = \max\{\tau' + \delta \mid (u, v, \tau, \tau', \delta) \in E^{int}\}$.

A temporal st-walk of length $\ell$ from $s = v_0$ to $t = v_\ell$ in an interval temporal graph is a sequence of interval timed arcs and associated departure times $W = ((v_{i-1}, v_i, \tau_i, \tau'_i, \delta_i), \tau_i^{dep})_{i \in [1, \ell]}$ such that $\tau_i \le \tau_i^{dep} \le \tau'_i$ for all $i \in [1, \ell]$ and $\tau_i^{dep} + \delta_i \le \tau_{i+1}^{dep}$ for all $i \in [1, \ell-1]$. This is a temporal path if $v_i \ne v_j$ for $i \ne j$, $i, j \in [0, \ell]$. The arrival time of $W$ is $\tau_\ell^{dep} + \delta_\ell$. For $i \in [1, \ell-1]$, the waiting time at node $v_i$ is defined as $\tau_{i+1}^{dep} - (\tau_i^{dep} + \delta_i)$.

A temporal path (or walk) $((v_{i-1}, v_i, \tau_i, \tau'_i, \delta_i), \tau_i^{dep})_{i \in [1, \ell]}$ in an interval temporal graph is $\Delta$-restless if $\tau_{i+1}^{dep} - (\tau_i^{dep} + \delta_i) \le \Delta$ for all $i \in [1, \ell-1]$.

We assume that an interval temporal graph $G^{int} = (V, E^{int})$ is given as input as a list of interval timed arcs, which we also denote $E^{int}$ for simplicity. Finally, we consider the following decision problem:

**Problem 2.** INTERVAL-RESTLESS-TEMPORAL-PATH: Given an interval temporal graph $G^{int} = (V, E^{int})$, a source node $s \in V$, a target node $t \in V$ and a waiting time $\Delta \in \mathbb{N}$, is there a $\Delta$-restless temporal path from $s$ to $t$ in $G^{int}$?

Note that the interval model captures the point model, since an appearance time in the point model is an appearance interval with equal bounds in the interval model. Moreover, an interval temporal graph $G^{int} = (V, E^{int})$ can be transformed into a point temporal graph $G = (V, E)$ with $E = \{(u, v, \tau + i, \delta) \mid \exists (u, v, \tau, \tau', \delta) \in E^{int} \text{ and } i \in [0, \tau' - \tau]\}$. However, this transformation might drastically increase the size of the input.
Let us now define the vertex-IM-width of an interval temporal graph $G^{int} = (V, E^{int})$. We say that a node $u \in V$ is active over time $\tau$ if there is an interval timed arc $(v, w, \tau_0, \tau_1, \delta) \in E^{int}$ with $v = u$ or $w = u$ and $\tau_0 \le \tau$ and an interval timed arc $(x, y, \tau'_0, \tau'_1, \delta') \in E^{int}$ with $x = u$ or $y = u$ and $\tau'_1 + \delta' \ge \tau$, that is if $\tau_{int}^{min}(u) \le \tau \le \tau_{int}^{max}(u)$ with:

$$ \tau_{int}^{min}(u) = \min\{\tau \in \mathbb{N} | \exists v \in V, \tau' \in \mathbb{N}, \delta \in \mathbb{N}_{>0}, (u, v, \tau, \tau', \delta) \in E^{int} \\ \text{or} \\ (v, u, \tau, \tau', \delta) \in E^{int}\}, $$

$$ \tau_{int}^{max}(u) = \max\{\tau' + \delta \in \mathbb{N} | \exists v \in V, \tau \in \mathbb{N}, (u, v, \tau, \tau', \delta) \in E^{int} \\ \text{or} \\ (v, u, \tau, \tau', \delta) \in E^{int}\}. $$

**Definition 5.** Given an interval temporal graph $G^{int} = (V, E^{int})$ with lifetime $\Lambda^{int}$ and $\tau \in [0, \Lambda^{int}]$, we define $F_{\tau}^{int}$ as the set of nodes that are active over time $\tau$, that is:

$$ F_{\tau}^{int} = \{u \in V | \tau_{int}^{min}(u) \le \tau \le \tau_{int}^{max}(u)\} $$

The interval vertex-IM-width $vimw^{int}(G^{int})$ is the maximum number of nodes active over any time, that is $vimw^{int}(G^{int}) = \max_{\tau \in [0, \Lambda^{int}]} |F_{\tau}^{int}|$.

**Theorem 3.** INTERVAL-RESTLESS-TEMPORAL-PATH is NP-hard, even if the input interval temporal graph has interval vertex-IM-width equal to three.

The NP-hardness of restless temporal walk in the interval model was proved by Orda and Rom [24]. A simpler proof is presented by Zeitz in [28]. We adapt the reduction of the latter to prove our result. The main difficulty of our reduction lies in the choice of the appearance intervals and the delays so that the interval vertex-IM-width is equal to three.

*Proof.* The reduction is from the NP-hard problem SUBSET-SUM. Recall that in the problem SUBSET-SUM, we are given $n$ positive integers $x_1, \dots, x_n$ and a target $X$, and we want to determine if there exists $I \subseteq [1, n]$ such that $\sum_{i \in I} x_i = X$. Let $((x_i)_{i \in [1, n]}, X)$ be an instance of SUBSET-SUM. We construct an instance of INTERVAL-RESTLESS-TEMPORAL-PATH based on a sequence of times $\sigma_0 = \tau_0 < \sigma_1 < \tau_1 < \sigma_2 < \dots$ (that we define later):

* The nodes of the constructed interval temporal graph $G^{int} = (V, E^{int})$ are numbered from 0 to $n+1$. The source is $s=0$ and the target is $t=n+1$;

* For $i \in [0, n-1]$, we have the interval timed arcs $e_{i+1}^1 = (i, i+1, \sigma_i, \tau_i, \delta_i)$ and $e_{i+1}^2 = (i, i+1, \sigma_i, \tau_i, \delta_{i+1})$;

* We add the interval timed arc $e_{n+1} = (n, t, \sigma_n + X, \sigma_n + X, 1)$;

* We take $\Delta = 0$.

Finally, we have:
<figure><img src="image_5.png" /><figcaption>Figure 4: Illustration of the construction of Theorem 4. The labels next to the arrows correspond to the appearance intervals and the delays of the interval timed arcs.</figcaption></figure>

$$ \delta_i = 1 + \sum_{k \in [1, i]} x_k \quad \text{for } i \in [0, n] $$

$$ \sigma_0 = 0 $$

$$ \sigma_i = \sigma_{i-1} + \delta_{i-1} \quad \text{for } i \in [1, n] $$

$$ \tau_0 = 0 $$

$$ \tau_i = \tau_{i-1} + \delta_i \quad \text{for } i \in [1, n] $$

An illustration of the construction is given Figure 4. We define the delays and the appearance intervals as such for several reasons:

**Claim.** The earliest arrival time of a Δ-restless temporal path from s to i in $G^{int}$ for $1 \le i \le n$ is $\sigma_i$ and the latest arrival time is $\tau_i$.

Let us prove this by induction. This is true for $i = 1$. Let us assume that this is true for $i$ such that $1 \le i \le n - 1$. The earliest arrival time of a Δ-restless temporal path from s to $i + 1$ is then $\sigma_i + \delta_i = \sigma_{i+1}$ as $\sigma_i$ is the earliest arrival time of a Δ-restless temporal path from s to i and $\delta_i$ is the smallest possible delay of an interval timed arc from i to $i + 1$ (note that the interval timed arcs from i to $i + 1$ have appearance interval $[\sigma_i, \tau_i]$). We conclude with the same kind of reasoning for $\tau_{i+1}$.

**Claim.** We have that $\sigma_i = \tau_{i-1} + 1$ for $i \in [1, n]$, that is the appearance interval of each interval timed arc from i to $i + 1$ is strictly after the appearance interval of an interval timed arc from $i - 1$ to i for $i \in [1, n - 1]$.

Let us prove this by induction. This is true for $i = 1$. Let us assume that this is true for $i$ such that $1 \le i \le n - 1$. We have that $\sigma_{i+1} = \sigma_i + \delta_i = \tau_{i-1} + 1 + \delta_i$ by induction hypothesis and thus $\sigma_{i+1} = \tau_i + 1$. We will see later that this is useful in order to have the interval vertex-IM-width equal to three.

**Claim.** There is a Δ-restless temporal path from s to t in $G^{int}$ if and only if there exists $I \subseteq [1, n]$ such that $\sum_{i \in I} x_i = X$.

**Necessity:** Suppose that there exists $I \subseteq [1, n]$ such that $\sum_{i \in I} x_i = X$. Consider the following temporal st-path in $G^{int}$: $P = (e_i, \sigma_{i-1} + \sum_{k \in I \cap [1, i-1]} x_k)_{i \in [1, n+1]}$ with, for $i \in [1, n]$, $e_i = e_i^2$ if $i \in I$ and $e_i = e_i^1$ otherwise. Informally, we traverse arc $e_1^1$ at time 0 if $1 \in I$, otherwise we traverse arc $e_1^1$. Then, as soon as we arrive at node $i - 1$ for $2 \le i \le n$, we directly take arc $e_i^2$ if $i \in I$ and $e_i^1$ otherwise. Then we take arc $e_{n+1}$. Let us prove that P is a valid Δ-restless
temporal st-path in $G^{int}$ with $\Delta = 0$. To do so, we only need to prove that $P_{sub_j} = (e_i, \sigma_{i-1} + \sum_{k \in I \cap [1, i-1]} x_k)_{i \in [1, n]}$, the subpath from $s$ to $j$ for $j \in [1, n]$, is a valid $\Delta$-restless temporal path with arrival time $\sigma_j + \sum_{k \in I \cap [1, j]} x_k$. Again, we prove this by induction. This is true for $j = 1$. Let us assume that this is true for $j$ such that $1 \le j \le n - 1$. We have, by induction hypothesis, that $P_{sub_j}$ is a valid $\Delta$-restless temporal sj-path in $G^{int}$ with arrival time $\sigma_j + \sum_{k \in I \cap [1, j]} x_k$. The subpath $P_{sub_{j+1}}$ extends the subpath $P_{sub_j}$ by taking arc $e_{j+1}$ at departure time $\tau_j^{dep} = \sigma_j + \sum_{k \in I \cap [1, j]} x_k$. Thanks to the previous observation about earliest and latest arrival time, we have that $\tau_j^{dep} \in [\sigma_j, \tau_j]$, thus we can indeed take arc $e_{j+1}$ at this time. Finally, the arrival time of $P_{sub_{j+1}}$ is $\sigma_j + \sum_{k \in I \cap [1, j]} x_k + \delta_j + x$ with $x = 0$ if $j+1 \notin I$ and $x = x_{j+1}$ otherwise, which is equal to $\sigma_{j+1} + \sum_{k \in I \cap [1, j+1]} x_k$.

**Sufficiency:** Suppose that there is a $\Delta$-restless temporal st-path $P$ in $G^{int}$ with $\Delta = 0$. Let $I = \{i \in [1, n] | e_i^2$ is a timed arc of the path $P\}$. The arrival time of $P$ is $\sigma_n + X + 1$, thus we have that $\sum_{i \in I} \delta_i + \sum_{i \in [1, n] \setminus I} \delta_{i-1} + 1 = \sigma_n + X + 1$. We have that:

$$ 
\begin{align*}
\sum_{i \in I} \delta_i + \sum_{i \in [1, n] \setminus I} \delta_{i-1} &= \sum_{i \in I} (\delta_{i-1} + x_i) + \sum_{i \in [1, n] \setminus I} \delta_{i-1} \\
&= \sum_{i \in [1, n]} \delta_{i-1} + \sum_{i \in I} x_i \\
&= \sigma_n + \sum_{i \in I} x_i
\end{align*}
$$

Thus, $\sum_{i \in I} x_i = X$ and this concludes the proof.

**Claim.** The constructed interval temporal graph $G^{int}$ has interval vertex-IM-width equal to three.

First, observe that for $i \in [1, n - 1]$, $\tau_{int}^{min}(i) = \sigma_{i-1}$ and $\tau_{int}^{max}(i) = \tau_{i+1}$. Note that $\tau_{int}^{min}(i)$ and $\tau_{int}^{max}(i)$ are strictly increasing in $i$ and recall that $\sigma_i = \tau_{i-1} + 1$ for $i \in [1, n]$. Now, observe that for $3 \le i \le n$, $\tau_{int}^{max}(i-2) = \tau_{i-1} < \sigma_i$ and for $1 \le i \le n-3$, $\tau_i < \sigma_{i+1} = \tau_{int}^{min}(i+2)$. Thus, let $\tau$ such that $\sigma_i \le \tau \le \tau_i$ for $3 \le i \le n-3$. The only nodes that can be active over time $\tau$ are $i-1, i$ and $i+1$, so $|F_{\tau}^{int}| \le 3$. For $\sigma_2 \le \tau \le \tau_2$, we have that $\tau_{int}^{max}(0) = \tau_1 < \sigma_2$ so $|F_{\tau}^{int}| \le 3$ as only 1, 2 and 3 can be active over time $\tau$. We also have that $|F_{\tau}^{int}| \le 3$ for $\tau < \sigma_2$ (only 0, 1 and 2 can be active over this time). With the same kinds of observations, we can conclude that $|F_{\tau}^{int}| \le 3$ for $\tau > \tau_{n-3}$. Finally, we have that the interval vertex-IM-width is exactly 3. Indeed, at time $\tau = \sigma_i$ for $1 \le i \le n-1$, we have $F_{\tau}^{int} = \{i-1, i, i+1\}$.

□