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

HAL
open science

# Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics

Justine Cauvi, Nils Morawietz, Laurent Viennot

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

## To cite this version:

Justine Cauvi, Nils Morawietz, Laurent Viennot. Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics. 2025. hal-05293265

HAL Id: hal-05293265

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

Preprint submitted on 1 Oct 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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics*

Justine Cauvi¹, Nils Morawietz², and Laurent Viennot³

¹École Normale Supérieure de Lyon, Lyon, France, Inria, DI ENS, Paris, France

²LaBRI, Université de Bordeaux, France, Institute of Computer Science, Friedrich Schiller University Jena, Germany

³Inria, DI ENS, Paris, France

October 2025

**Abstract**

In this work, we follow the current trend on temporal graph realization, where one is given a property *P* and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property *P*. We consider the problems where as property *P*, we are given a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. That is, we are given a matrix *D* and ask whether there is a temporal graph such that for any ordered pair of vertices (*s*, *t*), *D*<sub>*s*,t*</sub> equals the duration (length, or earliest arrival time, respectively) of any temporal path from *s* to *t* minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings like: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (that is, limited occurrence number per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard.

**Keywords:** network design, temporal paths, foremost paths, fastest paths, shortest paths, non-strict paths, periodic temporal graphs

<footnote>*Supported by the French ANR, projects ANR-22-CE48-0001 (TEMPOGRAL) and ANR-24-CE48-4377 (GO-DASse).</footnote>
# 1 Introduction

Graph realization problems have been studied since the 1960s and consists in finding a static graph that satisfies a desired property *P* or answering that no such graph exists. The earliest example of such a problem is the case of degree sequence realization, where one is given a non-decreasing sequence (*d*₁, ..., *d*ₙ) of natural numbers, and one asks whether there is an undirected graph *G* with vertex set {1, ..., *n*}, such that vertex *i* has degree exactly *d*ᵢ. This problem was introduced by Erdős and Gallai [9] and has been generalized until recently (see, e.g., [2] when ranges are given for each degree). In another early graph realization problem by Hakimi and Yau [13], one is given an *n* × *n* distance matrix *D* and asks whether there is a static graph on *n* vertices, where for each ordered pair (*i*, *j*) of vertices, the shortest path from *i* to *j* has length exactly *D*ᵢⱼ. Since then, graph realization problems were considered in many variations and for many other desirable properties to realize. Recently, Klobas, Mertzios, Molter and Spirakis [17] lifted graph realization problems to the realm of temporal graphs motivated by the realization problem for distance matrices on static graphs. Here, a temporal graph *G* is a finite sequence (*G*₁, ..., *G*₉) of static graphs that are all defined over the same vertex set. Temporal graphs are a valuable tool to model and analyze the behavior of real world dynamic networks [4]. In the problem introduced by Klobas et al. [17], one asks whether our desired property is fulfilled by some temporal graph.<fnref n="1" /> They introduced the following problem:

**FASTEST-PATH TGR:**

**Input:** An *n* × *n* distance matrix *D*.

**Question:** Is there a temporal graph *G* with *n* vertices such that for any ordered pair (*s*, *t*) of vertices, the fastest temporal path<fnref n="2" /> from *s* to *t* has duration *D*ᵣⱼ?

More precisely, the authors considered this problem<fnref n="3" /> where only a single label per edge is allowed and where the temporal graph is periodic, that is, where the same edges repeat every Δ time steps for some period Δ > 0. They showed that the problem is NP-hard and they exhibited an FPT algorithm parameterized by the feedback edge number of the underlying graph<fnref n="4" /> while they showed that it is W[1]-hard when parameterized by the feedback vertex set number. Erlebach, Morawietz and Wolf [11] generalized the problem by allowing each edge to appear up to *ℓ* times per period and proved that this remains NP-hard even on underlying graphs that are trees for *ℓ* = 5. In [20], the authors studied the problem where upper bounds on the fastest paths are given and the underlying graph is a tree. This was further considered for directed graphs by Meusel, Müller-Hannemann and Reinhardt [22]. Further recent papers on temporal graph realization include: designing a temporal graph for which the fastest path should not have duration more than α times the real distance [21], designing a temporal graph which should have a prescribed reachability relation between the vertices [10], and designing a temporal graph for which all pairs of agents can pairwise reach each other via strict temporal paths, with one label per edge, while the degree sequence of the underlying graph is prescribed [3]. All these problems are motivated both from a design perspective, where we aim to design a network with a desired behavior, or from a verification perspective, where we want to verify that the behavior of our network is correct or at least plausible. From the perspective of temporal network design problems, the field is even more vibrant (see, e.g., [1, 7, 8, 15, 16, 18, 19, 24]).

**Our Results.** In this work, we extend the previous work on FASTEST-PATH TGR to the non-strict case (that is, where arbitrary many edges per snapshot can be traversed). Furthermore, we consider the other most famous temporal path metrics Foremost and Shortest (formally defined in Section 2). Roughly speaking, FOREMOST-PATH TGR requires that the earliest arrival time at *t*, minimized over all temporal *st*-path, is equal to *D*ᵣⱼ for each vertex pair (*s*, *t*), whereas

<footnote n="1">¹It is worth mentioning that Göbel, Cerdeira and Veldman [12] considered a connectivity problem that can also be seen as a temporal graph realization problem.</footnote>

<footnote n="2">²A (strict) temporal path can start at any time step and is allowed to traverse only a single edge per snapshot, and its duration is the difference between the starting time and the arrival time (see Section 2).</footnote>

<footnote n="3">³They analyzed the problem under the name SIMPLE (PERIODIC) TEMPORAL GRAPH REALIZATION.</footnote>

<footnote n="4">⁴The underlying graph is uniquely defined via the vertex pairs (*s*, *t*) for which *D*ᵣⱼ = *D*ᵣᵢ = 1.</footnote>
SHORTEST-PATH TGR requires that the number of edges, minimized over all temporal st-path, is equal to $D_{s,t}$ for each vertex pair $(s, t)$. Our main results are as follows:

1. In Section 3 we show that all considered version (strict/non-strict, periodic/non-periodic) of FOREMOST-PATH TGR are polynomial-time solvable, if we are allowed to put an arbitrary number of labels per edge. This is surprising, as all other previously mentioned temporal graph realization problems turn out to be NP-hard (with one exception [3]). In particular, we show that all our algorithms produce a labeling with at most $n$ labels per edge and at most $n^2$ time labels in total, if dealing with a realizable instance. This is somehow tight as some realizable matrices do require $\Omega(n^2)$ time labels or have edges that need at least $\Omega(n)$ time labels.

2. To show the limitations of the tractability, we show that FOREMOST-PATH TGR becomes NP-hard if (i) we are only allowed to assign one label per edge or (ii) the matrix $D$ contains for each vertex pair more than one entry and we are to choose which of these possible values we want to realize. For the latter problem version, we present a single exponential FPT-algorithm when parameterized by the number of entries in $D$ that have more than one possible value.

3. In Section 4 we consider FASTEST-PATH TGR. Among other results, we answer open questions by Klobas et al. [17] and Erlebach et al. [11] about the parameterized complexity of the problem for the vertex cover number. We show that the problem is W[1]-hard when parameterized by this parameter plus the largest entry in the matrix. This result improves significantly over the previous known parameterized hardness result for the feedback vertex set number; in terms of the parameter, the construction, and the length.

4. In Section 5 we consider SHORTEST-PATH TGR and show that the problem for both the strict and the non-strict case are NP-hard, but becomes trivial when considering a periodic temporal graph.

Finally, in Section 6, we conclude with some open questions for future work.

## 2 Preliminaries

For natural numbers $1 \le i \le j$, we let $[i, j] := \{i, i+1, \dots, j\}$ and we define $[j] := [1, j]$.

**(Static) graphs.** An (undirected) graph $G = (V, E)$ is defined by its vertex set $V$ and its edge set $E \subseteq \binom{V}{2}$. Any pair $\{u, v\} \in E$ is called an edge between vertices $u$ and $v$. We also say that $u$ and $v$ are neighbors when $\{u, v\} \in E$. For a vertex set $S \subseteq V$, we define the subgraph of $G$ induced by $S$ as $G[S] := (S, E \cap \binom{S}{2})$. A graph $H = (V', E')$ is a subgraph of $G$ if $V' \subseteq V$ and $E' \subseteq E$. A uv-walk is a sequence $P = (v_0 = u, v_1, \dots, v_k = v)$ of vertices such that $\{v_{i-1}, v_i\}$ is an edge for every $i \in [k]$. We then say that $P$ is a walk from $u$ to $v$ in $G$. Such a walk is called a path if the vertices $v_0, \dots, v_k$ are pairwise distinct.

**Temporal graphs.** A temporal graph is defined by a pair $\mathcal{G} = (G, \lambda)$ where $G = (V, E)$ is a graph, and $\lambda: E \to 2^{\mathbb{N}_{>0}}$ is a labeling that associates to each edge $e \in E$ the set $\lambda(e)$ of (positive) times when $e$ appears. The graph $G$ is called the *underlying graph* of $\mathcal{G}$ and the labeling $\lambda$ is called the *time labeling* of $\mathcal{G}$. When $\mathcal{G}$ is clear from the context, we let $n = |V|$ denote its number of vertices. A temporal edge is a couple $(\{u, v\}, \tau)$ such that $\{u, v\} \in E$ and $\tau \in \lambda(\{u, v\})$. Its appearance time is $\tau$. Given a time label $\tau \in \mathbb{N}_{>0}$, we define the set $E_{\tau} = \{e \in E : \tau \in \lambda(e)\}$ of edges appearing at time $\tau$, and $G_{\tau} = (V, E_{\tau})$ is called the *snapshot* of $\mathcal{G}$ at time $\tau$. The size of a temporal graph can be measured by its number $\sum_{e \in E} |\lambda(e)|$ of time labels. A temporal graph is said to be $\Delta$-periodic if each edge appears periodically with period $\Delta \in \mathbb{N}_{>0}$, that is $\tau \in \lambda(e)$ if and only if $\tau \bmod \Delta \in \lambda(e)$. Such a temporal graph is represented by its list of temporal edges up to time $\Delta$. In the following, we always assume that the vertices of a temporal graph $\mathcal{G}$ are numbered from 1 to $n$. We assume without loss of generality that its vertex set is $V = [n]$. We let $\mathcal{T}\mathcal{G}$ denote the set of all such temporal graphs.
**Temporal paths.** A strict (resp. non-strict) temporal uv-walk is a walk $P = (v_0 = u, v_1, \dots, v_k = v)$ in $G$ which is associated to time labels $(\tau_1, \dots, \tau_k)$ such that $\tau_i \in \lambda(\{v_{i-1}, v_i\})$ for each $i \in [k]$ and $\tau_1 < \dots < \tau_k$ (resp. $\tau_1 \le \dots \le \tau_k$). Equivalently, it can be defined as the sequence of temporal edges $(\{v_0, v_1\}, \tau_1), \dots, (\{v_{k-1}, v_k\}, \tau_k)$ satisfying $\tau_1 < \dots < \tau_k$ (resp. $\tau_1 \le \dots \le \tau_k$). It is said to have length $k$, departure time $\tau_1$, arrival time $\tau_k$, and duration $\tau_k - \tau_1 + 1$ (number of time steps spanned). It is called a temporal uv-path if the vertices $v_0, \dots, v_k$ are pairwise distinct. Note that a strict (resp. non-strict) temporal walk can always be transformed into a strict (resp. non-strict) temporal path by removing loops, and this can only reduce length, arrival time and duration. By default, we consider strict temporal paths, and simply call them temporal paths. We specify non-strict for non-strict temporal paths.

**Temporal path metrics.** Classically, a temporal uv-path is said to be shortest, foremost, or fastest if it has minimum length, arrival time, or duration, respectively among all temporal uv-paths. These notions indeed define some kind of metrics that we now formalize. A distance matrix $D$ is any matrix of size $n \times n$ with values in $\mathbb{N} \cup \{\infty\}$ and that satisfies the following very loose notion of metric: $D_{uv} = 0$ if and only if $u = v$, for all $u, v \in [n]$. It is not assumed that $D$ satisfies any other specific properties. In particular, it may violate the triangle inequality. A temporal path metric is defined as a function $M$ that associates a distance matrix $M(G)$ to any temporal graph $G \in \mathcal{T}G$. Consider for example, a cost function $C$ that associates a positive cost in $\mathbb{N}_{>0}$ to any temporal path given as a sequence of temporal edges (independently of any temporal graph). It defines a temporal path metric by associating to any temporal graph $G \in \mathcal{T}G$ the matrix $C(G)$ (resp. $\mathrm{NS}-C(G)$) such that $C(G)_{uv}$ (resp. $\mathrm{NS}-C(G)_{uv}$) is the minimum cost of a strict (resp. non-strict) temporal uv-path in $G$. We define $C(G)_{uv} := \infty$ (resp. $\mathrm{NS}-C(G)_{uv} := \infty$) if no strict (resp. non-strict) temporal uv-path exists and $C(G)_{uv} := 0$ (resp. $\mathrm{NS}-C(G)_{uv} := 0$) if $u = v$. The foremost, fastest, and shortest notions are indeed associated to the following cost functions: arrival time, duration, and length, respectively. We let Foremost, Fastest, and Shortest denote the corresponding temporal path metrics, respectively. We also let NS-Foremost, NS-Fastest, and NS-Shortest denote the respective variants for non-strict temporal paths. For example, given a temporal graph $G$, and two vertices $u, v$ in $G$, Foremost($G$)$_{uv}$ is the earliest arrival time of a strict temporal uv-path in $G$.

**Temporal graph realization.** Given an integer $n$, the temporal graph realization problem consists in finding a temporal graph with $n$ vertices that satisfies a given property. We assume that this property can be expressed as an input sequence $I \in \{0, 1\}^*$ of bits, given that the vertices of the temporal graph are $1, \dots, n$. More precisely, we define a predicate $P$ as a binary relation between the set $\mathcal{T}G$ of all temporal graphs and the set $\{0, 1\}^*$ of all bit sequences, that is $P$ is a subset of $\mathcal{T}G \times \{0, 1\}^*$. We then say that a temporal graph $G$ satisfies a sequence $I$ of bits for $P$ if $(G, I) \in P$. We equivalently say that $P(G, I)$ is satisfied, or that $G$ is a realization of $I$ for $P$. As a simple example, the lifetime of a temporal graph can be tested by the predicate $P(G, \Lambda) := \max(\cup_{e \in E} \lambda(e)) = \Lambda$ where $G = (G, \Lambda)$ and $\Lambda$ encodes an integer (that we denote also by $\Lambda$ with a slight abuse of notation). That is $P(G, \Lambda)$ is satisfied when $\Lambda$ is the last appearance time of a temporal edge of $G$. Given a predicate $P$ we thus define the following (very general) problem.

**$P$ TEMPORAL GRAPH REALIZATION ($P$ TGR):**

**Input:** A number $n$ and a sequence $I$ of bits.

**Question:** Is there a temporal graph $G$ with $n$ vertices such that $P(G, I)$ is satisfied?

This paper focuses on temporal path metric realization. More precisely, considering a temporal path metric $M \in \{\text{Foremost, Fastest, Shortest, NS-Foremost, NS-Fastest, NS-Shortest}\}$, we define the *M-temporal-path-metric* predicate, or *M-path* for short, as $P(G, I) := M(G) = D$ where the sequence $I$ of bits encodes an $n \times n$ distance matrix $D$ where $n$ is the number of vertices of $G$. For example, Foremost-path TGR is the following problem.

**FOREMOST-PATH TGR:**

**Input:** A number $n$ and an $n \times n$ distance matrix $D$.

**Question:** Is there a temporal graph $G$ with $n$ vertices such that $\mathrm{Foremost}(G) = D$?

When considering an instance of $P$ TGR, we always let $n$ denote the associated number. Note
that, in the case of an *M*-PATH TGR instance, the input has size $\Theta(n^2)$. For brevity, given an input sequence *I* encoding a distance matrix *D*, a realization *G* of *I* for *M*-path is simply called an *M*-realization of *D*. If further the metric *M* is clear from the context, we simply say that *G* is a *realization* of *D* or that *G* realizes *D*.

We also combine *M*-path predicates with additional requirements. In particular, when the input *I* encodes a prescribed (static) graph $G_p$ with *n* nodes, or a period $\Delta$, we define the following additional predicates, respectively:

*   Prescribed($G, G_p$) := the underlying graph of $G$ is a subgraph of $G_p$,

*   Periodic($G, \Delta$) := $G$ is $\Delta$-periodic.

Given two predicates *P*, *Q*, the problem *P Q TGR* asks whether there exists a temporal graph satisfying both *P* and *Q* for a given pair of inputs for *P* and *Q*. For example, *PERIODIC FOREMOST-PATH TGR* asks, given an *n × n* distance matrix *D* and a period *Δ*, whether there exists a *Δ*-periodic temporal graph that is a *Foremost-realization* of *D*. We also sometimes refer to *P Q TGR* as *Q TGR* where *P* is required, especially if *P* is specified in plain text without defining a formal name for it.

## 3 Foremost paths

We first consider the Foremost-path TGR problem. Recall that, given an *n × n* distance matrix *D*, it consists in checking whether there exists a temporal graph *G* whose foremost matrix is *D*, i.e. Foremost(*G*) = *D*. We also consider its non-strict variant (using NS-Foremost), and combinations with Prescribed and Periodic additional requirements. Similar results can be obtained for latest departure using a time-reversal argument. More precisely, the latest-departure temporal path metric is associated to the cost function that assigns the opposite of the departure time to a temporal path. The time-reversal *G'* of a temporal graph *G* is obtained by changing each time label $\tau$ by $\Lambda+1-\tau$ where $\Lambda$ is the maximum time label. As a result any latest-departure temporal *uv*-path in *G* corresponds to a foremost temporal *vu*-path in *G'* where edges are traversed in reverse order. We often implicitly assume that we are given an *n × n* distance matrix *D*.

### 3.1 Polynomial time algorithms

We first show that these main variants of the problem can be solved in polynomial time.

**Strict Foremost paths** In the strict setting, we can indeed state the following.

**Theorem 1** *FOREMOST-PATH TGR can be solved in O(n³ log n) time and O(n²) space. Fur- thermore, if dealing with a realizable instance, a realization with at most n² time labels can be computed with same complexity.*

Note that the above complexity can be expressed as $\tilde{O}(N^{3/2})$ where $N = \Theta(n^2)$ is the size of the input. We also state that the above result is somehow tight in terms of the number of time labels as follows.

**Proposition 1** *There exists a family $(D^n)_{n \in \mathbb{N}_{>0}}$ of $n \times n$ distance matrices that are Foremost-realizable and such that any realization requires $\Omega(n^2)$ time labels.*

**Proof.** Consider the temporal graph $G^n$ with *n* vertices, whose underlying graph is a star rooted at 1, and where, for all $v > 1$, edge {1, *v*} appears at times $nv, nv+1+v, nv+2+v, ..., n^2+v$. Its foremost matrix $D^n$ = Foremost($G^n$) then satisfies $D_{uv}^n = nu + v$ for $u > v > 1$, $D_{uv}^n = nv$ for $1 < u < v$, and $D_{1v}^n = D_{v1}^n = nv$ for $1 < v$. These temporal graphs thus define a family $(D^n)_{n \in \mathbb{N}_{>0}}$ of distance matrices that are foremost realizable and that have $\Omega(n^2)$ pairwise distinct entries. This implies that any foremost realization of such a matrix $D^n$ must have $\Omega(n^2)$ time
labels. The reason is that any foremost realization $\mathcal{G}'$ of an $n \times n$ distance matrix $D$ containing $p$ pairwise distinct entries must have at least $p$ time labels. Indeed, any entry $D_{uv}$ must correspond to some foremost temporal $uv$-path in $\mathcal{G}'$ whose last edge appears at time $D_{uv}$.

**Remark.** The above lower bound also applies to non-strict foremost realizations (using a similar proof with the same families of matrices and temporal graphs). It also holds if we restrict the problem to sparse prescribed graphs with $O(n)$ edges, or even trees, as long as the star is a possible prescribed graph.

**Proposition 2** *There exists a family $(D^n)_{n \in \mathbb{N}_{>0}}$ of $n \times n$ distance matrices that are Foremost-realizable and such that any realization requires at least one edge with $\Omega(n)$ time labels.*

**Proof.** We obtain the results by deriving a similar result from the following problem.

**REACHABILITY GRAPH REALIZATION:**

**Input:** A directed graph $G = (V, A)$.

**Question:** Is there a undirected temporal graph $\mathcal{G}$ with *strict reachability graph* equal to $G$, that is, is there for each pair of distinct vertices $(u, v)$ a strict temporal path from $u$ to $v$ in $\mathcal{G}$ if and only if $(u, v)$ is an arc of $G$?

Erlebach et al. [10, Theorem 4] presented a family $(G^n)_{n \in \mathbb{N}_{>0}}$ of directed graphs on $n$ vertices, for which REACHABILITY GRAPH REALIZATION is a yes-instance and where each temporal graph $\mathcal{G}$ with reachability graph $G^n$ has at least one edge with $\Omega(n)$ labels. Based on this family of graphs, we define our family of distance matrices. For each $n$, let $G^n$ be an arbitrary but fixed temporal graph with reachability graph $G^n$. We define $D^n$ to be the foremost matrix of $G^n$. Clearly, $D^n$ is Foremost-realizable (namely, by $G^n$). It thus remains to show that each temporal graph $\mathcal{G}'$ with foremost matrix $D^n$ has at least one edge with at least $\Omega(n)$ labels. To this end, we show that the reachability graph of $\mathcal{G}'$ equals $G^n$. This then implies the statement due to the properties of $G_n$. By definition of $D^n$, $D^n_{u,v} < \infty$ if and only if $(u, v) \in A$. Thus, the reachability graph of $\mathcal{G}'$ is $G^n$, as the foremost matrix of $\mathcal{G}'$ equals $D^n$.

We now present a simple algorithm for computing a Foremost-realization that leads to $O(n^4)$ time complexity. It is based on the observation that any realization $\mathcal{G}$ of a distance matrix $D$ for Foremost-path must satisfy the following compatibility property.

**Definition 1 (Edge compatibility)** *Given an $n \times n$ distance matrix $D$, a temporal edge $(\{v, w\}, \tau)$ is said to be Foremost-edge-compatible with $D$ if it satisfies: $\text{EdgeCompat}(D, \{v, w\}, \tau) := \forall x \in [n], D_{xv} < \tau \implies D_{xw} \le \tau$ and $D_{xw} < \tau \implies D_{xv} \le \tau$.*

The intuition behind is the following. If an edge $\{v, w\}$ appears at time $\tau$ in a temporal graph $\mathcal{G}$, then any foremost temporal $xv$-path with arrival time less than $\tau$ can be extended by the temporal edge $(\{v, w\}, \tau)$, implying that the foremost arrival time at $w$ is at most $\tau$. Moreover, if $\mathcal{G}$ is a realization of $D$, i.e. $D = \text{Foremost}(\mathcal{G})$, and $D_{xv} < \tau$, then we must have $D_{xw} \le \tau$. By symmetry of edges, we must also have $D_{xw} < \tau \implies D_{xv} \le \tau$. Note that, given an $n \times n$ distance matrix $D$ and a temporal edge $(\{v, w\}, \tau)$, the property $\text{EdgeCompat}(D, \{v, w\}, \tau)$ can easily be tested in $O(n)$ time.

The algorithm consists in checking that for each entry $\tau = D_{uw}$ of $D$, there exists a vertex $v$ such that $D_{uv} < \tau$ and the temporal edge $(\{v, w\}, \tau)$ is Foremost-edge-compatible with $D$. If this is the case, such a temporal edge $(\{v, w\}, \tau)$ is added (see Algorithm 1). This condition is indeed necessary as a foremost temporal $uw$-path in a realization of $D$ must end with such an edge. We will show that this condition is also sufficient, and leads to a construction of a realization with at most $n^2$ time labels.

The correctness of the algorithm comes with defining how a temporal graph can partially realize a matrix as follows.
**Algorithm 1 FOREMOST-PATH TGR**

**Input:** A number $n$ and an $n \times n$ distance matrix $D$

**Output:** YES if there exists a temporal graph $(G, \lambda)$ that is a Foremost-realization of $D$, NO otherwise

1. Let $C$ be the set of all couples $(u, w)$ such that $u \neq w$ and $D_{uw} < \infty$

2. Let $\lambda$ be an empty labeling, i.e. $\lambda(\{u, v\}) = \emptyset$ for all $u, v \in [n]$

3. Return EXISTS($D, C, \lambda$)

4. **procedure EXISTS($D, C, \lambda$)**
   ▷ Given an $n \times n$ distance matrix $D$, $C \subset [n] \times [n]$ and a labeling $\lambda$

5. **for all** $(u, w) \in C$ **do**

6. **if** $\exists v \in [n]$ such that $D_{uv} < D_{uw}$ and EdgeCompat($D, \{v, w\}, D_{uw}$) **then**

7. Add $D_{uw}$ to $\lambda(\{v, w\})$

8. **else**

9. Return NO

10. Return YES

**Definition 2** A temporal graph $\mathcal{G}$ is said to be Foremost-compatible with $D$ if $D \leq \text{Foremost}(\mathcal{G})$, i.e. $D_{uv} \leq \text{Foremost}(\mathcal{G})_{uv}$ for all $u, v \in [n]$, and all temporal edges of $\mathcal{G}$ are Foremost-edge-compatible with $D$.

First note that any Foremost-realization of $D$ must be Foremost-compatible with $D$.

**Lemma 1** If $\mathcal{G}$ is a Foremost-realization of $D$, then $\mathcal{G}$ is Foremost-compatible with $D$.

**Proof.** First, we clearly have $D \leq \text{Foremost}(\mathcal{G})$ since $\mathcal{G}$ is a Foremost-realization of $D$. Second, suppose for the sake of contradiction that some temporal edge $(\{v, w\}, \tau)$ is not Foremost-edge-compatible with $D$. That is, without loss of generality, there exists a vertex $x$ such that $D_{xv} < \tau$ and $D_{xw} > \tau$. Any foremost temporal $xv$-path in $\mathcal{G}$ must arrive in $v$ at time $D_{xv}$. However, this temporal path can be extended with $(\{v, w\}, \tau)$, yielding a temporal $xw$-walk arriving at time $\tau < D_{xw}$, contradicting the fact that $\mathcal{G}$ is a Foremost-realization of $D$.

Note also that an $n$-vertex empty temporal graph, i.e. without any time label, is always $D$ compatible as it does not contain any temporal edge. Moreover, Foremost-compatibility is preserved by addition of a Foremost-edge-compatible temporal edge as stated below.

**Lemma 2** If a temporal graph $\mathcal{G} = (G, \lambda)$ is Foremost-compatible with $D$ and a temporal edge $(\{v, w\}, \tau)$ is Foremost-edge-compatible with $D$, then the temporal graph $\mathcal{G}'$ obtained from $\mathcal{G}$ by adding label $\tau$ to edge $\{v, w\}$ is also Foremost-compatible.

**Proof.** We just need to prove $D \leq \text{Foremost}(\mathcal{G}')$. Suppose for the sake of contradiction that there exists $x \neq y$ such that $D_{xy} > \text{Foremost}(\mathcal{G}')_{xy}$, i.e., $D_{xy}$ is greater than the arrival time of a foremost temporal $xy$-path $P$ in $\mathcal{G}'$. Consider the first temporal edge $(\{z, z'\}, \sigma')$ of $P$ such that $P$ arrives in $z$ at time $\sigma \geq D_{xz}$ but arrives in $z'$ before $D_{xz'}$, i.e. $\sigma' < D_{xz'}$. Such an edge must exist since $P$ arrives in $y$ before $D_{xy}$ and $D_{xx} = 0$. The (strict) temporal path definition implies $\sigma < \sigma'$ which thus yields $D_{xz} < \sigma'$. As $D_{xz'} > \sigma'$, $(\{z, z'\}, \sigma')$ cannot be Foremost-edge-compatible with $D$. This contradicts either the Foremost-edge-compatibility of $(\{v, w\}, \tau)$ if $(\{z, z'\}, \sigma') = (\{v, w\}, \tau)$, or the Foremost-compatibility of $\mathcal{G}$ otherwise.

**Lemma 3** If $\mathcal{G}$ is a Foremost-realization of $D$, then for any entry $\tau = D_{uw}$ with $u \neq w$, there exists a vertex $v$ such that $D_{uv} < \tau$ and $(\{v, w\}, \tau)$ is Foremost-edge-compatible with $D$.
**Proof.** It suffices to consider the last temporal edge ({v, w}, τ) of a foremost temporal uw-path in a Foremost-realization G of D. It must satisfy τ = D<sub>uw</sub> since G is a realization of D. Since it is a strict temporal path, it arrives in v before τ, implying D<sub>uv</sub> < τ. Moreover, ({v, w}, τ) is Foremost-edge-compatible with D by Lemma 1.

**Proof.** [Proof of Theorem 1] If there exists a Foremost-realization of D, the algorithm must find a suitable temporal edge ( {v, w} , D<sub>uw</sub> ) for each pair ( u, w ) by Lemma 3. It thus returns NO, only when no such realization exists. Let K<sub>n</sub> denote the complete graph with vertex set [ n ]. Lemma 2 implies that Algorithm 1 preserves the invariant that ( K<sub>n</sub> , λ ) is Foremost-compatible with D. If the algorithm returns YES, the constructed temporal graph G = ( K<sub>n</sub> , λ ) is thus Foremost-compatible with D, implying D ≤ Foremost( G ). We now prove that we indeed must have D = Foremost( G ). Suppose for the sake of contradiction that there are pairs ( u, w ) satisfying D<sub>uw</sub> < Foremost( G )<sub>uw</sub>. Consider such a pair ( u, w ) such that D<sub>uw</sub> is minimum. When this pair was considered, the algorithm added to G a temporal edge ( {v, w} , D<sub>uw</sub> ) satisfying D<sub>uv</sub> < D<sub>uw</sub>. By the choice of ( u, w ), we have D<sub>uv</sub> = Foremost( G )<sub>uv</sub>. Now, if we extend a foremost temporal uv- path in G with ( {v, w} , D<sub>uw</sub> ), we obtain a temporal uw-walk arriving at time D<sub>uw</sub> in contradiction with D<sub>uw</sub> < Foremost( G )<sub>uw</sub>. This concludes the proof of correctness of Algorithm 1.

Its time complexity is clearly O ( n 4 ) as for each of the n 2 pairs ( u, w ), we consider at most n vertices v and the test for the Foremost-edge-compatibility of ( { v, w } , D$_{uw}$ ) takes O ( n ) time. To obtain O ( n 3 log n ), we use an interval tree data-structure (see, e.g., [5]). It can store n intervals and querying whether a value τ is in one of these intervals can be answered in O (log n ) time. It uses O ( n ) space and can be constructed in O ( n log n ) time. To benefit from such a data-structure, we consider all pairs ( u, w ) with fixed w consecutively. Before processing them, we compute for each vertex v two interval trees T$_{v}$ and T ′ v where T$_{v}$ (resp. T ′ v ) contains the n intervals [ D$_{xv}$ + 1 , D$_{xw}$ − 1] (resp. [ D$_{xw}$ + 1 , D$_{xv}$ − 1]) for x ∈ [ n ], ignoring empty intervals. The Foremost-edge-compatibility of a temporal edge ( { v, w } , τ ) can then be tested in O (log n ) time by checking that neither T$_{v}$ nor T ′ v has an interval containing τ . The reason is that any vertex x violating D$_{xv}$ < τ = ⇒ D$_{xw}$ ≤ τ satisfies D$_{xv}$ < τ < D$_{xw}$ in which case τ belongs to the interval of T$_{v}$ associated to x . Analogously, any vertex x violating D$_{xw}$ < τ = ⇒ D$_{xv}$ ≤ τ is associated to an interval of T ′ v that contains τ . Constructing the interval trees takes O ( n 2 log n ) time while processing each ( u, w ) pair now takes O ( n log n ) time as it mainly consists in n Foremost-edge- compatibility tests. The overall complexity is thus O ( n 3 log n ) time using O ( n $^{2}$) space.

Note that the algorithm adds a time label to an edge { v, w } at most once for each vertex u , when considering either ( u, w ) or ( u, v ), depending on whether D$_{uv}$ < D$_{uw}$ or D$_{uv}$ < D$_{uv}$ . The Foremost-realization computed by Algorithm 1 thus has at most n time labels per edge, and at most n 2 time labels in total.

**Non-strict foremost paths** We have a similar result for the non-strict case.

**Theorem 2** NS-FOREMOST-PATH TGR can be solved in O ( n 3 log n ) time and O ( n $^{2}$) space. Fur- thermore, if dealing with a realizable instance, a realization with at most n 2 time labels can be computed with same complexity.

A slight modification of Algorithm 1 suffices, replacing EdgeCompat( D , { v, w } , τ ) with:

$$
\text{NSEdgeCompat}(D, \{v, w\}, \tau) := \forall x \in [n], D_{xv} \le \tau \iff D_{xw} \le \tau.
$$

Following the above definition, we say that a temporal edge ( { v, w } , τ ) is NS-Foremost- edge- compatible with D if it satisfies NSEdgeCompat( D , { v, w } , τ ). Similarly, a temporal graph G is said to be NS-Foremost- compatible with D if D ≤ NS-Foremost( G ) and all temporal edges of G are NS-Foremost-edge-compatible. The following variations of Lemmas 1 and 2 have almost identical proofs which are omitted.

**Lemma 4** If G is a NS-Foremost-realization of D , then G is NS-Foremost-compatible with D .
**Lemma 5** If a temporal graph $\mathcal{G} = (G, \lambda)$ is NS-Foremost-compatible with $D$ and a temporal edge $(\{v, w\}, \tau)$ is NS-Foremost-edge-compatible with $D$, then the temporal graph $\mathcal{G}'$ obtained from $\mathcal{G}$ by adding label $\tau$ to edge $\{v, w\}$ is also NS-Foremost-compatible.

The main difference with the strict setting concerns Lemma 3 which has the following variation.

**Lemma 6** If $\mathcal{G}$ is a NS-Foremost-realization of $D$, then for any entry $\tau = D_{uw}$ with $u \neq w$, there exists a vertex $v$ such that $D_{uv} < \tau$ and $(\{v, w\}, \tau)$ is NS-Foremost-edge-compatible with $D$.

**Proof.** It suffices to consider a non-strict foremost temporal $uw$-path $P$. The path $P$ must end with one or more temporal edges with time label $\tau = D_{uw}$ since $\mathcal{G}$ is a NS-Foremost-realization of $D$. Consider the first such temporal edge $(\{v, w'\}, \tau)$. This choice implies that $P$ arrives in $v$ before $\tau$, implying $D_{uv} < \tau$. We now show that $(\{v, w\}, \tau)$ is NS-Foremost-edge-compatible with $D$. For the sake of contradiction, suppose without loss of generality that there exists a vertex $x$ such that $D_{xv} \le \tau$ and $D_{xw} > \tau$. Consider a non-strict foremost temporal $xv$-path $P'$ in $\mathcal{G}$. The path $P'$ must arrive in $v$ at time $D_{xv}$ since $\mathcal{G}$ is a NS-Foremost-realization of $D$. As $D_{xv} \le \tau$, it can be extended by the suffix of $P$ consisting of temporal edges appearing at time $\tau$. This leads to a non-strict temporal $xw$-walk arriving at time $\tau$. This implies $D_{xw} = \text{NS-Foremost}(\mathcal{G})_{xw} \le \tau$, which contradicts $D_{xw} > \tau$.

Note that the temporal edge $(\{v, w\}, \tau)$ is not necessarily in $\mathcal{G}$, it can be a shortcut for a non-strict temporal path where all edges are traversed at time $\tau$. In comparison, the temporal edge proposed in the proof of Lemma 3 is in the considered realization.

The rest of the proof of Theorem 2 is almost identical to that of Theorem 1 and is omitted.

**Foremost paths in a periodic temporal graph** We now consider the variant where the realization is required to be periodic. Recall that PERIODIC FOREMOST-PATH TGR is given a period $\Delta$ in addition to $D$, and asks whether there exists a $\Delta$-periodic temporal graph $\mathcal{G}$ such that $\text{Foremost}(\mathcal{G}) = D$. We obtain similarly the following.

**Theorem 3** PERIODIC FOREMOST-PATH TGR can be solved in $O(n^3 \log n)$ time and $O(n^2)$ space. Furthermore, if dealing with a realizable instance, a realization with at most $n^2$ time labels within any period can be computed with same complexity.

The proof is almost identical to that of Theorem 1 using the following notion of edge-compatibility:

$$ \text{PeriodEdgeCompat}(D, \{v, w\}, \tau) := \forall i \in \mathbb{Z}, \text{EdgeCompat}(D, \{v, w\}, \tau + i\Delta). $$

Note that the above condition is restrictive only for $\tau + i\Delta > 0$ as $\text{EdgeCompat}(D, \{v, w\}, \tau')$ is always satisfied for $\tau' \le 0$.

The correctness of the resulting variant of Algorithm 1 mainly comes from the following observation. Any $\Delta$-periodic realization must satisfy the above condition for each temporal edge $(\{v, w\}, \tau)$ as each periodic appearance of $\{v, w\}$ at $\tau + i\Delta$ must be Foremost-edge-compatible by Lemma 1.

Note that the above condition can again be performed in $O(n)$ time by checking both $\text{PeriodECDir}(D, v, w, \tau)$ and $\text{PeriodECDir}(D, w, v, \tau)$ where $\text{PeriodECDir}(D, v, w, \tau, \Delta) := \forall x \in [n], \forall i \in \mathbb{Z}, D_{xv} < i\Delta + \tau \Rightarrow D_{xw} \le i\Delta + \tau$. In the latter test, it is sufficient to test for each $x \in [n]$ only the first index $i = \lfloor \frac{D_{xv}-\tau}{\Delta} + 1 \rfloor$ satisfying $D_{xv} < i\Delta + \tau$. The complexity thus remains the same.

**Foremost paths with prescribed graph** We now consider the variant in which a prescribed graph $G_p = ([n], E_p)$ is additionally given as input, and the realization is required to have a subgraph of $G_p$ as underlying graph. We let $N_p(v) = \{w : \exists \{v, w\} \in E_p\}$ denote the set of neighbors of any vertex $v \in [n]$ in $G_p$. Recall that the problem is formally defined as follows.
### PRESCRIBED FOREMOST-PATH TGR:

**Input:** A number $n$, an $n \times n$ distance matrix $D$, a prescribed graph $G_p = ([n], E_p)$.

**Question:** Is there a temporal graph $G = (G, \lambda)$ with $n$ vertices such that Foremost($G$) equals $D$ and $G$ is a subgraph of $G_p$?

We obtain similarly the following.

**Theorem 4** *PRESCRIBED FOREMOST-PATH TGR can be solved in $O(n^3 \log n)$ time and $O(n^2)$ space. Furthermore, if dealing with a realizable instance, a realization with at most $n^2$ time labels can be computed with same complexity.*

Again, the proof is almost identical to that of Theorem 1 using the following notion of edge-compatibility that takes into account that edges must be in the prescribed graph:

$$ \text{PrescribedEdgeCompat}(D, \{v, w\}, \tau) := \text{EdgeCompat}(D, \{v, w\}, \tau) \text{ and } \{u, w\} \in E_p. $$

### Non-strict foremost paths with a prescribed graph
We now consider the non-strict version of the prescribed foremost realization problem. Recall that in the adaptation of Algorithm 1 for the non-strict case, we were using the fact that, in a NS-Foremost-realization $G$ of $D$, a non-strict temporal path where all edges are traversed at time $\tau$ from a node $v$ to a node $w$ can be replaced by a single temporal edge $(\{v, w\}, \tau)$ (see Lemma 6). The main difficulty here is that the shortcut temporal edge might not be part of the prescribed graph. Indeed, the condition $D_{uv} < D_{uw}$ at Line 6 of Algorithm 1 now becomes problematic as the prescribed graph may impose to add a temporal edge $(\{v, w\}, D_{uw})$ such that $D_{uv} = D_{uw}$ to fulfill an entry $D_{uw}$. Moreover, the order in which we can fulfill entries $D_{uw_1} = \dots = D_{uw_p}$ in this manner may depend on the prescribed graph. A naive solution would be to let each edge $\{v, w\} \in E_p$ appear at all times $\tau \notin \{0, \infty\}$ appearing in $D$ that satisfy $\text{NSEdgeCompat}(D, \{v, w\}, \tau)$. It would then suffice to check if the resulting temporal graph is an NS-Foremost-realization of $D$. However, this would result in a poor complexity and possibly $\Theta(n^4)$ time labels overall. We can still solve the problem with a better complexity and a tight number of time labels as stated below.

**Theorem 5** *PRESCRIBED NS-FOREMOST-PATH TGR can be solved in $O(n^2m)$ time and $O(n^2)$ space, where $m$ is the number of edges of the prescribed graph. Furthermore, if dealing with a realizable instance, a realization with at most $n^2$ time labels can be computed with same complexity.*

The result is a consequence of Algorithm 2 which scan the set $\{d_1, \dots, d_p\}$ of entries of $D$ excluding 0 and $\infty$ (in any order).

The set $C_i$ of all couples $(u, w)$ with same value $D_{uw} = d_i$ is processed as a whole. As with the prescribed non-strict variant of Algorithm 1, we add label $d_i$ to an edge $\{v, w\}$ if we find a neighbor $v$ of $w$ in $G_p$ such that the edge with time label $D_{uw}$ is edge-compatible with $D$ according to $\text{NSEdgeCompat}$ and $u$ can reach $v$ before $w$ according to $D$, i.e., $D_{uv} < D_{uw}$. However, this is not sufficient as some pairs $(u, w)$ might need to use an edge $\{w', w\}$ at time $d_i$ where $(u, w')$ is another couple of $C_i$. For that purpose, for each couple $(u, w)$ where a compatible edge $\{v, w\}$ with $D_{uv} < D_{uw}$ was found, we start a BFS like search to scan and mark other couples $(u, w')$ that can be reached at time $d_i$ through $w$ based on the following lemma.

**Lemma 7** If $G$ is a NS-Foremost-realization of $D$, then for any entry $\tau = D_{uw}$ with $u \neq w$, there exists vertices $v_1, \dots, v_k$ with $k \ge 2$ and $v_k = w$ such that $D_{uv_1} < \tau$ and such that the temporal edges $(\{v_i, v_{i+1}\}, \tau)$ for $i \in [k-1]$ are all NS-Foremost-edge-compatible with $D$ and are all in $G$.

**Proof.** It suffices to consider a non-strict foremost temporal $uw$-path in $G$ and its longest suffix $(\{v_1, v_2\}, \tau), \dots, (\{v_{k-1}, w\}, \tau)$ of temporal edges with time label $\tau = D_{uw}$. All these temporal edges are NS-Foremost-edge-compatible by Lemma 4.

**Proof.** We now prove the correctness of Algorithm 2. First, suppose that there exists a NS-Foremost-realization $G$ such that its underlying graph is a subgraph of $G_p$. We prove that
<caption>**Algorithm 2** Prescribed NS-FOREMOST-PATH TGR</caption>

**Input:** A number $n$, an $n \times n$ distance matrix $D$, a prescribed graph $G_p = ([n], E_p)$
**Output:** YES if there exists a temporal graph $(G_p, \lambda)$ that is a NS-Foremost-realization of $D$, NO otherwise
1: Let $d_1, \dots, d_p$ be an enumeration of the set $\{D_{uw} : u \neq w \text{ and } D_{uw} \neq \infty\}$
2: Let $\lambda$ be an empty labeling, i.e. $\lambda(\{u, v\}) = \emptyset$ for all $\{u, v\} \in E_p$
3: $Mark_{uw} := \text{False}$ for all $u, w \in [n]$
4: **for all** $i = 1, \dots, p$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;Let $C_i$ be the set of all couples $(u, w)$ such that $D_{uw} = d_i$
6: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $(u, w) \in C_i$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\neg Mark_{uw}$ **then**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists v \in N_p(w)$ such that $D_{uv} < D_{uw}$ and $\text{NSEdgeCompat}(D, \{v, w\}, d_i)$ **then**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Mark_{uw} := \text{True}$
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $d_i$ to $\lambda(\{v, w\})$
11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;BFS$(u, w, d_i)$
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists (u, w) \in C_i$ such that $\neg Mark_{uw}$ **then**
13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Return NO
14: Return YES
15: **procedure** BFS$(u, w, d_i)$
16: &nbsp;&nbsp;&nbsp;&nbsp;Add $w$ to queue $Q$
17: &nbsp;&nbsp;&nbsp;&nbsp;**while** $Q \neq \emptyset$ **do**
18: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Let $v := \text{pop}(Q)$
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for all** $w' \in N_p(v)$ such that $D_{uw'} = d_i$ and $\neg Mark_{uw'}$ **do**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{NSEdgeCompat}(D, \{v, w'\}, d_i)$ **then**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Mark_{uw'} := \text{True}$
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $d_i$ to $\lambda(\{v, w'\})$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $w'$ to $Q$
&nbsp;&nbsp;&nbsp;&nbsp;▷ Given two nodes $u, w$ and the time $d_i = D_{uw}$

all couples $(u, w)$ satisfying $0 < D_{uw} < \infty$ are marked. Consider any couple $(u, w) \in C_i$ and let us prove that it will be marked, i.e. $Mark_{uw}$ will be set to True. Applying Lemma 7 with $\tau = d_i = D_{uw}$, there exists vertices $v_1, \dots, v_k$ with $v_k = w$ and $D_{uv_1} < d_i$ such that each temporal edge $(\{v_j, v_{j+1}\}, d_i)$ is in $G$ and is NS-Foremost-edge-compatible with $D$. We have the following properties:

(i) All edges $\{v_j, v_{j+1}\}$ for $j \in [k-1]$ are in $E_p$ since the underlying graph of $G$ is a subgraph of $G_p$.

(ii) $D_{uv_j} \le d_i$ for all $j \in \{2, \dots, k\}$ since $D_{uv_1} = \text{NS-Foremost}(G)_{uv_1} < d_i$ and a non-strict foremost temporal $uv_1$-path can be extended by $(\{v_j, v_{j+1}\}, d_i)$ for $j \in [k-1]$, leading to $d_i \ge \text{NS-Foremost}(G)_{uv_j} = D_{uv_j}$ for $1 < j \le k$.

Let $j$ be the last index in $[k]$ such that $D_{uv_j} < d_i$. Since $D_{uw} = D_{uv_k} = d_i$, we have $j < k$ and $D_{uv_{j+1}} = d_i$. As $\{v_j, v_{j+1}\}, d_i$ is NS-Foremost-edge-compatible with $D$, the algorithm must mark $(u, v_{j+1})$ at Line 9 if it has not been already marked during a call to BFS at Line 21. Suppose for the sake of contradiction that $(u, w)$ is not marked. Let $j'$ be the last index in $j+1, \dots, k-1$ which is marked. This happens either at Line 9 or Line 21. In both cases, $v_{j'}$ is enqueued in $Q$ during a call to BFS, and later popped at Line 18. The algorithm then scans $w' = v_{j'+1}$ and must mark it at Line 21 since $D_{uv_{j'+1}} = d_i$ by (ii) and the choice of $j$, and $(\{v_{j'}, v_{j'+1}\}, d_i)$ is NS-Foremost-edge-compatible with $D$, in contradiction with $Mark_{uv_{j'+1}} = \text{False}$ by the choice of $j'$. We thus conclude that all couples $(u, w)$ with $0 < D_{uw} < \infty$ are marked, and the algorithm thus returns YES.

Now, note the following invariant: $(G_p, \lambda)$ is NS-Foremost-compatible at any point of the execution of the algorithm. This is a direct consequence of Lemma 5. We thus have $D \le$
NS-Foremost((G<sub>p</sub>, λ)). We prove that we indeed have D = NS-Foremost((G<sub>p</sub>, λ)). Suppose for the sake of contradiction that there exists a couple (u, w) satisfying D<sub>uw</sub> < NS-Foremost((G<sub>p</sub>, λ))<sub>uw</sub>. Consider such a couple (u, w) such that D<sub>uw</sub> is minimum. Consider the index *i* such that D<sub>uw</sub> = *d*<sub>i</sub>. Moreover, consider the first couple (u, w') which is marked among the couples (u, w) ∈ C<sub>i</sub> satisfying D<sub>uw</sub> < NS-Foremost((G<sub>p</sub>, λ))<sub>uw</sub>. It must have been marked when finding a NS-Foremost-edge-compatible temporal edge ({v, w'}, *d*<sub>i</sub>) which has been added to (G<sub>p</sub>, λ). If this happens at Line 9, we have D<sub>uv</sub> < D<sub>uw'</sub> by the choice of v, implying D<sub>uv</sub> = NS-Foremost((G<sub>p</sub>, λ))<sub>uv</sub> by minimality of D<sub>uw</sub>. Otherwise, it happens at Line 21, and (u, v) was already marked since v was popped at Line 18. This implies D<sub>uv</sub> = NS-Foremost((G<sub>p</sub>, λ))<sub>uv</sub> by the choice of w'. In both cases we have D<sub>uv</sub> = NS-Foremost((G<sub>p</sub>, λ))<sub>uv</sub>, and extending a non-strict foremost temporal uv-path in (G<sub>p</sub>, λ) by the temporal edge ({v, w'}, *d*<sub>i</sub>) leads to a non-strict temporal uw'-walk arriving at time *d*<sub>i</sub> = D<sub>uw'</sub> in contradiction with D<sub>uw'</sub> < NS-Foremost((G<sub>p</sub>, λ))<sub>uw'</sub>. This concludes the proof of correctness of Algorithm 2.

The complexity of the algorithm comes from the following observation. For each couple (u, w), we consider the neighbors v of w at most twice: once when considering (u, w) at Line 6 in the main loop, and once when w is popped during a BFS call. The reason is that a node w is enqueued only if (u, w) has just been marked and (u, w) was not marked before. For each such neighbor x, we perform a test of edge compatibility in O(n). The overall complexity is thus O(∑<sub>uw</sub> |N<sub>p</sub>(w)|n) = O(n<sup>2</sup> ∑<sub>w</sub> |N<sub>p</sub>(w)|) = O(n<sup>2</sup>m).

Finally, a time label is added to an edge {v, w} at most once for each node u. Indeed, if D<sub>uv</sub> < D<sub>uw</sub> (resp. D<sub>uw</sub> < D<sub>uv</sub>), it can only be added when fulfilling (u, w) (resp. (u, v)). Otherwise, if D<sub>uv</sub> = D<sub>uw</sub>, it can only be added when one of v, w is marked and not the other, i.e., when fulfilling either (u, w) or (u, v). The constructed realization (G<sub>p</sub>, λ) thus has at most n<sup>2</sup> time labels in total. ■

## 3.2 Limits of polynomial-time algorithms for FOREMOST-PATH TGR

In this section, we show several additional requirements on instances of FOREMOST-PATH TGR for which the problem becomes NP-hard.

**Foremost paths with a single time-label per edge** The problem becomes hard when we restrict the number of allowed labels per edge to one.

**Theorem 6** *FOREMOST-PATH TGR is NP-hard when allowing at most one label per edge.*

**Proof.** We reduce from SAT.

**SAT:**

**Input:** A formula *F* in CNF.

**Question:** Is *F* satisfiable?

Let *F* be an instance of SAT where no clause contains the same variable both positively and negatively. Under these restrictions, SAT is NP-hard [14].

**Construction.** Let *X* be the variable set of *F* and let *C* denote the clauses of *F*. To obtain an instance *D* of FOREMOST-PATH TGR, we first define the vertex set over which the matrix *D* is defined. We set $V := \{x, \bar{x} | x \in X\} \cup C \cup \{\top, \bot\}$.

We now describe the entries of *D*. See Figure 1 for an illustration. Let $c \in C$. We set $D_{c,\top} := 3$. Furthermore, for each variable $x$ that occurs positively in $c$, we set $D_{c,x} := 2$ and $D_{\bar{x},c} := 2$. Similarly, for each variable $x$ that occurs negatively in $c$, we set $D_{c,\bar{x}} := D_{\bar{x},c} := 2$ and $D_{x,c} := 2$. For each variable $x$, we set $D_{x,\bar{x}} := D_{\bar{x},x} := 1$, and for each literal $\ell$, we set $D_{\ell,\top} := D_{\top,\ell} := D_{\ell,\bot} := D_{\bot,\ell} := 2$. Furthermore, for any two literals $\ell$ and $\ell'$ that belong to different variables, we set $D_{\ell,\ell'} := D_{\ell',\ell} := 2$. We set $D_{\top,\bot} := 1$. All other entries of *D* are set to 4. Note that this includes the entry $D_{\top,c}$ for each clause $c$. This completes the definition of *D*.

**Intuition.** The difficulty of the constructed instance comes from the realizability of the entries from clause vertices to $\top$. Each clause $c$ can only reach literals that are contained in $c$ in time 2,
<figure><img src="image_4.png" /><figcaption>Figure 1: The variable gadget from the reduction of Theorem 6 with a true assignment on the left side and a false assignment on the right side. Here, the clause $c_i$ contains the literal $x$ and the clause $c_j$ contains the literal $\bar{x}$. The matrix only shows the entries of value smaller than 4. Each clause vertex $c_i$ aims to reach $\top$ by time 3, but for each variable $x$, one of the edges $\{x, \top\}$ or $\{\bar{x}, \top\}$ has to receive label 2.</figcaption></figure>

but has to reach $\top$ by time 3. This implies that for some literal $\ell$ in $c$, the edge $\{\ell, \top\}$ needs to receive label 3, as the direct edge $\{c, \top\}$ cannot receive a label smaller than 4 due to $D_{\top,c} = 4$. Moreover, for each variable $x$, the entries of $D$ between $\{x, \bar{x}\}$ and $\{\top, \bot\}$ ensure that at least one of $\{x, \top\}$ or $\{\bar{x}, \top\}$ has to receive label 2. As we require to have at most one label per edge, note that the edge $\{\ell, \top\}$ can receive label 3 to fulfill $D_{c,\top}$ only if it did not already receive label 2. Hence, we can derive a truth assignment for the edges between each variable gadget and the vertex $\top$ (by checking which of the edges $\{x, \top\}$ or $\{\bar{x}, \top\}$ does not have label 2), which we show to be a satisfying assignment of the formula in each realization of $D$.

**Correctness.** We now show that $F$ is satisfiable if and only if $D$ is realizable with a single label per edge.

(=$\Leftarrow$) Let $\mathcal{G} = ((V, E), \lambda)$ be a realization of $D$ where each edge receives a single label. Note that we can assume that $E = \binom{V}{2}$, as the largest entry of $D$ is 4, that is, each non-edge can receive label 4 while preserving the property of being a realization for $D$.

First, we show that the edges between each variable gadgets and $\{\top, \bot\}$ encodes a truth assignment.

**Claim 1** For each variable $x \in X$, $\lambda(\{x, \top\}) = 2$ or $\lambda(\{\bar{x}, \top\}) = 2$.

*Proof.* Let $x \in X$. Since $\mathcal{G}$ realizes $D$ and $D_{x,\top} = 2$, there is a temporal path $P$ from $x$ in $\mathcal{G}$ that reaches $\top$ at time 2. As $D_{x,\bar{x}}$ and $D_{\bar{x},x}$ are the only entries of $D$ of value 1 that include $x$, the temporal path $P$ that realizes $D_{x,\top} = 2$ consists of either (i) the single edge $\{x, \top\}$ with label 2, or (ii) the edge $\{x, \bar{x}\}$ with label 1 followed by the edge $\{\bar{x}, \top\}$ with label 2. $\triangleleft$

Based on this claim, we define a truth assignment of the variables of $X$ as follows. For each variable $x \in X$, we set variable $x$ to True if and only if $\lambda(\{x, \top\}) \neq 2$. We show that this assignment satisfies $F$. To this end, we show that each clause is satisfied by the assignment. Let $c$ be a clause. Since $D_{c,\top} = 3$ and $\mathcal{G}$ realizes $D$, there is a temporal path $P$ from $c$ that reaches $\top$ at time 3. By $D_{\top,c} = 4$, we get $\lambda(\{c, \top\}) > 3$. This implies that $P$ has length at least 2. Let $q$ be the first internal vertex of $P$. Since each entry of $D$ including $c$ has value at least 2, $P$ has length exactly 2 since we consider strict temporal paths and $P$ ends in time 3. That is, $P = (c, q, \top)$, $\lambda(\{c, q\}) = 2$, and $\lambda(\{q, \top\}) = 3$. By $\lambda(\{c, q\}) = 2$, we get that $D_{c,q} \leq 2$, which implies that $q$ is a literal that is contained in clause $c$. Thus, literal $q$ is set to True by our truth assignment, since $\lambda(\{q, \top\}) = 3 \neq 2$. Hence, clause $c$ is satisfied by the truth assignment, which implies that $F$ is satisfied.
(⇒) Let $\pi$ be a satisfying truth assignment for $F$. We define a labeling $\lambda$ for the complete graph $G$ with vertex set $V$, such that $G := (G, \lambda)$ realizes $D$. We initialize $\lambda$ by setting $\lambda(e) := 1$ for each edge $e \in \{\top, \bot\}\cup\{\{x, \bar{x}\} \mid x \in X\}$. This realizes all entries of $D$ of value 1. Next, we define the set $E_2$ of edges that receive label 2. For any two literals $\ell$ and $\ell'$ that do not belong to the same variable, we add the edge $\{\ell, \ell'\}$ to $E_2$. This implies that all entries of value 2 between literal vertices are realized. For each clause $c$ and each literal $\ell$ of $c$, we add $\{c, \ell\}$ to $E_2$. This realizes all entries of $D$ of value 2 including any clause vertex. This is due to the fact that $c$ and literal $\ell$ can pairwise reach each other at time 2 via the direct edge and the negated literal $\ell$ of $\ell$ can reach $c$ via the path using edges $\{\ell, \ell\}$ at time 1 and $\{\ell, c\}$ at time 2. The only entries of $D$ of value 2 that are not yet realized are all entries between $\{\top, \bot\}$ and any literal $\ell$. Let $x \in X$. If $x$ is assigned to True by $\pi$, we add the edges $\{x, \bot\}$ and $\{\bar{x}, \top\}$ to $E_2$. Otherwise, we add the edges $\{x, \top\}$ and $\{\bar{x}, \bot\}$ to $E_2$. In both cases, all vertices of $\{x, \bar{x}\}$ can reach all vertices of $\{\top, \bot\}$ and vice versa at time 2, since there is a perfect matching at time 2 between these sets and the edges $\{x, \bar{x}\}$ and $\{\top, \bot\}$ receive label 1. Thus, via the edges of $E_2$ and the edges with label 1, all entries of $D$ of value at most 2 are realized. Next, we define the edges $E_3$ that we need to realize all entries of value 3 in $D$. Note that these are exactly the entries $D_{c,\top}$ for each clause $c$. If $x$ is assigned to True by $\pi$, we add the edges $\{x, \top\}$ to $E_3$ and otherwise, we add the edges $\{\bar{x}, \top\}$ to $E_3$. By definition of $E_2$, these edges have not received any label yet. Moreover, since $\pi$ is a satisfying assignment, these edges realize all entries of value 3, since for each clause $c$, there is a literal $\ell$ of $c$ that is assigned True by $\pi$. That is, $\{c, \ell\} \in E_2$ and $\{\ell, \top\} \in E_3$, which implies that there is a path from $c$ to $\top$ that arrives at time 3. Finally, all other edges receive label 4. This clearly realizes all remaining entries of $D$. Moreover, as $E_1, E_2$, and $E_3$ are pairwise disjoint, each edge receives exactly one time label. Hence, $G$ realizes $D$. ■

**Foremost paths in ranges** Given a temporal path metric $M$, we define the following variant of $M$-PATH TGR where the input sequence encodes a matrix $D$ of ranges. More precisely, each entry is supposed to represent a range $[\ell, r] = \{\ell, \dots, r\}$ of positive integers. The Ranged-$M$-path predicate is then defined as $P(G, D) := M(G)_{uv} \in D_{uv}$ for all $u, v \in [n]$. For example, this leads to the following problem for $M$ = Foremost.

**RANGED-FOREMOST-PATH TGR:**

**Input:** A number $n$ and an $n \times n$ matrix $D$ of ranges.

**Question:** Is there a temporal graph $G$ such that $\text{Foremost}(G)_{uv} \in D_{uv}$ for all $u, v \in [n]$?

An entry $(u, v)$ is said to be *undetermined* if $D_{uv} = [\ell, r]$ with $\ell \neq r$. Note that when the number $k$ of undetermined entries is zero, this problem is equivalent to FOREMOST-PATH TGR, for which we presented a polynomial-time algorithm. We now analyze the complexity of RANGED-FOREMOST-PATH TGR and its non-strict variant RANGED-NS-FOREMOST-PATH TGR with a focus on the parameter $k$.

**Theorem 7** *RANGED-FOREMOST-PATH TGR and RANGED-NS-FOREMOST-PATH TGR are both NP-hard. Moreover, believing the ETH, neither RANGED-FOREMOST-PATH TGR nor RANGED-NS-FOREMOST-PATH TGR can be solved in $2^{o(k)} \cdot n^{O(1)}$ time, where $k$ is the number of undetermined entries of $D$.*

**Proof.** We present a straight forward reduction from REACHABILITY GRAPH REALIZATION.

**REACHABILITY GRAPH REALIZATION:**

**Input:** A directed graph $G = (V, A)$.

**Question:** Is there a undirected temporal graph $G$ with *strict reachability graph* equal to $G$, that is, is there for each pair of distinct vertices $(u, v)$ a strict temporal path from $u$ to $v$ in $G$ if and only if $(u, v)$ is an arc of $G$?

Erlebach et al. [10] showed that REACHABILITY GRAPH REALIZATION is NP-hard and cannot be solved in $2^{o(|A|)} \cdot n^{O(1)}$ time, unless the ETH fails. Let $G = (V, A)$ be an instance of REACHABILITY GRAPH REALIZATION. We define an instance $D$ of RANGED-FOREMOST-PATH TGR as follows. For each pair $(u, v)$ of distinct vertices, we set $D_{u,v} := [1, n^3]$ if $(u, v) \in A$ and $D_{u,v} := n^3+1$,
otherwise. This completes the definition of $D$. Note that the number of undetermined entries in $D$ equals $|A|$. We show that $D$ is realizable if and only if $G$ is a yes-instance of REACHABILITY GRAPH REALIZATION.

(⇒) Let $G' := (G', \lambda')$ be a realization for $D$. Moreover, let $G''$ denote the temporal graph obtained by limiting $G'$ to the first $n^3$ time steps. Since $G'$ realizes $D$, this implies that for each pair $(u, v)$ of distinct vertices, there is a temporal path from $u$ to $v$ in $G''$ if and only if $D_{u,v} = [1, n^3]$. The latter is the case if and only if $(u, v)$ is an arc of $G$ by definition of $D$. This implies that the strict reachability graph of $G''$ is equal to $G$. Thus, $G$ is a yes-instance of REACHABILITY GRAPH REALIZATION.

( ⇐ ) Let $G' = (G' = (V, E'), \lambda')$ be a temporal graph with strict reachability graph that is equal to $G$. By Erlebach et al. [10, Lemma 3], we can assume that each of the at most $n^2$ edges of $G'$ receives at most $n$ labels each. Thus, we can assume that the lifetime of $G'$ is at most $n^3$, since edgeless snapshots can safely be removed. Hence, for each pair $(u, v)$ of distinct vertices, there is a temporal path from $u$ to $v$ in $G'$ if and only if $(u, v) \in A$, which is the case if and only if $D_{u,v} = [1, n^3]$ by definition of $D$. This implies that $G'$ realizes all entries of $D$ with range $[1, n^3]$ and does not create a temporal path with arrival time less than $n^3 + 1$ for any vertex pair $(u, v)$ with $D_{u,v} = n^3 + 1$. Thus, by additionally assigning label $n^3 + 1$ to each edge $e \in \binom{V}{2}$, the resulting temporal graph also realizes all entries of $D$ of value $n^3 + 1$. Consequently, $D$ is realizable.

This completes the proof that RANGED-FOREMOST-PATH TGR is NP-hard. The ETH lower bound now follows from the fact that REACHABILITY GRAPH REALIZATION has this ETH lower bound for $|A|$ and $|A|$ equals the number $k$ of undetermined entries in $D$.

We can also show the hardness and ETH lower bound for the non-strict version, i.e., RANGED-NS-FOREMOST-PATH TGR, by instead reducing from NON-STRICT REACHABILITY GRAPH REALIZATION. The problem is the same as REACHABILITY GRAPH REALIZATION, except that one asks for a temporal graph with non-strict reachability graph equal to $G$ instead of a temporal graph with strict reachability graph equals to $G$. By Erlebach et al. [10] NON-STRICT REACHABILITY GRAPH REALIZATION is also NP-hard and cannot be solved in $2^{o(|A|)} \cdot n^{O(1)}$ time, unless the ETH fails.

For the strict setting, we obtain hardness even when each range has size at most 2.

**Theorem 8** *RANGED-FOREMOST-PATH TGR is NP-hard even when each range has length at most two and the largest value of the matrix is 5.*

**Proof.** We reduce from SAT.

Let $F$ be an instance of SAT where no clause contains the same variable both positively and negatively. Under these restrictions, SAT is NP-hard [14].

**Construction.** Let $X$ be the variable set of $F$ and let $C$ denote the clauses of $F$. To obtain an instance $D$ of RANGED-FOREMOST-PATH TGR, we first define the vertex set over which the matrix $D$ is defined. We set $V := \{x, \bar{x} | x \in X\} \cup C \cup \{\top, \bot\}$.

We now describe the entries of $D$. See Figure 2 for an illustration. Let $c \in C$. We set $D_{c,\top} := 2$ and $D_{c,\bot} := 3$. Furthermore, for each variable $x$ that occurs positively in $c$, we set $D_{c,x} := D_{x,c} := 1$ and $D_{c,\bar{x}} := 2$. Similarly, for each variable $x$ that occurs negatively in $c$, we set $D_{c,\bar{x}} := D_{\bar{x},c} := 1$ and $D_{c,x} := 2$. Let $x$ be a variable. We set $D_{x,\bar{x}} := D_{\bar{x},x} := 1$, $D_{x,\top} := D_{\bar{x},\top} := 2$, and $D_{x,\bot} := D_{\bar{x},\bot} := 3$. Furthermore, we set $D_{\top,x} := D_{\bar{\top},x} := [2, 3]$ and $D_{\bot,x} := D_{\bar{\bot},x} := [3, 4]$. All other entries of $D$ are set to 5. Note that this includes the entry $D_{\top,\bot}$ and the entry $D_{\top,c}$ for each clause $c$. This completes the definition of $D$.

**Intuition.** The difficulty of the constructed instance comes from the realizability of the entries from clause vertices to $\top$. Each clause $c$ can only reach literals that are contained in $c$ in time 1, but has to reach $\top$ by time 2. This implies that for some literal $\ell$ in $c$, the edge $\{\ell, \top\}$ needs to receive label 2. Moreover, for each variable $x$, the entries of $D$ ensure that at least one of $\{x, \bot\}$ or $\{\bar{x}, \bot\}$ has to receive label 3. As we do not allow for paths from $\top$ to $\bot$ prior to time 5, not both edges $\{x, \top\}$ and $\{\bar{x}, \top\}$ can receive label 2, as this would create a path of arrival time 3
<figure><img src="image_5.png" /><figcaption>Figure 2: The variable gadget from the reduction of Theorem 8 with a true assignment on the left side and a false assignment on the right side. The matrix only shows the entries of value smaller than 5. Each clause vertex $c_i$ aims to reach $\top$ by time 2 and $\bot$ by time 3, but $\top$ and $\bot$ should pairwise not reach each other prior to time 5.</figcaption></figure>

from $\top$ to $\bot$. Thus, the edges between each variable gadget and the vertex $\top$ encodes a truth assignment, which we show to be a satisfying assignment of the formula in each realization of $D$.

**Correctness.** We now show that $F$ is satisfiable if and only if $D$ is realizable.

(=$\Leftarrow$) Let $\mathcal{G} := (G, \lambda)$ be a temporal graph that realizes $D$, where $G$ is a static graph with vertex set $V$. We show that there is a satisfying assignment for $F$. To this end, we analyze the labels on edges incident with $\top$ and $\bot$. Since each entry in $D$ has value at most 5, we can assume without loss of generality that $G$ is a clique and each edge of $G$ exists in time step 5. Consider the edges $E := \{e \in \binom{V}{2}, \min \lambda(e) < 5\}$. Since $\mathcal{G}$ realizes $D$, for each edge $\{u, v\} \in E$, we get that $D_{u,v} < 5$ and $D_{v,u} < 5$. Since $D_{\top,\bot} = 5$ and for each clause $c$, $D_{\top,c} = D_{\bot,c} = 5$, the only edges of $E$ incident with $\top$ or $\bot$ have literals as their other endpoint.

**Claim 2** For each variable $x \in X$, $2 \notin \lambda(\{x, \top\})$ or $2 \notin \lambda(\{\bar{x}, \top\})$.

*Proof.* Let $x \in X$. Since $\mathcal{G}$ realizes $D$ and $D_{x,\bot} = 3$, there is a temporal path $P$ from $x$ in $\mathcal{G}$ that reaches $\bot$ at time 3. As already discussed, the only edges incident with $\bot$ that can receive a label smaller than 5 are edges for which the other endpoint is a vertex corresponding to a literal. Thus, the predecessor of $\bot$ in $P$ is a literal $\ell$. As $D_{x,\ell'} = 5$ for each literal $\ell' \notin \{x, \bar{x}\}$, $\ell$ is either $x$ or $\bar{x}$. This implies that $3 \in \lambda(\{x, \bot\})$ or $3 \in \lambda(\{\bar{x}, \bot\})$. If $3 \in \lambda(\{x, \bot\})$, then $2 \notin \lambda(\{x, \top\})$, as otherwise, there is a temporal path from $\top$ in $\mathcal{G}$ that reaches $\bot$ at time $3 < 5 = D_{\top,\bot}$. Similarly, if $3 \in \lambda(\{\bar{x}, \bot\})$, then $2 \notin \lambda(\{\bar{x}, \top\})$, as otherwise, there is a temporal path from $\top$ in $\mathcal{G}$ that reaches $\bot$ at time $3 < 5 = D_{\top,\bot}$. Consequently, $2 \notin \lambda(\{x, \top\})$ or $2 \notin \lambda(\{\bar{x}, \top\})$. $\triangleleft$

Based on this property, we now define a truth assignment. For each variable $x \in X$, we set variable $x$ to True if and only if $2 \in \lambda(\{x, \top\})$. We show that this assignment satisfies $F$. To this end, we show that each clause is satisfied by the assignment. Let $c$ be a clause. Since $D_{c,\top} = 2$ and $\mathcal{G}$ realizes $D$, there is a temporal path $P$ from $c$ that reaches $\top$ at time 2. By $D_{\top,c} = 5$, we get $\min \lambda(\{c, \top\}) = 5$. This implies that $P$ has length 2. Hence, there is a vertex $q$, such that $P = (c, q, \top)$. Moreover, $1 \in \lambda(\{c, q\})$ and $2 \in \lambda(\{q, \top\})$, since we consider strict temporal paths and $P$ ends in time 2. By $1 \in \lambda(\{c, q\})$, we get that $D_{c,q} = D_{q,c} = 1$. This property only holds for the vertices $q$ that represent the literals that are contained in clause $c$. That is, $q = \ell$ for some literal that is contained in $c$. Recall that $P$ reaches $\top$ at time 2. This implies that $2 \in \lambda(\{\ell, \top\})$. Hence, if $\ell$ is a positive literal $x$, then variable $x$ is set to True by the truth
assignment. Otherwise, if $\ell$ is a negative literal $\bar{x}$, then the variable $x$ is set to False by the truth assignment, due to Claim 2 and the fact that $2 \in \lambda(\{\ell, \top\})$. In both cases, clause $c$ is satisfied by the truth assignment, which implies that $F$ is satisfied.

(⇒) Let $\pi$ be a satisfying truth assignment for $F$. We define a labeling $\lambda$ for the complete graph $G$ with vertex set $V$, such that $\mathcal{G} := (G, \lambda)$ realizes $D$. We initialize $\lambda$ by setting $\lambda(e) := \{5\}$ for each edge $e$ of the complete graph $G$. Note that this guarantees that between each pair of vertices there is always a temporal paths with arrival time at most 5. Since this is the largest entry in $D$, we guarantee to not realize journeys of too early arrival time in this way. In the following, we describe how to add further labels to the edges, to realize all entries smaller than 5 in $D$. Let $x$ be a variable. We add the labels 1, 2, 3, and 4 to the edge $\{x, \bar{x}\}$. If $x$ is assigned to True by $\pi$, we add label 2 to edge $\{x, \top\}$ and label 3 to edge $\{\bar{x}, \bot\}$. Otherwise, that is, if $x$ is assigned to False by $\pi$, we add label 2 to edge $\{\bar{x}, \top\}$ and label 3 to edge $\{x, \bot\}$. Finally, if variable $x$ occurs positively in a clause $c$, we add label 1 to the edge $\{x, c\}$, and if variable $x$ occurs negatively in a clause $c$, we add label 1 to the edge $\{\bar{x}, c\}$. This completes the definition of $\lambda$. We now show that this labeling realizes $D$.

Note that (i) only the labels 1 and 5 are on edges incident with clause vertices, (ii) only the labels 2 and 5 are on edges incident with vertex $\top$, and (iii) only the labels 3 and 5 are on edges incident with vertex $\bot$. This implies that each temporal path $P$ with arrival time smaller than 5 only uses vertices that correspond to literals as internal vertices. Moreover, since for any two distinct variables $x$ and $y$, there is no edge with label smaller than 5 between any vertex of $\{x, \bar{x}\}$ and any vertex of $\{y, \bar{y}\}$, each temporal path with arrival time less than 5 uses only edges of the subgraph depicted in Figure 2 for some variable $x$. That is, each such temporal path $P$ uses only edges of $G_x$ for some variable $x$, where $G_x := G[\{x, \bar{x}, \top, \bot\} \cup C_x \cup C_{\bar{x}}]$ with $C_x := \{c \in C \mid x \in c\}$ and $C_{\bar{x}} := \{c \in C \mid \bar{x} \in c\}$. Note that when restricting the edges of $G_x$ to those that receive at least one label smaller than 5, the resulting static graph is a tree. It is easy to verify that no temporal path in this tree arrives faster than specified in $D$. In the following, we thus only focus on showing that there is always a temporal path in $\mathcal{G}$ with exactly the arrival time as specified by $D$. We only focus on those entries of value smaller than 5, as the entries of value 5 are clearly realized by the fact that each edge receives label 5.

Let $x$ be a variable. Since $1 \in \lambda(\{x, c\})$ for each clause $c \in C_x$, the entries $D_{c,x}$ and $D_{x,c}$ of value 1 are realized. Similarly, since $1 \in \lambda(\{\bar{x}, c\})$ for each clause $c \in C_{\bar{x}}$, the entries $D_{c,\bar{x}}$ and $D_{\bar{x},c}$ of value 1 are realized. Moreover, since the edge $\{x, \bar{x}\}$ receives labels 1 and 2, the entry $D_{x,\bar{x}}$ of value 1 are realized, as well as the entries $D_{c,\bar{x}}$ and $D_{c',x}$ of value 2 for each clause $c \in C_x$ and each clause $c' \in C_{\bar{x}}$. Note that this implies that all entries of value less than 5 involving only clause and literal vertices are realized. Now, recall that $3 \in \lambda(\{x, \bot\})$ or $3 \in \lambda(\{\bar{x}, \bot\})$. Since $x$ and $\bar{x}$ can pairwise reach each other in time 1, and each vertex of $C_x \cup C_{\bar{x}}$ can reach vertex $x$ and vertex $\bar{x}$ at time at most 2, there are paths that arrive at vertex $\bot$ at time 3 for all vertices of $\{x, \bar{x}\} \cup C_x \cup C_{\bar{x}}$. This realizes all entries $D_{q,\bot}$ of value 3 with $q \in \{x, \bar{x}\} \cup C_x \cup C_{\bar{x}}$. Since each clause contains at least one variable, this thus implies that all entries of the form $D_{v,\bot}$ are realized for each vertex $v$ of $G$. Now consider the entries $D_{\bot,x}$ and $D_{\bot,\bar{x}}$. By $3 \in \lambda(\{x, \bot\})$ or $3 \in \lambda(\{\bar{x}, \bot\})$, vertex $\bot$ can reach one of the vertices $x$ or $\bar{x}$ at time 3 and the other vertex at time 4, since edge $\{x, \bar{x}\}$ has label 4. Thus, the entries $D_{\bot,x}$ and $D_{\bot,\bar{x}}$ of range [3, 4] are realized. It remains to consider the entries involving $\top$. Recall that $2 \in \lambda(\{x, \top\})$ and $2 \in \lambda(\{\bar{x}, \top\})$. By the fact that edge $\{x, \bar{x}\}$ receives label 1 and 3, this implies that (i) both $x$ and $\bar{x}$ can reach $\top$ at time 2 and (ii) vertex $\top$ can reach one of the vertices $x$ or $\bar{x}$ at time 2 and the other one at time 3. Thus, (i) the entries $D_{x,\top}$ and $D_{\bar{x},\top}$ of value 2 are realized and (ii) the entries $D_{\top,x}$ and $D_{\top,\bar{x}}$ of range [2, 3] are realized. Hence, all entries involving $x$ or $\bar{x}$ are realized. It remains to consider the entry $D_{c,\top}$ of value 2 for each clause $c \in C$. Let $c \in C$. Since the truth assignment $\pi$ satisfies $F$, there is a literal $\ell$ contained in $c$ that is assigned to True by $\pi$. By definition of $\lambda$, $1 \in \lambda(\{c, \ell\})$ and $2 \in \lambda(\{\ell, \top\})$. This implies that vertex $c$ can reach $\top$ at time 2 and thus that the entry $D_{c,\top}$ of value 2 is realized. Hence, all entries of value smaller than 5 of $D$ are realized by $\mathcal{G}$. Consequently, $\mathcal{G}$ realizes $D$. ■
**FPT algorithm for RANGED-FOREMOST-PATH TGR** We now propose a dynamic programming algorithm solving RANGED-FOREMOST-PATH TGR which has running time $2^{O(k) \cdot n^{O(1)}}$. Note that this is tight in the sense that a significantly faster algorithm would contradict ETH by Theorem 7.

**Theorem 9** *RANGED-FOREMOST-PATH TGR can be solved in $O(k^23^k n^4)$ time and $O(2^k + n^2)$ space, where k is the number of undetermined entries of D.*

In the following, we let $\ell_{uw}$ (resp. $r_{uw}$) denote the lower bound (resp. upper bound) of entry $(u, w)$, i.e., $D_{uw} = [\ell_{uw}, r_{uw}]$. Recall that an entry $(u, w)$ is undetermined if $\ell_{uw} \neq r_{uw}$. The set of such undetermined entries is denoted by *Undet* and its size is denoted by *k*.

The above result is a consequence of Algorithm 3, which is based on the following observation.

**Lemma 8** *If there exists a realization $\mathcal{G}$ of $D$ for Ranged-Foremost-path, then there is a realization $\mathcal{G}'$ of $D$ for Ranged-Foremost-path such that all time labels of $\mathcal{G}'$ are in the set $\{\ell_{uw} + j \mid u \neq w \text{ and } 0 \le j \le k\}$, where $k$ is the number of undetermined entries of $D$.*

**Proof.** Let $\mathcal{G}$ be a realization of $D$ for Ranged-Foremost-path. Without loss of generality, we can assume that all time labels of $\mathcal{G}$ are coefficients of its foremost matrix Foremost($\mathcal{G}$). Indeed, let $(\{u, v\}, \tau)$ be a temporal edge of $\mathcal{G}$ whose time label $\tau$ is not a coefficient of its foremost matrix Foremost($\mathcal{G}$). Let $P$ be a foremost temporal path from a vertex $x$ to a vertex $y$ that traverses $\{u, v\}$ from $u$ to $v$ at time $\tau$, without loss of generality. We have that there exists a foremost temporal $xv$-path $P'$ arriving at time Foremost($\mathcal{G}$)$_{xv} < \tau$ as $\tau$ is not a coefficient of Foremost($\mathcal{G}$). The temporal path $P'$ extended with the suffix of $P$ that starts at node $v$ is thus a foremost temporal $xy$-walk that does not use temporal edge $(\{u, v\}, \tau)$. Thus, deleting temporal edge $(\{u, v\}, \tau)$ preserves the fact that $\mathcal{G}$ is a realization of $D$ for Ranged-Foremost-path.

Thus, let $\mathcal{G} = (\mathcal{G}, \lambda)$ be a realization of $D$ such that all the time labels of $\mathcal{G}$ are coefficients of its foremost matrix Foremost($\mathcal{G}$). Let $\ell_1 < \dots < \ell_p$ be the lower bounds of the entries of $D$ sorted in increasing order (excluding 0 and $\infty$). Let $C_{\mathcal{G}}$ be the set of coefficients of the foremost matrix of $\mathcal{G}$ that are not 0 or $\infty$. For all $i \in [p]$, we denote $\ell_i^1, \dots, \ell_i^{k_i}$ the coefficients in $C_{\mathcal{G}}$ sorted in increasing order that are strictly between $\ell_i$ and $\ell_{i+1}$, with the convention that $\ell_{p+1} = \infty$. In other words, we have the following increasing sequence: $0 < \ell_1 < \ell_1^1 < \dots < \ell_1^{k_1} < \ell_2 < \dots < \ell_i < \ell_i^1 < \dots < \ell_i^{k_i} < \ell_{i+1} < \dots < \ell_{p+1} = \infty$. First, observe that, for all $i \in [p]$, the number $k_i$ of coefficients in $C_{\mathcal{G}}$ that are between the lower bounds $\ell_i$ and $\ell_{i+1}$ is at most $k$, where $k$ is the number of undetermined entries of $D$. We construct the temporal graph $\mathcal{G}'$ as follows: for each $i \in [p]$ and $j \in [k_i]$, we replace all time labels $\ell_i^j$ of $\mathcal{G}$ by the label $\ell_i + j$. We then have that all time labels of $\mathcal{G}'$ are in the set $\{\ell_{uw} + j \mid u \neq w \text{ and } 0 \le j \le k\}$. Let us prove that $\mathcal{G}'$ is still a realization of $D$. We show that for all $(u, w) \in [n] \times [n]$, if Foremost($\mathcal{G}$)$_{uw} = \ell_i^j$ for some $i \in [p]$ and $j \in [k_i]$ then Foremost($\mathcal{G}'$)$_{uw} = \ell_i + j$, and Foremost($\mathcal{G}'$)$_{uw}$ = Foremost($\mathcal{G}$)$_{uw}$ otherwise. This comes from the fact that the order of the sequence $0 < \ell_1 < \ell_1^1 < \dots < \ell_1^{k_1} < \ell_2 < \dots < \ell_i < \ell_i^1 < \dots < \ell_i^{k_i} < \ell_{i+1} < \dots < \ell_{p+1} = \infty$ is preserved, i.e. $0 < \ell_1 < \ell_1 + 1 < \dots < \ell_1 + k_1 < \ell_2 < \dots < \ell_i < \ell_i + 1 < \dots < \ell_i + k_i < \ell_{i+1} < \dots < \ell_{p+1} = \infty$. The transformation thus preserves temporal paths. It remains to prove that, for each $(u, w)$ such that Foremost($\mathcal{G}$)$_{uw} = \ell_i^j$ and Foremost($\mathcal{G}$)$_{uw} = \ell_i + j$ for some $i \in [p]$ and $j \in [k_i]$, $\ell_i + j$ is in $D_{uw}$. As Foremost($\mathcal{G}$)$_{uw} = \ell_i^j$ and $\mathcal{G}$ realizes $D$, we have $\ell_{uv} \le \ell_i^j \le r_{uw}$. As $\ell_{uv}$ is a lower bound of an entry of the matrix $D$, we also have that $\ell_{uv} \le \ell_i$. We conclude with $\ell_{uv} \le \ell_i \le \ell_i + j \le \ell_i^j \le r_{uw}$. ■

The general idea of the algorithm is to process all possible times in $\{\ell_{uw} + j \mid u \neq w \text{ and } 0 \le j \le k\}$ in increasing order and guesses which undetermined entries can be realized at the current time. More precisely, letting $0 < \tau_1 < \dots < \tau_m$ denote these times, we maintain, for each $i \in [m]$, a table $R[\cdot, i]$ such that $R[S, i]$ for $S \subseteq \text{Undet}$ is equal to True if and only if there exists a temporal graph $\mathcal{G}$ with time labels in $\{\tau_1, \dots, \tau_i\}$ such that:
* for each $(u, w) \in S$, the earliest arrival time of any foremost temporal *uw*-path in $G$ is in $D_{uw}$ and is at most $\tau_i$,

* for each $(u, w)$ with $\ell_{uw} = r_{uw} = \tau \le \tau_i$, the earliest arrival time of any foremost temporal *uw*-path in $G$ is $\tau$,

* for all other entries $(u, w)$, there is no temporal *uw*-path in $G$.

As a consequence of Lemma 8, we have that $R[\text{Undet}, m] = \text{True}$ if and only if there exists a temporal graph that realizes $D$ for Ranged-Foremost-path.

When processing time $\tau_i$, we consider tri-partitions $S, T, U$ of the set $\text{Undet}$ where $S$ represents the set of undetermined entries that must be realized before time $\tau_i$, $T$ represents the set of undetermined entries that must be realized at time $\tau_i$ and $U$ the set of undetermined entries that must be realized after time $\tau_i$. We first check that $R[S, i-1]$ is equal to True and that all entries $(u, w)$ in $T$ are such that $\tau_i \in D_{uw}$. If this is the case, we have to check that we can realize the entries in $T$ with time $\tau_i$, as well as entries $(u, w)$ such that $l_{uw} = r_{uw} = \tau_i$, by completing a temporal graph associated to $R[S, i-1]$. To do so, we proceed similarly to Algorithm 1, by looking for a suitable vertex $v$ when dealing with the entry $(u, w)$, such that adding the temporal edge $(\{v, w\}, \tau_i)$ creates a temporal *uw*-path with arrival time $\tau_i$ without creating any temporal path that arrives too early. This is verified in the algorithm using the following definition of edge compatibility:

* $\text{RangeEdgeCompat}(D, \{v, w\}, \tau, S, T) := \text{RangeEdgeCompatDir}(D, v, w, \tau, S, T)$ and $\text{RangeEdgeCompatDir}(D, v, w, \tau, S, T)$,

* where $\text{RangeEdgeCompatDir}(D, v, w, \tau, S, T) := \forall x \in [n], (r_{xv} < \tau \text{ or } (x, v) \in S) \implies (r_{xw} \le \tau \text{ or } (x, w) \in S \cup T)$.

If we can indeed complete such a temporal graph, then we set $R[S \cup T, i]$ to True. Note that, similarly to Algorithm 1, we do not need explicit access to such a temporal graph as we probe it through $D, S, T$.

The correctness of the algorithm relies on the following lemma about edge compatibility:

**Lemma 9** If $G$ is a realization of $D$ for Ranged-Foremost-path, then for all temporal edges $(\{v, w\}, \tau)$ in $G$, we have that $\text{RangeEdgeCompat}(D, \{v, w\}, \tau, S, T)$ is satisfied, where $S = \{(u, w) \in \text{Undet} \mid \text{Foremost}(G)_{uw} < \tau\}$ is the set of undetermined entries whose earliest arrival time in $G$ is before $\tau$ and $T = \{(u, w) \in \text{Undet} \mid \text{Foremost}(G)_{uw} = \tau\}$ is the set of undetermined entries whose earliest arrival time in $G$ is at $\tau$.

**Proof.** Suppose for the sake of contradiction that some temporal edge $(\{v, w\}, \tau)$ does not satisfy $\text{RangeEdgeCompat}(D, \{v, w\}, \tau, S, T)$. That is, without loss of generality, there exists a vertex $x$ such that $(r_{xv} < \tau$ or $(x, v) \in S)$ and $(r_{xw} > \tau$ and $(x, w) \notin S \cup T)$. By definition of the set $S$, and since $G$ is a realization of $D$, the condition $(r_{xv} < \tau$ or $(x, v) \in S)$ means that there exists a foremost temporal $xv$-path $P$ arriving at a time $\sigma < \tau$. Extending this path with $(\{v, w\}, \tau)$ yields a temporal $xw$-walk arriving at time $\tau$. If $(x, w)$ is an undetermined entry of $D$, this contradicts the fact that $(x, w) \notin S \cup T$. Otherwise, we have $\ell_{xw} = r_{xw}$, and $\ell_{xw} > \tau$ contradicts the fact that $G$ is a realization of $D$ for Ranged-Foremost-path. ■

**Proof.**[Proof of Theorem 3] Let us first prove that if there exists a temporal graph that realizes $D$ for Ranged-Foremost-path, then the algorithm returns YES. Let $G$ be such a realization with all time labels being in the set $\{\ell_{uw} + j \mid u \ne w \text{ and } 0 \le j \le k\}$. Such a temporal graph exists by Lemma 8. Let us denote $\tau_1 < \dots < \tau_m$ the times in $\{\ell_{uw} + j \mid u \ne w \text{ and } 0 \le j \le k \text{ and } \ell_{uw} < \infty\}$. Let $S_i = \{(u, w) \in \text{Undet} \mid \text{Foremost}(G)_{uw} = \tau_i\}$ be the set of undetermined entries $(u, w)$ such that a foremost temporal *uw*-path in $G$ arrives at time $\tau_i$. First, observe that $\cup_{k=1}^m S_k = \text{Undet}$. Let us prove by induction on $i$ that after the $i$th iteration of the main loop, we have $R[\cup_{k=1}^i S_k, i] = \text{True}$. We indeed have $R[\emptyset, 0] = \text{True}$. For $i \ge 1$, when the tri-partition $\cup_{k=1}^{i-1} S_k, S_i, \text{Undet} \setminus \cup_{k=1}^i S_k$ is considered at Line 9, we have:
**Algorithm 3 Ranged-Foremost-path TGR**

**Input:** A number $n$, an $n \times n$ matrix $D$ of ranges

**Output:** YES if there exists a temporal graph that realizes $D$ for Ranged-Foremost-path, NO otherwise

1. Let $\mathit{Undet} = \{(u, w) \in [n] \times [n], \ell_{uw} \neq r_{uw}\}$ be the set of undetermined entries of $D$

2. Let $k = |\mathit{Undet}|$ be the number of undetermined entries of $D$

3. Let $0 < \tau_1 < \dots < \tau_m$ be the times in $\{\ell_{uw} + j \mid u \neq w \text{ and } 0 \le j \le k \text{ and } \ell_{uw} < \infty\}$

4. Set $R[S, 0] := \text{False}$ for all $S \subseteq \mathit{Undet}$

5. $R[\emptyset, 0] := \text{True}$

6. **for all** $i = 1$ to $m$ **do**

7. $R[S, i] := \text{False}$ for all $S \subseteq \mathit{Undet}$

8. Let $C_i$ be the set of all $(u, w)$ such that $\ell_{uw} = r_{uw} = \tau_i$

9. **for all** tri-partition $S, T, U$ of $\mathit{Undet}$ such that $R[S, i-1]$ and $\forall (u, w) \in T, \tau_i \in D_{uw}$ **do**

10. **if** $\mathit{EXISTS}(D, C_i, \tau_i, S, T)$ **then**

11. $R[S \cup T, i] := \text{True}$

12. Return $R[\mathit{Undet}, m]$

13. **procedure** $\mathit{EXISTS}(D, C, \tau, S, T)$ ▷ Given an $n \times n$ matrix $D$ of ranges, a time $\tau$, $C, S, T \subseteq [n] \times [n]$

14. **for all** $(u, w) \in C \cup T$ **do**

15. **if** $\mathfrak{D}v \in [n]$ such that $(r_{uv} < \tau$ or $(u, v) \in S)$ and $\mathit{RangeEdgeCompat}(D, \{v, w\}, \tau, S, T)$ **then**

16. Return False

17. Return True

• $R[\cup_{k=1}^{i-1} S_k, i-1] = \text{True}$ by induction hypothesis.

• $\forall (u, w) \in S_i, \tau_i \in D_{uw}$ by definition of $S_i$ and the fact that $\mathcal{G}$ is a Ranged-Foremost- realization of $D$.

• $\mathit{EXISTS}(D, C_i, \tau_i, \cup_{k=1}^{i-1} S_k, S_i) = \text{True}$ where $C_i$ is the set of all $(u, w)$ such that $\ell_{uw} = r_{uw} = \tau_i$. Indeed, let $(u, w) \in C_i \cup S_i$. We have that there exists a foremost temporal *uw*-path $P$ in $\mathcal{G}$ that arrives at time $\tau_i$. Consider the predecessor $v$ of $w$ in $P$. By Lemma 9, we have that $\mathit{RangeEdgeCompat}(D, \{v, w\}, \tau_i, \cup_{k=1}^{i-1} S_k, S_i)$ is satisfied. Moreover, either $(u, v)$ is an undetermined entry, and in this case we have $(u, v) \in \cup_{k=1}^{i-1} S_k$, or $l_{uv} = r_{uv}$ and in this case we have $r_{uv} < \tau$. Thus, the procedure $\mathit{EXISTS}$ returns True.

As a consequence, $R[\cup_{k=1}^{i} S_k, i]$ is set to True. This implies that $R[\mathit{Undet}, i]$ is set to True by considering the last index $i = m$. This concludes the proof that the algorithm returns NO only when no realization exists.

Let us now prove that if the algorithm returns YES, then there exists a temporal graph $\mathcal{G}$ that realizes $D$ for Ranged-Foremost-path. If the algorithm returns YES, we have a sequence of subsets of $\mathit{Undet} S_1, \dots, S_m$ such that:

(i) $\cup_{k=1}^{m} S_k = \mathit{Undet}$,

(ii) $R[\cup_{k=1}^{i} S_k, i] = \text{True}$ for each $i \in [m]$,

(iii) $\forall (u, w) \in S_i, \tau_i \in D_{uw}$,

(iv) $\mathit{EXISTS}(D, C_i, \tau_i, \cup_{k=1}^{i-1} S_k, S_i) = \text{True}$ for each $i \in [m]$.

Consider the distance matrix $D'$ defined by $D'_{uw} = \tau_i$ for all $i \in [m]$ and $(u, w) \in C_i \cup S_i$. This completely defines $D'$ as $\cup_{i \in [m]} S_i = \mathit{Undet}$ by (i) and $\cup_{i \in [m]} C_i$ is the set of deter- mined entries in $D$. We will show that there exists a Foremost-realization of $D'$. As we have $D'_{uw} \in D_{uw}$ for all $u \neq v$ by (iii), this will imply that such a realization is also a realization
of D for Ranged-Foremost-path. Now, we note that for $i \in [m]$ and $(u, w) \in C_i \cup S_i$, the test RangeEdgeCompat($D$, $\{v, w\}$, $\tau_i$, $\cup_{k=1}^{i-1} S_k$, $S_i$) is equivalent to EdgeCompat($D'$, $\{v, w\}$, $\tau_i$) since $(r_{xv} < \tau_i$ or $(x, v) \in \cup_{k=1}^{i-1} S_k$) is equivalent to $D'_{xv} < \tau_i$ by definition of $D'$. Similarly, $(r_{uv} < \tau_i$ or $(u, v) \in \cup_{k=1}^{i-1} S_k$) is equivalent to $D'_{uv} < \tau_i$. The tests performed at Line 15 by the m calls to EXISTS($D$, $C_i$, $\tau_i$, $\cup_{k=1}^{i-1} S_k$, $S_i$) are thus equivalent to all tests at Line 6 of Algorithm 1 running with input $D'$. By its correctness (see the proof of Theorem 1), (iv) implies that $D'$ is Foremost-realizable.

Regarding the time complexity, for $i \in [m]$, EXISTS($D$, $C_i$, $\tau_i$, $S$, $T$) for a tri-partition $S$, $T$, $U$ of Undet takes $O((|C_i| + k)n^2)$ time assuming that we can check in constant time whether an undetermined entry $(u, v)$ is in set $S$ or $T$. This is achieved by using $n \times n$ boolean matrices for storing $S$ and $T$ in $O(n^2)$ time for each tri-partition (and $O(n^2)$ space). The overall time complexity is thus $O(\sum_{i=1}^m 3^k(|C_i| + k)n^2) = O(3^k n^4 + 3^k kn^2m) = O(k^23^k n^4)$ as $m = O(kn^2)$. Regarding the space complexity, note that at step $i \in [m]$, only the tables $R[\cdot, i-1]$ and $R[\cdot, i]$ are used. We can thus maintain at each step only 2 such tables. The overall space complexity is thus in $O(2^k+n^2)$. ■

Note that the definition of RangeEdgeCompat can be adapted in order to deal with the non-strict variant with ranges and the prescribed variant with ranges. Namely, we can respectively define:

* RangeNSEdgeCompat($D$, $\{v, w\}$, $\tau$, $S$, $T$) := $\forall x \in [n]$, $(r_{xv} \le \tau$ or $(x, v) \in S \cup T) \iff (r_{xw} \le \tau$ or $(x, w) \in S \cup T)$,

* RangePrEdgeCompatDir($D$, $v$, $w$, $\tau$, $S$, $T$, $G_p$ = $([n]$, $E_p$)) := $\forall x \in [n]$, $(r_{xv} < \tau$ or $(x, v) \in S) \implies (r_{xw} \le \tau$ or $(x, w) \in S \cup T)$ and $\{v, w\} \in E_p$.

Note also that it is straightforward to adapt the proof of Lemma 8 to obtain a similar statement for Ranged-NS-Foremost-path.

**Remark.** The algorithm proposed here can easily be generalized to a more general setting where a collection of ranges is given for each entry of $D$ with time complexity $O(k^23^k n^2 N)$ where $N \ge n^2$ denotes the total number of ranges in $D$. In particular, this provides an FPT algorithm for RANGED-FOREMOST-PATH TGR when each entry of $D$ encodes a set of integers and at most $k$ of them are non-singletons. Note that the hardness result of Theorem 8 holds in that setting, even if each set has size at most 2.

# 4 Fastest paths

In this section we revisit temporal graph realization for fastest paths analyzed by Klobas et al. [17] and Erlebach et al. [11]. We answer an open question by both papers about the parameterized complexity with respect to the vertex cover number. Moreover, we consider also non-strict paths and the non-periodic setting with arbitrary many labels per edge.

Recall the problem definition:

**FASTEST-PATH TGR:**

**Input:** A duration matrix $D$ of size $n \times n$.

**Question:** Is there a temporal graph $G$ (with unbounded lifetime and unbounded number of labels) that realizes the duration matrix $D$, that is, for each ordered pair of vertices $(u, v)$ in $G$ with $u \ne v$, the duration of a fastest past from $u$ to $v$ equals $D_{uv}$?

So far, FASTEST-PATH TGR has only been considered for strict temporal paths and if we consider a periodic temporal graph or if we limit the number of labels per edge (per period) [11,17]. Our parameterized hardness result holds even for non-periodic temporal graph with arbitrary lifetime and arbitrary many labels per edge. We then lift this hardness also to the periodic case with one label per edge per period to answer the open questions.
## Strict fastest paths

**Theorem 10** FASTEST-PATH TGR is NP-hard and W[1]-hard when parameterized by the vertex cover number of the underlying graph plus the largest entry of D. This holds even on a family of instances for which all yes-instances are realizable with only one label per edge.

**Proof.** We reduce from MULTICOLORED CLIQUE [6].

**MULTICOLORED CLIQUE:**

**Input:** An undirected graph $G = (V, E)$, an integer $k$, and a $k$-partition $(V_1 \cup \cdots \cup V_k)$ of $V$, such that $V_i$ is an independent set in $G$ for each $i \in [1, k]$.

**Question:** Is there a clique of size $k$ in $G$?

Note that a clique in such a graph is said to be multicolored since its vertices must belong to pairwise-distinct sets among $V_1 \cup \cdots \cup V_k$. The reason is that these sets are pairwise-disjoint independent sets, and they can be viewed as color classes. Let $I := (G = (V_1 \cup \cdots \cup V_k, E), k)$ be an instance of MULTICOLORED CLIQUE where for each $1 \le a < b \le k$, $G[V_a \cup V_b]$ is a disjoint union of bicliques. For each $a \in [1, k]$, we call $V_a$ a color class. Even under these restrictions, MULTICOLORED CLIQUE is NP-hard and W[1]-hard when parameterized by $k$ [23]. Let $V := V_1 \cup \cdots \cup V_k$.

**Construction.** To obtain an instance $D$ of FASTEST-PATH TGR as follows, we first describe the underlying graph, that is, the graph $G'$ that contains an edge $\{u, v\}$ if and only if $D_{u,v} = 1$. The graph $G'$ is defined over the vertex set $V' := V \cup \{s, s', s'', t, t', t''\} \cup X \cup L$, where $L$ is a vertex set of size $2k + 2$ and $X := \{x_i \mid 1 \le i \le k + 1\}$ (see Figure 3). We add edges between these vertices, such that $V' \setminus V$ is a vertex cover of $G'$. That is, there are no edges between the vertices of $V$ in $G'$. We make $L$ into a clique and adjacent to all vertices of $V'$ besides $s$ and $t$. Similarly, we make the vertices $s'$ and $s''$ adjacent to all vertices of $V'$ besides $t$ and make the vertices $t'$ and $t''$ adjacent to all vertices of $V'$ besides $s$. Additionally, we make $x_1$ adjacent to the vertices of $V_1$, $x_{k+1}$ adjacent to the vertices of $V_k$, and for each $i \in [2, k]$, we make $x_i$ adjacent to the vertices of $V_{i-1} \cup V_i$. There are no edges between the vertices of $X$. Finally, we make $s$ adjacent to $s'$, $s''$, and $x_1$, and we make $t$ adjacent to $t'$, $t''$, and $x_{k+1}$.

This completes the underlying graph $G'$ and thus all entries of the matrix $D$ of value 1. Let $E'$ denote the edges of $G'$. Next, we define the remaining entries. Note that each vertex of $\{s', s'', t', t''\} \cup L$ has an edge towards each other vertex of $V' \setminus \{s, t\}$. Hence, for these vertices it remains to define the entries of the table from and to the vertices $s$ and $t$. We set $D_{s,q} := D_{q,s} := 2k + 3$ for each vertex $q \in \{t', t''\} \cup L$. Similarly, we set $D_{t,q} := D_{q,t} := 2k + 3$ for each vertex $q \in \{s', s''\} \cup L$. For each non-edge $\{u, v\} \notin E$, we set $D_{u,v} := D_{v,u} := 2k + 3$. Finally, we set $D_{s,t} := 2k + 2$ and $D_{t,s} := 4k + 5$. All other undefined entries are set to 2. This completes the construction. Note that $X \cup L \cup \{s', s'', t', t''\}$ is a vertex cover of size $3k + 7$ and that the largest entry in $D$ is $4k + 5$.

**Intuition.** The idea behind the reduction is that realizing all entries besides $D_{s,t}$ is possible, regardless of whether $G$ contains a (multicolored) clique of size $k$. We will show that this is ensured by the fact that $G[V_i \cup V_j]$ with $1 \le i < j \le k$ is a disjoint union of bicliques. The difficulty to decide whether the matrix is realizable thus comes from the difficulty of deciding whether the entry $D_{s,t}$ can additionally be realized, which can only be done by using vertices of $X \cup V$ as intermediate vertices of the path. Let $S$ denote the vertices of $V$ on any path $P$ realizing the entry $D_{s,t} = 2k + 2$. Based on the structure of the underlying graph (see Figure 3), $S$ contains for each $i \in [1, k]$ at least one vertex of $V_i$. By definition of the entries between vertices of $V$, these vertices need to form a clique in the original graph, as only adjacent vertices $u$ and $v$ in $G$ fulfill $D_{u,v} \le 2k + 2$, which is the duration of $P$.

**Correctness.** We now show that $D$ is realizable if and only if $G$ admits a clique of size $k$. More precisely, we show that if $G$ admits a clique of size $k$, then there is a realization for $D$ with exactly one label per edge.
<figure><img src="image_6.png" /><figcaption>Figure 3: An illustration of the underlying graph from the reduction behind Theorem 10. The edges of the biclique ($L \cup \{s', s'', t', t''\}$, $V \cup X$) are not depicted. Note that $L$ is a clique of size $2k+2$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 4: An illustration of the labeling of the first described time block for a realization of the instance of FASTEST-PATH TGR from the reduction behind Theorem 10. For a better readability, $\gamma$ substitutes $2k+3$ and the addition by the lower label $\alpha$ of the time block is omitted on all labels. Only the edges that receive labels are depicted.</figcaption></figure>
(⇒) Let $\lambda: E' \to 2^N$ be an edge labeling, such that $\mathcal{G} := (G', \lambda)$ realizes $D$. We show that $G$ has a clique of size $k$. Consider the entry $D_{s,t} = 2k+2$. Since $\mathcal{G}$ is a realization of $D$, this implies that the fastest temporal path from $s$ to $t$ has duration exactly $2k+2$. Let $P$ be an arbitrary fastest temporal path from $s$ to $t$ in $\mathcal{G}$. Since the duration of $P$ is $2k+2$, the duration of each (not necessarily proper) subpath of $P$ is at most $2k+2$. Hence, for any two distinct vertices $a, b$ of $P$, where $a$ precedes $b$ in $P$, the entry $D_{a,b}$ is at most $2k+2$, as $D$ is realized by $\mathcal{G}$. This immediately implies that $P$ does not visit any vertex of $\{s', s'', t', t''\} \cup L$, since $D_{s,t'} = D_{s,t''} = D_{s',t} = D_{s'',t} = 2k+3$ and $D_{s,l} = D_{l,t} = 2k+3$ for each vertex $l \in L$. That is, $P$ only uses vertices of $V \cup \{s, t\} \cup X$. By definition, each path from $s$ to $t$ in $G'[V \cup \{s, t\} \cup X]$ traverses all vertices of $X$ and one vertex of each of the color classes of $V$, that is, for each $i \in [1, k]$, the path contains one vertex of $V_i$. This in particular holds for $P$. Let $S$ be the vertices of $V$ that are visited by $P$. By the above, $S$ has size at least $k$. Moreover, for each two distinct vertices $a$ and $b$ of $S$, $D_{a,b} = D_{b,a} \le 2k+2$, since the subpath between $a$ and $b$ of $P$ has duration at most $2k+2$ and $\mathcal{G}$ realizes $D$. This implies that $\{a, b\}$ is an edge of $\mathcal{G}$, as otherwise, $D_{a,b} = D_{b,a}$ is defined as $2k+3$. Consequently, $S$ is a clique of size $k$ in $\mathcal{G}$.

(←) Let $S$ be a clique of size $k$ in $G$ and for each $i \in [1, k]$, let $v_i$ denote the unique vertex of $S \cap V_i$. We define a labeling $\lambda: E' \to \mathbb{N}$, such that $\mathcal{G} := (G', \lambda)$ realizes $D$. To this end, we describe several *time blocks*, that is, intervals $[\alpha, \beta]$ with $\beta \ge \alpha + 4k + 6$, such that only the described edges receive a label from this interval, and all other edges receive no label from $[\alpha - (4k+6), \beta + (4k+6)]$. The reason behind this is that labeling edges in different time blocks do not create paths of duration less than $4k+6$, which is larger than the largest entry of $D$. Hence, we can show that our labeling realizes $D$ by showing that for each two vertices $a$ and $b$ of $G'$ (i) there is a time block in which there is a temporal path from $a$ to $b$ of duration exactly $D_{a,b}$ and (ii) for each time block, there is no temporal path from $a$ to $b$ of duration less than $D_{a,b}$. Note that the order of time blocks does not matter. Hence, when describing the labeling, we simply describe a collection of time blocks which in total fulfill the above properties, while not explicitly defining the concrete start and end time of the time blocks. In the following, we mainly focus on realizing all entries of value at least 2 in $D$. Afterwards, we describe how to realize the entries of value 1.

* Realizing all entries involving vertices of $V' \setminus (V \cup X)$ besides $D_{s,t}$. In the first time block $[\alpha, \beta]$, we realize all entries of $D$ of value at least 2 that involve at least one vertex of $\{s, s', s'', t, t', t''\} \cup L$, besides the entry $D_{s,t}$ (see Figure 4). We set $\lambda(\{s, s'\}) := \lambda(\{t, t'\}) := \alpha + 1$, $\lambda(\{s'', s\}) := \lambda(\{t'', t\}) := \alpha + 4k + 5$. Furthermore, for each vertex $q \in V \cup X$, we set $\lambda(\{s', q\}) := \lambda(\{t', q\}) := \alpha + 2$ and $\lambda(\{q, s''\}) := \lambda(\{q, t''\}) := \alpha + 4k + 4$, and we set $\lambda(\{s', t'\}) := \lambda(\{s', t''\}) := \lambda(\{s'', t'\}) := \lambda(\{s'', t''\}) := \alpha + 2k + 3$. For each vertex $l \in L$ and each vertex $z \in \{s', t', s'', t''\}$, we also set $\lambda(\{l, z\}) := \alpha + 2k + 3$.

This realizes the entries between $s$ and vertices of $L$ via the paths $(s, s', l)$ and $(l, s'', s)$ for each $l \in L$ with labels $(\alpha + 1, \alpha + 2k + 3)$ and $(\alpha + 2k + 3, \alpha + 4k + 5)$. These paths have duration $2k+3$ as required by $D$. Moreover, no faster paths between $s$ and a vertex $l \in L$ exists in this time block, since each edge incident with $l$ has label $\alpha + 2k + 3$ and the only labels incident with $s$ are $\alpha + 1$ and $\alpha + 4k + 5$. Analogously, all entries between $t$ and vertices of $L$ are realized. Since $s$ and $t$ are the only vertices that are not adjacent to the vertices of $L$, this thus realizes all entries of value at least 2 involving vertices of $L$. By the path $(t, t', s'', s)$ with labels $(\alpha+1, \alpha+2k+3, \alpha+4k+5)$ we further realize the entry $D_{t,s}$ and no faster path from $t$ to $s$ is realized, since both $s$ and $t$ only have the incident labels $\alpha+1$ and $\alpha+4k+5$ and are not adjacent. Similar to the paths between $s$ and vertices of $L$, there are the paths $(s, s', \hat{t})$ and $(\hat{t}, s'', s)$ for each $\hat{t} \in \{t', t''\}$ with labels $(\alpha+1, \alpha+2k+3)$ and $(\alpha+2k+3, \alpha+4k+5)$, respectively. These paths realize the entries between $s$ and vertices of $\{t', t''\}$. Moreover, no faster paths between these vertices are realized by this time block. This is due to the fact that (i) each path going over a vertex of $V \cup X$ in this time block takes time at least $4k+3$ (since $\alpha+2$ and $\alpha+4k+4$ are the only labels incident with vertices of $V \cup X$), (ii) each path going over $t$ has duration at least $4k+5$, and (iii) all other paths use an edge of label $\alpha+2k+3$ and a label from $\{\alpha+1, \alpha+4k+5\}$. Analogously, the entries between $t$ and the vertices of $\{s', s''\}$ are realized. This thus shows that all entries of
value at least 2 involving any vertex of {$s', s'', t', t''$} are realized. For each vertex $q \in V \cup X$, there are also the paths $(s, s', q)$, $(t, t', q)$, $(q, s'', s)$, and $(q, t'', t)$ of duration 2. These paths realize all entries of value larger than 1 between {$s, t$} and vertices of $V \cup X$. Thus, all entries of value at least 2 involving $s$ or $t$ are also realized by this time block, excluding $D_{s,t}$. It remains to argue that the time block does not create paths that are too fast between some vertices. Since we already argued that all entries involving at least one vertex of $V' \setminus (V \cup X)$ are realized in this time block, we only have to consider entries between vertices of $V \cup X$ that could theoretically be violated. Between these vertices, the value of the largest entry is at most $2k+3$. No path faster than this can be realized in this time block between vertices of $V \cup X$, since each such vertex has only the incident labels $\alpha+2$ and $\alpha+4k+4$. That is, each path in this time block that starts and ends in a vertex of $V \cup X$ traverses both an edge with label $\alpha+2$ and an edge with label $\alpha+4k+4$, implying that the duration of that path is at least $4k+3 > 2k+3$. Thus, this time block realizes all entries of value at least two involving vertices of $V' \setminus (V \cup X)$ besides $D_{s,t}$ and does not create any paths that are too fast.

* **Realizing $D_{s,t}$.** Next, we define a time block $[\alpha, \beta]$ that realizes the entry $D_{s,t}$. Recall that $S$ is a clique in $G$ and that for each $i \in [1, k]$, $v_i$ denotes the vertex of $S \cap V_i$. Consider the path $P := (s, x_1, v_1, \dots, x_k, v_k, x_{k+1}, t)$ and label the edges of this path with consecutive time labels starting with $\alpha$. Hence, this path has duration equals to its length, namely $D_{s,t} = 2k+2$. Since the entries of $D$ between vertices of {$s, t$} $\cup$ X and V are of value at most 2 and the entries between vertices of {$s, t$} $\cup$ X and X are of value at most 2, this creates no path of duration less than $D_{a,b}$ for vertices $a$ and $b$ of $P$ that are not both from V. Moreover, the only vertices of $P$ that are from V are all from the clique $S$. Hence, the entry $D_{a,b}$ also equals 2 for all such vertices $a$ and $b$ of $P$ that are from V. Thus, this time block does not create paths that are too fast.

So far, we realized all entries of $D$ of value at least 2 that involve at least one vertex of {$s, s', s'', t, t', t''$} $\cup$ $L$. In the following, we describe further time blocks to realize the entries of $D$ of value at least 2 involving only vertices of $V \cup X$. To this end, we will only use edges between $X \cup V$ and $L$. Note that none of these edges has received a label in the previous time blocks, that is, the only edges incident with vertices of $L$ that received labels so far were the edges between $L$ and {$s', s'', t', t''$}. Let the vertices of $L$ be called {$\ell^*, \ell^{**}$} $\cup$ {$\ell_i, \ell'_i$ | $1 \le i \le k$}.

* **Realizing entries between vertices of $V$ of value $2k+3$ and entries between vertices of $V$ and $X$.** We define a time block $[\alpha, \beta]$ as follows: For each vertex $v \in V$, we set $\lambda(\{v, \ell^*\}) := \alpha+1$ and $\lambda(\{v, \ell^{**}\}) := \alpha+2k+3$. For each vertex $x \in X$, we set $\lambda(\{x, \ell^*\}) := \alpha$ and $\lambda(\{x, \ell^{**}\}) := \alpha+2k+4$. Finally, we set $\lambda(\{\ell^*, \ell^{**}\}) = \alpha+2$. Note that each vertex of $V$ has only two incident labels in this time block, namely, $\alpha+1$ and $\alpha+2k+3$. Hence, no temporal path between vertices of $V$ has duration less than $2k+3$. Moreover, since entries involving a vertex from $V$ and a vertex from $X$ are of value at most 2, we guarantee that we do not create paths that are too fast in this time block. We now show that this time block realizes (i) all entries of value at least 2 between vertices of $V$ and $X$ and (ii) all entries between vertices of $V$ of value $2k+3$. For the first type, let $v \in V$ and $x \in X$ with $\{v, x\} \notin E'$. That is, $D_{x,v} = 2$. Then, there is a temporal path $(x, \ell^*, v)$ in this time block of duration 2. Similarly, the temporal path $(v, \ell^{**}, x)$ also has duration 2. Now consider the second type. For each two distinct vertices $u$ and $v$ of $V$ with $D_{u,v} \ne 2$, there is the temporal path $(u, \ell^*, \ell^{**}, v)$ with labels $(\alpha+1, \alpha+2, \alpha+2k+3)$. This path has duration $2k+3 = D_{u,v}$. This time block realizes the stated entries of $D$.

* **Realizing entries between vertices of $X$.** For each $i \in [1, k]$, we define a time block $[\alpha_i, \beta_i]$ in which we set $\lambda(\{x_i, \ell_i\}) := \alpha_i$ and $\lambda(\{\ell_i, x\}) := \alpha_i+1$ for each $x \in X \setminus \{x_i\}$. For each $i \in [1, k]$, this realizes the entries $D_{x_i,x}$ with $x \in X \setminus \{x_i\}$. Similarly, we add a time block $[\alpha_{k+1}, \beta_{k+1}]$ in which we set $\lambda(\{x_{k+1}, \ell'_1\}) := \alpha_{k+1}$ and $\lambda(\{\ell'_1, x\}) := \alpha_{k+1}+1$ for each $x \in X \setminus \{x_{k+1}\}$. These time blocks realize all entries of $D$ between vertices of $X$.
* **Realizing entries between vertices of V of value 2.** Recall that we have to ensure that there is a path of duration 2 between the endpoints of each edge $e \in E$ in our temporal graph. To define the necessary time blocks, we will highly rely on the fact that for each $1 \le a < b \le k$, $G[V_a \cup V_b]$ is a vertex disjoint union of bicliques. This property will allow us to realize all edges between $V_a$ and $V_b$ via just two vertices of $L$. We can do this for several combinations of color classes via the same two vertices of $L$, as long as no color class occurs in more than one pair. We formalize this as follows. Let $M_1, \dots, M_k$ be a partition of $\{(a,b) | 1 \le a < b \le k\}$, such that for each $i \in [1, k]$ and each $a \in [1, k]$, there is at most one ordered pair in $M_i$ that contains $a$. That is, $M_i$ is a matching in the directed graph with vertex set $[1, k]$ and edge set $\{(a,b) | 1 \le a < b \le k\}$. Note that such a partition exists due to the fact that a clique on $k$ vertices has a proper edge coloring with $k$ colors. Let $i \in [1, k]$. We let $E_{M_i}$ denote all edges of $G$ between each pair of color classes in $M_i$, that is, $E_{M_i} := \cup_{(a,b) \in M_i} E(V_a, V_b)$. Since $M_i$ is a matching and $G[V_a \cup V_b]$ is a disjoint union of bicliques for each $1 \le a < b \le k$, $G_i := (V, E_{M_i})$ is also a disjoint union of bicliques. That is, each connected component in $G_i$ is a biclique. We use the vertices $\ell_i$ and $\ell'_i$ of $L$ to realize the entries of $D$ corresponding to the edges of $E_{M_i}$. For each connected component of $G_i$ with bipartition $(A, B)$, we add a new time block $[\alpha, \beta]$ and set $\lambda(\{v_a, \ell_i\}) := \alpha$ for each $v_a \in A$ and $\lambda(\{v_b, \ell'_i\}) := \alpha + 1$ for each $v_b \in B$. This realizes paths of duration 2 from each vertex of $A$ to each vertex of $B$ and no other temporal paths of length more than 1. Since $(A, B)$ is a biclique, for all these vertex pairs, the entry in the matrix is also 2. In the same way, we also add a new time block $[\alpha', \beta']$ and set $\lambda(\{v_b, \ell'_i\}) := \alpha$ for each $v_b \in B$ and $\lambda(\{v_a, \ell'_i\}) := \alpha + 1$ for each $v_a \in A$. This thus realizes also the entries of duration 2 from each vertex of $B$ to each vertex of $A$. Since $E = \cup_{i \in [1, k]} E_{M_i}$, this implies that we realized for each edge $\{u, v\} \in E$ the entries $D_{u,v}$ and $D_{v,u}$ of value 2 by the above time blocks.

Hence, all entries of value at least 2 in $D$ are realized by $\lambda$. Let $E''$ denote the edges of $E'$ that have not received a label yet. We add one final time block from which all edges of $E''$ receive the same label. This surely does not create new temporal paths of length more than 1 for which the duration is at most $4k+5$. This completes the definition of $\lambda$. Thus, also all entries of value 1 are realized. By definition of the time blocks, we showed that $(G', \lambda)$ realizes the input matrix $D$ even with just a single label per edge. ■

Based on this reduction, we can now directly transfer the hardness result to PERIODIC FASTEST-PATH TGR even when allowing at most one label per edge.

**PERIODIC FASTEST-PATH TGR:**

**Input:** A duration matrix $D$ of size $n \times n$ and a period $\Delta$.

**Question:** Is there a $\Delta$-periodic temporal graph that realizes the fastest path matrix $D$?

That is, we simply define the period $\Delta$ to be an integer much larger than $n^2 \cdot \max D$, which ensures that all fastest paths start and end within a window of $\Delta$ consecutive time steps (see [11]).

**Theorem 11** *Even when only allowed to put one label per edge and per period, PERIODIC FASTEST-PATH TGR is $W[1]$-hard when parameterized by the vertex cover number of the underlying graph plus the largest entry of $D$.*

This answers an open question by Klobas et al. [17] and Erlebach et al. [11] about the parameterized complexity of the problem with respect to the vertex cover number. Furthermore, this reduction improves significantly over the known hardness result for parameter feedback vertex set number. It also shows that PERIODIC FASTEST-PATH TGR can presumably not be solved in FPT time for the combined parameter of the vertex cover number plus $\ell$ (the number of allowed labels per edge and per period) plus the largest entry in $D$. Thus, in the FPT algorithm by Erlebach et al. [11] for the vertex cover number plus the period $\Delta$, one cannot replace $\Delta$ by $\ell$ plus the largest entry of $D$.
**Non-Strict fastest paths** Next, we show that a similar reduction also shows similar intractability results for FASTEST-PATH TGR with non-strict paths. The following reduction however requires more than one label per edge.

**Theorem 12** NS-FASTEST-PATH TGR is NP-hard and W[1]-hard when parameterized by the vertex cover number of the underlying graph plus the largest entry of D.

**Proof.** We again reduce from MULTICOLORED CLIQUE.

Let $I := (G = (V_1 \cup \cdots \cup V_k, E), k)$ be an instance of MULTICOLORED CLIQUE. The requirement that the induces subgraph between any two color classes is a disjoint union of bicliques is not required for this reduction. We obtain an instance $D$ of NS-FASTEST-PATH TGR as follows: We take the instance of FASTEST-PATH TGR produced by the reduction behind Theorem 10 and restrict it to the vertices of $V \cup X \cup \{s, s', t, t'\}$. Let $G'$ be the respective underlying graph. Since $V$ is an independent set in the instance from the reduction behind Theorem 10, $X \cup \{s', t'\}$ is a vertex cover of size $k+3$ of $G'$.

This completes the construction. Intuitively, the main difficulty comes from realizing the entry $D_{s,t}$ while not violating the other entries. We show that this can only be realized if and only if $G$ has a clique of size $k$.

(⇒) The proof of this direction is identical to the one on the proof of Theorem 10. We thus only recall the main parts of the proof for this direction.

* To realize the entry $D_{s,t}$ of value $2k+2$, there needs to be a temporal path $P$ of duration exactly $2k+2$.

* For each pair $(u, v)$ of vertices on $P$, where $u$ appears before $v$ on $P$, it holds that $D_{u,v} \le 2k+2$.

* By $D_{s,t'} = D_{s',t} = 2k+3$, $P$ contains neither $s'$ nor $t'$.

* Each path form $s$ to $t$ in $G' - \{s', t'\} := G'[V \cup X \cup \{s, t\}]$ contains exactly one vertex of $V_i$ for each $i \in [1, k]$. Thus, $P$ visits for each $i \in [1, k]$, exactly one vertex $v_i$ of $V_i$.

* Since $D_{v_i,v_j} \le 2k+2$ for each $i \in [1, k-1]$ and each $j \in [i+1, k]$, there is the edge $\{v_i, v_j\}$ in $G$ (as otherwise, $D_{v_i,v_j} = D_{v_j,v_i} = 2k+3$).

* Thus, $\{v_i \mid i \in [1, k]\}$ is a clique of size $k$ in $G$.

(←) Let $S$ be a clique of size $k$ in $G$ and for each $i \in [1, k]$, let $v_i$ denote the unique vertex of $S \cap V_i$. We define a labeling $\lambda: E' \to 2^N$, such that $G := (G', \lambda)$ realizes $D$. We present the labeling again via the help of time blocks.

Let $(p, q) \in (V \cup X)^2$ be a pair of distinct vertices, such that $\{p, q\}$ is not an edge of $G'$. We add a new time block $[\alpha, \beta]$ in which we add labels $\alpha+1$ and $\alpha+2 \cdot D_{p,q}-1$ to edge $\{p, s'\}$ and add label $\alpha+D_{p,q}$ to edge $\{s', q\}$. This realizes both entries $D_{p,q}$ and $D_{q,p}$ and no other paths of duration more than 1 exists in this time block.

For each vertex $p \in V \cup X$, we add a time block $[\alpha, \beta]$, in which we add labels $\alpha+1$ and $\alpha+3$ to the edge $\{p, s'\}$ and add label $\alpha+2$ to edge $\{s, s'\}$. This creates paths of duration exactly 2 between $p$ and $s$ and no other paths of duration more than 1 exists in this time block. Similarly, we ensure paths of duration between $p$ and $t$ by adding a time block $[\alpha', \beta']$, in which we add labels $\alpha' + 1$ and $\alpha' + 3$ to the edge $\{p, t'\}$ and add label $\alpha' + 2$ to edge $\{t, t'\}$. All these time blocks together realize all entries between $V$ and $\{s, t\}$ of value more than 1.

It remains to realize the entries between the vertices of $\{s, s', t, t'\}$ of value at least 2. To this end, we add two time blocks. In the first time block $[\alpha, \beta]$, we add label $\alpha+1$ and $\alpha+4k+5$ to both edges $\{s, s'\}$ and $\{t, t'\}$, and add label $\alpha+2k+3$ to edge $\{s', t'\}$. This ensures paths of duration $2k+3$ between $s$ and $t'$ and between $t$ and $s'$. Moreover, this ensures that there is a path of duration $D_{t,s} = 4k+5$ from $t$ to $s$. Observe that no faster paths between these vertices are realized. Thus, the only entry of value at least 2 that is not yet realized is the entry $D_{s,t}$ of
value $2k + 2$. We do this in the same way as in the proof of Theorem 10. Due to the similarity, we just recall the rough idea. Recall that $S$ is a clique in $G$ and that for each $i \in [1, k]$, $v_i$ denotes the vertex of $S \cap V_i$. Consider the path $P := (s, x_1, v_1, \dots, x_k, v_k, x_{k+1}, t)$ and label the edges of this path with consecutive time labels starting with $\alpha$. Hence, this path has duration equals to its length, namely $D_{s,t} = 2k + 2$. Since $S$ is a clique in $G$, all entries of $D$ between these vertices are at most 2. Thus, this time block does not create paths that are too fast.

Finally, for each entry $D_{p,q}$ of value 1 for which the edge $\{p, q\}$ has not received a label so far, we add a time block from which the edge $\{p, q\}$ receives an arbitrary label. This thus also realizes all entries of value 1, which in total implies that $D$ is realized by $(G', \lambda)$. ■

By replacing the vertices $s'$ and $t'$ by $\Theta(n^2)$ true twins each (also with respect to all respecting entries in the matrix), we can obtain an equivalent instance of NS-FASTEST-PATH TGR, such that each constructed yes-instance in that way can be realized with only one label per edge. This, however, has a vertex cover of unbounded size and the parameterized hardness does not transfer.

**Corollary 1** NS-FASTEST-PATH TGR is NP-hard and W[1]-hard when parameterized by the largest entry of $D$. This holds even on a family of instances for which all yes-instances are realizable with only one label per edge.

This shows that PERIODIC NS-FASTEST-PATH TGR remains NP-hard. Moreover, since the reduction behind Theorem 12 never had to make use of non-strict paths to realize the obtained yes-instances, but only used paths that were also strict, this hardness result would also transfer to the version of FASTEST-PATH TGR, where we require the resulting temporal graph to be proper, that is, no two adjacent edges are allowed to share a label.

# 5 Shortest paths

In this section, we consider the question for shortest temporal paths.

**SHORTEST-PATH TGR:**

**Input:** A distance matrix $D$ of size $n \times n$.

**Question:** Is there a temporal graph $\mathcal{G}$ such that Shortest($\mathcal{G}$) = $D$?

Note that a realization of $D$ can only assign labels to edges $\{u, v\}$ where $D_{u,v} = D_{v,u} = 1$. Hence, $G = ([n], E)$ with $E := \{\{u, v\} | D_{u,v} = 1 \land D_{v,u} = 1\}$ is the underlying graph of every realization of $D$.

We show the NP-hardness of both the strict and the non-strict variants.

**Theorem 13** *SHORTEST-PATH TGR and NS-SHORTEST-PATH TGR are NP-hard.*

**Proof.** We reduce from the NP-hard SAT [14]. Let $F$ be an instance of SAT where each variable occurs at least once positively and at least once negatively, and where no clause contains the same variable both positively and negatively. Under these restrictions, SAT is NP-hard [14].

**Construction.** Let $X$ be the variable set of $F$ and let $C$ denote the clauses of $F$. To obtain an instance $D$ of SHORTEST-PATH TGR or NS-SHORTEST-PATH TGR, we first define the underlying graph $G = (V, E)$ that contains an edge $\{u, v\}$ if and only if $D_{u,v} = D_{v,u} = 1$ (see Figure 5). The graph $G$ contains for each variable $x \in X$ the vertices $x$ and $\bar{x}$ which are joined by an edge. For each clause $c \in C$, we also add a vertex $c$, which we make adjacent to all vertices corresponding to literals that are contained in $c$. Additionally, we add three more vertices to $G$. A vertex $v^*$ which is adjacent to all vertices of $C$, and two vertices $\top$ and $\bot$ that are adjacent to all vertices representing literals, that is, to the vertices of $\{x, \bar{x} | x \in X\}$.

Next, we describe the remaining entries of $D$. Let $c$ be a clause of $C$. We set $D_{c,\top} := 3$ and $D_{\top,c} := D_{c,\bot} := D_{\bot,c} := 2$. For each other clause $c'$ of $C$, we set $D_{c,c'} := D_{c',c} := 2$. For each positive literal $x$ that occurs in $c$, we set $D_{c,\bar{x}} := D_{\bar{x},c} := 2$. Similarly, for each negative literal $\bar{x}$
<figure><img src="image_8.png" /><figcaption>Figure 5: An example of the reduction behind Theorem 13 for the formula $(x \lor y \lor z) \land (\bar{x} \lor y) \land (\bar{y} \lor \bar{z})$. A labeling that realizes the matrix $D$ is depicted, where the dashed arcs receive the label set $\{1, 2, 7, 8\}$. Moreover this labeling corresponds to a satisfying truth assignment $(x = \text{False}, y = \text{True}, z = \text{False})$.</figcaption></figure>

that occurs in $c$, we set $D_{c,x} := D_{x,c} := 2$. For each variable $x$ for which neither $x$ nor $\bar{x}$ occurs in $c$, we set $D_{c,\bar{x}} := D_{\bar{x},c} := D_{c,x} := D_{x,c} := 3$. This defines all entries regarding vertices of $C$.

Let $\ell_1$ and $\ell_2$ be distinct literals, such that they are not the negation of each other. We set $D_{\ell_1, \ell_2} := D_{\ell_2, \ell_1} := 2$. For each literal $\ell$, we also set $D_{\ell, v^*} := D_{v^*, \ell} := 2$.

Finally, we set $D_{v^*, \perp} := D_{\perp, v^*} := 3$, $D_{\perp, \top} := D_{\top, \perp} := 2$, $D_{v^*, \top} := 4$, and $D_{\top, v^*} := 3$. This completes the definition of $D$.

Note that nearly all defined entries are the exact distances between the vertices in the underlying graph $G$. The only exceptions are the entry $D_{v^*, \top}$ and the entry $D_{c, \top}$ for each clause $c \in C$. Hence, only for the vertex pairs $(\{v^*\} \cup C) \times \{\top\}$, one could possibly create a temporal path that has length less than the respective entry of $D$. Based on this property, we can prove that a labeling $\lambda: E \to 2^N$ realizes $D$ by showing the following two points:

* For distinct vertices $a$ and $b$ of $V$, there is a temporal path of length $D_{a,b}$ from $a$ to $b$.

* For each $a \in \{v^*\} \cup C$, there is no temporal path of length less than $D_{a, \top}$ from $a$ to $\top$.

**Intuition.** Similar to the reduction behind Theorem 8, we have clause vertices that aim to reach $\top$. For each such clause vertex $c_i$, we want that the shortest temporal path to $\top$ has length exactly 3. By the structure of the implicit underlying graph, these paths must be of the form $(c_i, \ell, \bar{\ell}, \top)$ for some literal $\ell$ that occurs in clause $c_i$. If two clauses try to use the same variable gadget from different sides to realize their entries, that is, if $(c_i, \ell, \bar{\ell}, \top)$ and $(c_j, \ell, \bar{\ell}, \top)$ are both temporal paths in our solution graph, then in fact at least one of $(c_i, \ell, \top)$ or $(c_j, \ell, \top)$ is also a temporal path, implying that for at least one of the clauses, the shortest temporal path has length 2, which is lower than the desired length of 3. Intuitively, this means that in each solution, each variable gadget can only be used in one direction for paths between clauses and $\top$, which then encodes a satisfying truth assignment.

**Correctness.** We now show that $F$ is satisfiable if and only if $D$ is realizable.

(=$\Leftarrow$) Let $\mathcal{G} := (G, \lambda)$ be a realization of $D$.<fnref n="5" /> We show that $F$ is satisfiable. To this end, we define the following truth assignment $\pi$: We assign the literal $x$ to True if and only if $\max \lambda(\{x, \top\}) < \max \lambda(\{\bar{x}, \top\})$.

We now show that the so defined truth assignment satisfies $F$. To this end, let $c$ be an arbitrary clause of $C$. We show that one literal contained in $c$ is assigned to True by $\pi$. Since $\mathcal{G}$ realizes $D$ and $D_{c, \top} = 3$, the shortest temporal path in $\mathcal{G}$ from $c$ to $\top$ has length exactly 3. Let $P = (c, a, b, \top)$ be such a shortest temporal path from $c$ to $\top$ in $\mathcal{G}$ for vertices $a$ and $b$. The

<footnote n="5">⁵Recall that a realization of $D$ can only assign label to the edges of $E$, as all other vertex pairs have a pairwise distance strictly greater than one according to $D$.</footnote>
vertex $a$ is a literal $\ell$ that is contained in the clause $c$. This is due to the fact that the only other neighbor of $c$ in $G$ is vertex $v^*$ for which the shortest temporal path towards $\top$ is supposed to have length at $4 = D_{v^*,\top}$. Let $\overline{\ell}$ denote the complementary literal of $\ell$. Now consider the vertex $b$. Since $b$ is the direct predecessor of $\top$ in $P$, $b$ is a neighbor of both $\ell$ and $\top$ in $G$. By definition, $\overline{\ell}$ is the only such vertex. Thus, $P = (c, \ell, \overline{\ell}, \top)$. We show that $\max \lambda(\{\ell, \top\}) < \max \lambda(\{\overline{\ell}, \top\})$, which then implies that literal $\ell$ is set to True under $\pi$. To this end, let $\alpha := \min \lambda(\{c, \ell\})$. We distinguish between the strict and the non-strict case:

In the strict case, $\max \lambda(\{\overline{\ell}, \top\}) > \alpha$, since $P$ is a temporal path in $G$. Moreover, $\max \lambda(\{\ell, \top\}) \le \alpha$, as otherwise, $(c, \ell, \top)$ would be a temporal path of length $2 < D_{c,\top}$ in $G$. Thus, $\max \lambda(\{\ell, \top\}) \le \alpha < \max \lambda(\{\overline{\ell}, \top\})$.

In the non-strict case, $\max \lambda(\{\overline{\ell}, \top\}) \ge \alpha$, since $P$ is a temporal paths in $G$. Moreover, $\max \lambda(\{\ell, \top\}) < \alpha$, as otherwise, $(c, \ell, \top)$ would be a temporal path of length $2 < D_{c,\top}$ in $G$. Thus, $\max \lambda(\{\ell, \top\}) < \alpha \le \max \lambda(\{\overline{\ell}, \top\})$.

In both cases, $\max \lambda(\{\ell, \top\}) < \max \lambda(\{\overline{\ell}, \top\})$. This implies that the literal $\ell$ is set to True under $\pi$. Thus, $\pi$ satisfies $c$. Since the clause $c$ was chosen arbitrarily, this implies that $\pi$ satisfies all clauses of $C$ and thus the whole formula $F$.

(⇒) Assume that $F$ is satisfied and let $L$ denote the set of literals that are assigned to True in a fixed but arbitrary satisfying truth assignment for $F$. We define a labeling $\lambda: E \to 2^N$ as follows: For each edge $e$ incident with one of $v^*$ or $\perp$, we set $\lambda(e) := \{1, 2, 7, 8\}$. Let $x$ be a variable of $X$. We set $\lambda(\{x, \bar{x}\}) := \{1, 4, 7\}$. If $x \in L$, that is, if $x$ is assigned to True, we set $\lambda(\{\bar{x}, \top\}) := \{5\}$, $\lambda(\{x, \top\}) := \{2\}$, $\lambda(\{\bar{x}, c\}) := \{6\}$ for each clause $c \in C$ that contains the literal $\bar{x}$, and $\lambda(\{x, c\}) := \{3\}$ for each clause $c \in C$ that contains the literal $x$. Otherwise, that is, if $\bar{x} \in L$, we set $\lambda(\{\bar{x}, \top\}) := \{2\}$, $\lambda(\{x, \top\}) := \{5\}$, $\lambda(\{\bar{x}, c\}) := \{3\}$ for each clause $c \in C$ that contains the literal $\bar{x}$, and $\lambda(\{x, c\}) := \{6\}$ for each clause $c \in C$ that contains the literal $x$. This completes the definition of $\lambda$.

We now show that $G := (G, \lambda)$ realizes $D$. As discussed previously, we can do this in two steps.

* We show that for each two distinct vertices $a$ and $b$ of $V$, there is a temporal path of length exactly $D_{a,b}$ from $a$ to $b$, and

* we show that for each $a \in \{v^*\} \cup C$, there is no temporal path of length less than $D_{a,\top}$ from $a$ to $\top$.

The latter property follows from the definition of $\lambda$: For each literal $\ell$, $\max \lambda(\{\ell, \top\}) < \min \lambda(\{\ell, c\})$ for each clause $c \in C$ that contains the literal $\ell$. Thus, for each such clause $c$, $(c, \ell, \top)$ is not a temporal path, which implies that the shortest temporal path from $c$ to $\top$ has length at least 3 = $D_{c,\top}$, since each common neighbor of $c$ and $\top$ is a literal $\ell$ that is contained in $c$. Note that this holds in both the strict and the non-strict setting. Similarly, since the neighborhood of $v^*$ in $G$ are exactly the clauses of $C$ and since no such vertex $c \in C$ has a temporal path of length less than 3 towards $\top$, there is no temporal path of length less than $4 = D_{v^*,\top}$ from $v^*$ to $\top$. Consequently, for any two vertices $a$ and $b$ of $V$, there is no temporal path from $a$ to $b$ of length less than $D_{a,b}$ in $G$.

It thus remains to show that there always is at least one temporal path from $a$ to $b$ in $G$ of length exactly $D_{a,b}$. First, we consider all entries involving vertices of $C$.

* If $a$ and $b$ are from $C$, the entry $D_{a,b} = 2$ is realized via the path $(a, v^*, b)$ which has labels $(1, 2)$.

* Let $a$ be from $C$ and let $b$ be a literal $\ell$. If $\ell$ is contained in clause $a$, the two vertices are adjacent and the entries $D_{a,b}$ and $D_{b,a}$ of value 1 are realized by the direct edge. If the negation $\overline{\ell}$ of $\ell$ is contained in clause $a$, then the path $(a, \overline{\ell}, \ell)$ with labels $(\alpha, 7)$ and the path $(\ell, \overline{\ell}, a)$ with labels $(1, \alpha)$ realize the entries $D_{a,\ell}$ and $D_{\ell,a}$ of value 2, where $\alpha$ is the unique label of edge $\{a, \overline{\ell}\}$ which is an element of $\{3, 6\}$. If neither $\ell$ nor the negation of $\ell$ occurs in clause $a$, let $\ell'$ be an arbitrary literal which is contained in clause $a$. Then, the path $(a, \ell', \perp, \ell)$ with labels $(\alpha, 7, 8)$ and the path $(\ell, \perp, \ell', a)$ with labels $(1, 2, \alpha)$ realize the entries $D_{a,\ell}$ and $D_{\ell,a}$ of value 3, where $\alpha$ is the unique label of edge $\{a, \overline{\ell}\}$ which is an
element of {3, 6}. Note that the latter case also implies the existence of temporal paths of
length 2 between a and ⊥.

* Let $a$ be from $C$ and let $b$ be $\top$. Then, since the clause $c$ is satisfied by the truth assignment, there is some literal $\ell$ that is contained in $c$ and also assigned to True. Let $\overline{\ell}$ be the negation of $\ell$. By definition of $\lambda$, the paths $(a, \ell, \overline{\ell}, \top)$ has labels (3, 4, 5) and the path $(\top, \ell, a)$ has labels (2, 3). These two paths realize the entry $D_{a,\top}$ of value 3 and $D_{\top,a}$ of value 2.

Thus, all entries involving at least one vertex of $C$ are realized. We continue with the entries involving vertices that correspond to literals.

* Let $a$ and $b$ be literals that are not adjacent in $G$. Then, the entries $D_{a,b}$ and $D_{b,a}$ of value 2 are realized by the paths $(a, \bot, b)$ and $(b, \bot, a)$ with labels (1, 2) each.

* Let $a$ be a literal and let $b$ be $v^*$. Then, there is some clause $c$ such that $c$ contains literal $a$. Thus, the entries $D_{a,b}$ and $D_{b,a}$ of value 2 are realized by the paths $(a, c, v^*)$ and $(v^*, c, a)$ with labels $(\alpha, 7)$ and $(1, \alpha)$ respectively, where $\alpha$ denotes the unique label of edge $\{c, a\}$ which is an element of $\{3, 6\}$.

Note that these are all remaining entries of value at least 2 that involve vertices that correspond to literals. It remains to consider the entries between the vertices $v^*, \bot$ and $\top$. The entries $D_{\bot,\top}$ and $D_{\top,\bot}$ of value 2 are realized via the paths $(\bot, \ell, \top)$ and $(\top, \ell, \bot)$ with labels (1, 2) and (2, 7) respectively, where $\ell$ is an arbitrary literal that is assigned to True. For the remaining four entries involving $v^*$ and a vertex $b \in \{\top, \bot\}$, consider the previously discussed paths between $b$ and an arbitrary clause vertex $c \in C$. These paths only started/ended at $c$ with a label between 3 and 6. Thus, we can extend them by a preceding (resp. succeeding) edge from (resp. to) $v^*$ with label 1 (resp. 8) to realize the remaining four entries involving vertex $v^*$.

Thus, for each two vertices $a$ and $b$ of $V$, the shortest temporal path in $G$ from $a$ to $b$ has length exactly $D_{a,b}$. Consequently, $G$ realizes $D$.

Note that a realization question for shortest temporal paths in periodic temporal graphs is polynomial time solvable. Due to the periodicity, a shortest path in the underlying static graph will always be a shortest temporal path in the periodic temporal graph where each edge receives at least one label. Since the latter is mandatory, the resulting problem is answered with yes if and only if the given matrix $D$ is the distance matrix of the underlying graph.

# 6 Conclusion

Our work spawns several interesting future questions.

* We showed that **FOREMOST-PATH** TGR is polynomial-time solvable if we are allowed to assign up to $n$ labels per edge but becomes NP-hard when allowing only a single label per edge. What is the smallest number of labels per edge for which this problem is still polynomial-time solvable? For example, is there an efficient algorithm when we are allowed to assign only $\frac{n}{2}$ labels per edge?

* Our hardness results for **SHORTEST-PATH** TGR use multiple labels per edge. Does this problem become polynomial-time solvable, if we restrict the respective labeling? For example, what if we enforce that at most one label per edge is allowed or we require a proper labeling, that is, a labeling where no two adjacent edges share a label?

* Are there structural parameters for which we can solve **SHORTEST-PATH** TGR in FPT-time. For example, can we solve the problem efficiently if the underlying graph has bounded treewidth?

* One could consider approximation of the considered problems. For example under the measurement of fulfilling as many entries as possible. Are there constant factor approximations for **SHORTEST-PATH** TGR or **FASTEST-PATH** TGR?
References

[1] Eleni C. Akrida, Leszek Gąsieniec, George B. Mertzios, and Paul G. Spirakis. The complexity of optimal design of temporally connected graphs. *Theory Comput. Syst.*, 61(3):907–944, 2017. URL: https://doi.org/10.1007/s00224-017-9757-x, doi:10.1007/S00224-017-9757-X.

[2] Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently realizing inter-val sequences. *SIAM J. Discret. Math.*, 34(4):2318–2337, 2020. doi:10.1137/20M1326489.

[3] Arnaud Casteigts, Michelle Döring, and Nils Morawietz. Realization of Temporally Connected Graphs Based on Degree Sequences. In *Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC)*, 2025. URL: https://doi.org/10.48550/arXiv.2504.17743.

[4] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. *Int. J. Parallel Emergent Distributed Syst.*, 27(5):387–408, 2012. doi:10.1080/17445760.2012.668546.

[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. *Introduction to Algorithms, 3rd Edition*, chapter 14.3. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.

[6] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. *Parameterized Algorithms*. Springer, 2015.

[7] Argyrios Deligkas and Igor Potapov. Optimizing reachability sets in temporal graphs by delaying. *Inf. Comput.*, 285(Part):104890, 2022. URL: https://doi.org/10.1016/j.ic.2022.104890, doi:10.1016/J.IC.2022.104890.

[8] Jessica A. Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev. Delet-ing edges to restrict the size of an epidemic in temporal networks. *J. Comput. Syst. Sci.*, 119:60–77, 2021. URL: https://doi.org/10.1016/j.jcss.2021.01.007, doi:10.1016/J.JCSS.2021.01.007.

[9] Paul Erdős and Tibor Gallai. Graphs with prescribed degrees of vertices. *Mat. Lapok*, 11:264–274, 1960.

[10] Thomas Erlebach, Othon Michail, and Nils Morawietz. Recognizing and Realizing Temporal Reachability Graphs. In *Proceedings of the 33rd Annual European Symposium on Algorithms (ESA)*, 2025. URL: http://arxiv.org/abs/2503.15771.

[11] Thomas Erlebach, Nils Morawietz, and Petra Wolf. Parameterized algorithms for multi-label periodic temporal graph realization. *Theoretical Computer Science*, 1051:115412, 2025. URL: https://www.sciencedirect.com/science/article/pii/S0304397525003500, doi:10.1016/j.tcs.2025.115412.

[12] F. Göbel, J. Orestes Cerdeira, and Henk Jan Veldman. Label-connected graphs and the gossip problem. *Discret. Math.*, 87(1):29–40, 1991. doi:10.1016/0012-365X(91)90068-D.

[13] S. Louis Hakimi and S. S. Yau. Distance matrix of a graph and its re-alizability. *Quarterly of Applied Mathematics*, 22:305–317, 1965. URL: https://api.semanticscholar.org/CorpusID:118924338.

[14] Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, *Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA*, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972. doi:10.1007/978-1-4684-2001-2\_9.
[15] David Kempe, Jon M. Kleinberg, and Amit Kumar. Connectivity and inference problems for temporal networks. In F. Frances Yao and Eugene M. Luks, editors, *Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA*, pages 504–513. ACM, 2000. doi:10.1145/335305.335364.

[16] Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. The complexity of computing optimum labelings for temporal connectivity. *J. Comput. Syst. Sci.*, 146:103564, 2024. URL: https://doi.org/10.1016/j.jcss.2024.103564, doi:10.1016/J.JCSS.2024.103564.

[17] Nina Klobas, George B. Mertzios, Hendrik Molter, and Paul G. Spirakis. Temporal graph realization from fastest paths. *Theoretical Computer Science*, 1056:115508, 2025. URL: https://www.sciencedirect.com/science/article/pii/S0304397525004463, doi:10.1016/j.tcs.2025.115508.

[18] George B. Mertzios, Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Temporal network optimization subject to connectivity constraints. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, *Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II*, volume 7966 of Lecture Notes in Computer Science, pages 657–668. Springer, 2013. doi:10.1007/978-3-642-39212-2_57.

[19] George B. Mertzios, Othon Michail, and Paul G. Spirakis. Temporal network optimization subject to connectivity constraints. *Algorithmica*, 81(4):1416–1449, 2019. URL: https://doi.org/10.1007/s00453-018-0478-6, doi:10.1007/S00453-018-0478-6.

[20] George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Realizing temporal transportation trees. In *Proceedings of the 51st Workshop on Graph-Theoretic Concepts in Computer Science (WG)*, 2025. URL: https://arxiv.org/abs/2403.18513.

[21] George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Temporal Graph Realization With Bounded Stretch. In *Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS)*, 2025. URL: https://doi.org/10.48550/arXiv.2504.14258.

[22] Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt. Directed temporal tree realization for periodic public transport: Easy and hard cases. In *Proceedings of the 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)*, 2025. URL: https://arxiv.org/abs/2504.07920.

[23] Nils Morawietz, Carolin Rehs, and Mathias Weller. A timecop's work is harder than you think. In Javier Esparza and Daniel Král', editors, *45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic*, volume 170 of LIPIcs, pages 71:1–71:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.71, doi:10.4230/LIPICS.MFCS.2020.71.

[24] Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The complexity of finding small separators in temporal graphs. *J. Comput. Syst. Sci.*, 107:72–92, 2020. URL: https://doi.org/10.1016/j.jcss.2019.07.006, doi:10.1016/J.JCSS.2019.07.006.