Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics

In this work, we extend the previous work on Fastest-path TGR to the non-strict case (that is, where arbitrary many edges per time step can be traversed). Furthermore, we consider the other most frequently used temporal path metrics $\mathrm{Foremost}$ and $\mathrm{Shortest}$ (formally defined in Section 2). Roughly speaking, Foremost-path TGR requires that the earliest arrival time at $t$, minimized over all temporal $st$-paths, is equal to $D_{s,t}$ for each vertex pair $(s,t)$, whereas Shortest-path TGR requires that the number of edges, minimized over all temporal $st$-paths, is equal to $D_{s,t}$ for each vertex pair $(s,t)$. Our main results are as follows:

1. 1.

   In Section 3 we show that all considered versions (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 on each edge. This is surprising, as almost 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^2$ time labels in total, if dealing with a realizable instance. This is asymptotically tight as some realizable matrices do require $\mathrm{\Omega }(n^2)$ time labels.

2. 2.

   To show the limitations of the tractability, we also show in Section 3 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 more than one entry for each vertex pair, 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. 3.

   In Section 4 we consider Fastest-path TGR. Among other results, we answer open questions by Klobas et al. [16] 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 of the proof.

4. 4.

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

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

An (undirected) graph $G=(V,E)$ is defined by its vertex set $V$ and its edge set $E\subseteq \left(\genfrac{}{}{0pt}{}{V}{2}\right)$. 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 \left(\genfrac{}{}{0pt}{}{S}{2}\right))$. A graph $H=(V^{\prime },E^{\prime })$ is a subgraph of $G$ if $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$. A $uv$-walk is a sequence $P=(v_0=u,v_1,\mathrm{\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,\mathrm{\dots },v_k$ are pairwise distinct.

A temporal graph is defined by a pair $𝒢=(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 $𝒢$ and the labeling $\lambda$ is called the time labeling of $𝒢$. When $𝒢$ is clear from the context, we let $n=|V|$ denote the number of vertices of $𝒢$. A time-edge is a pair $(\{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 call $G_{\tau }=(V,E_{\tau })$ the snapshot of $𝒢$ 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 $\mathrm{\Delta }$-periodic if each edge appears periodically with period $\mathrm{\Delta }\in {\mathbb{N}}_{>0}$, that is $\tau \in \lambda (e)$ if and only if $\tau mod\mathrm{\Delta }\in \lambda (e)$. Such a temporal graph is represented by its list of time-edges up to time $\mathrm{\Delta }$. In the following, we always assume that the vertices of a temporal graph $𝒢$ are numbered from $1$ to $n$. We assume without loss of generality that its vertex set is $V=[n]$. We let $𝒯𝒢$ denote the set of all such temporal graphs.

A strict (respectively non-strict) temporal $uv$-walk is a walk $P=(v_0=u,v_1,\mathrm{\dots },v_k=v)$ in $G$ with associated time labels $({\tau }_1,\mathrm{\dots },{\tau }_k)$ such that ${\tau }_i\in \lambda (\{v_{i-1},v_i\})$ for each $i\in [k]$ and (respectively ${\tau }_1\le \mathrm{\cdots }\le {\tau }_k$). Equivalently, a temporal walk can be defined as the sequence of time-edges $(\{v_0,v_1\},{\tau }_1),\mathrm{\dots },(\{v_{k-1},v_k\},{\tau }_k)$ satisfying (respectively ${\tau }_1\le \mathrm{\cdots }\le {\tau }_k$). Moreover, $P$ has length $k$, departure time ${\tau }_1$, arrival time ${\tau }_k$, and duration ${\tau }_k-{\tau }_1+1$ (number of time steps spanned). A temporal $uv$-walk is called a temporal $uv$-path if the vertices $v_0,\mathrm{\dots },v_k$ are pairwise distinct. Note that a strict (respectively non-strict) temporal walk can always be transformed into a strict (respectively 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.

Classically, a temporal $uv$-path is said to be shortest, foremost, or fastest if it has minimum number of edges, minimum arrival time, or minimum duration, respectively among all temporal $uv$-paths. These notions indeed define some kinds of metrics that we now formalize. A distance matrix $D$ is any matrix of size $n\times n$ with values in $\mathbb{N}\cup \{\mathrm{\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, $D$ may violate the triangle inequality. A temporal path metric is defined as a function $M$ that associates a distance matrix $M(𝒢)$ to any temporal graph $𝒢\in 𝒯𝒢$. 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 time-edges (independently of any temporal graph). It defines a temporal path metric by associating to any temporal graph $𝒢\in 𝒯𝒢$ the matrix $C(𝒢)$ (respectively $\text{NS-}C(𝒢)$) such that $C{(𝒢)}_{uv}$ (respectively $\text{NS-}C{(𝒢)}_{uv}$) is the minimum cost of a strict (respectively non-strict) temporal $uv$-path in $𝒢$. We define $C{(𝒢)}_{uv}:=\mathrm{\infty }$ (respectively $\text{NS-}C{(𝒢)}_{uv}:=\mathrm{\infty }$) if no strict (respectively non-strict) temporal $uv$-path exists and $C{(𝒢)}_{uv}:=0$ (respectively $\text{NS-}C{(𝒢)}_{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 $\mathrm{Foremost}$, $\mathrm{Fastest}$, and $\mathrm{Shortest}$ denote the corresponding temporal path metrics, respectively. We also let $\mathrm{NS}-\mathrm{Foremost}$, $\mathrm{NS}-\mathrm{Fastest}$, and $\mathrm{NS}-\mathrm{Shortest}$ denote the respective variants for non-strict temporal paths. For example, given a temporal graph $𝒢$, and two vertices $u,v$ in $𝒢$, $\mathrm{Foremost}{(𝒢)}_{uv}$ is the earliest arrival time of a strict temporal $uv$-path in $𝒢$.

Given an integer $n$, the temporal graph realization problem consists of 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\}}^{\ast }$ of bits, given that the vertices of the temporal graph are $1,\mathrm{\dots },n$. More precisely, we define a predicate $P$ as a binary relation between the set $𝒯𝒢$ of all temporal graphs and the set ${\{0,1\}}^{\ast }$ of all bit sequences, that is $P$ is a subset of $𝒯𝒢\times {\{0,1\}}^{\ast }$. We then say that a temporal graph $𝒢$ satisfies a sequence $I$ of bits for $P$ if $(𝒢,I)\in P$. We equivalently say that $P(𝒢,I)$ is satisfied, or that $𝒢$ is a realization of $I$ for $P$. As a simple example, the lifetime of a temporal graph can be tested by the predicate $P(𝒢,\mathrm{\Lambda }):=\max ({\cup }_{e\in E}\lambda (e))=\mathrm{\Lambda }$ where $𝒢=(G,\lambda )$ and $\mathrm{\Lambda }$ encodes an integer (that we denote also by $\mathrm{\Lambda }$ with a slight abuse of notation). That is $P(𝒢,\mathrm{\Lambda })$ is satisfied when $\mathrm{\Lambda }$ is the last appearance time of a time-edge of $𝒢$. Given a predicate $P$ we thus define the following (very general) problem.

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

When considering an instance $(n,I)$ 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 $\mathrm{\Theta }(n^2)$. For brevity, given an input sequence $I$ encoding a distance matrix $D$, a realization $𝒢$ of $I$ for $M$-path is simply called an $M$-realization of $D$. If the metric $M$ is clear from the context, we simply say that $𝒢$ is a realization of $D$ or that $𝒢$ realizes $D$.

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

• $\mathrm{■}$

  $\mathrm{Prescribed}(𝒢,G_p):=$ the underlying graph of $𝒢$ is a subgraph of $G_p$,

• $\mathrm{■}$

  $\mathrm{Periodic}(𝒢,\mathrm{\Delta }):=$ $𝒢$ is $\mathrm{\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\times n$ distance matrix $D$ and a period $\mathrm{\Delta }$, whether there exists a $\mathrm{\Delta }$-periodic temporal graph that is a $\mathrm{Foremost}$-realization of $D$. Similarly, Prescribed Foremost-path TGR supposes that, in addition to $D$, the input includes a static graph $G_p$ called the prescribed graph, and asks whether there exists a $\mathrm{Foremost}$-realization of $D$ whose underlying graph is a subgraph of $G_p$. 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.

We reduce from Multicolored Clique [6].

Let $I:=(G=(V_1\cup \mathrm{\cdots }\cup V_k,E),k)$ be an instance of Multicolored Clique where for each , $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$ [22]. Let $V:=V_1\cup \mathrm{\cdots }\cup V_k$.

To obtain an instance $D$ of Fastest-path TGR as follows, we first describe the underlying graph, that is, the graph $G^{\prime }$ that contains an edge $\{u,v\}$ if and only if $D_{u,v}=1$. The graph $G^{\prime }$ is defined over the vertex set $V^{\prime }:=V\cup \{s,s^{\prime },s^{\prime \prime },t,t^{\prime },t^{\prime \prime }\}\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 1). We add edges between these vertices, such that $V^{\prime }\setminus V$ is a vertex cover of $G^{\prime }$. That is, there are no edges between the vertices of $V$ in $G^{\prime }$. We make $L$ into a clique and adjacent to all vertices of $V^{\prime }$ besides $s$ and $t$. Similarly, we make the vertices $s^{\prime }$ and $s^{\prime \prime }$ adjacent to all vertices of $V^{\prime }$ besides $t$ and make the vertices $t^{\prime }$ and $t^{\prime \prime }$ adjacent to all vertices of $V^{\prime }$ 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^{\prime },s^{\prime \prime }$, and $x_1$, and we make $t$ adjacent to $t^{\prime },t^{\prime \prime }$, and $x_{k+1}$.

This completes the underlying graph $G^{\prime }$ and thus all entries of the matrix $D$ of value $1$. Let $E^{\prime }$ denote the edges of $G^{\prime }$. Next, we define the remaining entries. Note that each vertex of $\{s^{\prime },s^{\prime \prime },t^{\prime },t^{\prime \prime }\}\cup L$ is adjacent to each other vertex of $V^{\prime }\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^{\prime },t^{\prime \prime }\}\cup L$. Similarly, we set $D_{t,p}:=D_{p,t}:=2k+3$ for each vertex $p\in \{s^{\prime },s^{\prime \prime }\}\cup L$. For each non-edge $\{u,v\}$ of $G$, 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^{\prime },s^{\prime \prime },t^{\prime },t^{\prime \prime }\}$ is a vertex cover of size $3k+7$ and that the largest entry in $D$ is $4k+5$.

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 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 1), $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$.

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.

$(\Rightarrow )$

Let $\lambda :E^{\prime }\to 2^{\mathbb{N}}$ be an edge labeling, such that $𝒢:=(G^{\prime },\lambda )$ realizes $D$. We show that $G$ has a clique of size $k$. Consider the entry $D_{s,t}=2k+2$. Since $𝒢$ 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 $𝒢$. 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 $𝒢$. This immediately implies that $P$ does not visit any vertex of $\{s^{\prime },s^{\prime \prime },t^{\prime },t^{\prime \prime }\}\cup L$, since $D_{s,t^{\prime }}=D_{s,t^{\prime \prime }}=D_{s^{\prime },t}=D_{s^{\prime \prime },t}=2k+3$ and $D_{s,\mathrm{\ell }}=D_{\mathrm{\ell },t}=2k+3$ for each vertex $\mathrm{\ell }\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^{\prime }[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 $𝒢$ realizes $D$. This implies that $\{a,b\}$ is an edge of $G$, as otherwise, $D_{a,b}=D_{b,a}$ is defined as $2k+3$. Consequently, $S$ is a clique of size $k$ in $G$.

$(\Leftarrow )$

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^{\prime }\to \mathbb{N}$, such that $𝒢:=(G^{\prime },\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^{\prime }$ (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$.

• $\mathrm{■}$

  Realizing all entries involving vertices of $V^{\mathbf{\prime }}\mathbf{\setminus }\mathbf{(}V\mathbf{\cup }X\mathbf{)}$ besides $D_{s\mathbf{,}t}$.

  We show that we can realize all these entries by only labeling edges that have at least one endpoint in $\{s^{\prime },s^{\prime \prime },t^{\prime },t^{\prime \prime }\}$. This proof is deferred to the full version.

• $\mathrm{■}$

  Realizing $D_{s\mathbf{,}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,\mathrm{\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 equal to its length, namely $D_{s,t}=2k+2$.

  The argument that this creates no paths that are too fast is deferred to the full version. It mainly comes from the fact that for any two vertices $a$ and $b$ of $P$ that are both from $V$, $\{a,b\}\in E$ since $S$ is a clique, and we have $D_{a,b}=2$.

So far, we have realized all entries of $D$ of value at least $2$ that involve at least one vertex of $\{s,s^{\prime },s^{\prime \prime },t,t^{\prime },t^{\prime \prime }\}\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^{\prime },s^{\prime \prime },t^{\prime },t^{\prime \prime }\}$. Let the vertices of $L$ be called $\{{\mathrm{\ell }}^{\ast },{\mathrm{\ell }}^{\ast \ast }\}\cup \{{\mathrm{\ell }}_i,{\mathrm{\ell }}_i^{\prime }\mid 1\le i\le k\}$.

• $\mathrm{■}$

  Realizing entries between vertices of $V$ of value $\mathrm{𝟐}k\mathbf{+}\mathrm{𝟑}$ 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,{\mathrm{\ell }}^{\ast }\}):=\alpha +1$ and $\lambda (\{v,{\mathrm{\ell }}^{\ast \ast }\}):=\alpha +2k+3$. For each vertex $x\in X$, we set $\lambda (\{x,{\mathrm{\ell }}^{\ast }\}):=\alpha$ and $\lambda (\{x,{\mathrm{\ell }}^{\ast \ast }\}):=\alpha +2k+4$. Finally, we set $\lambda (\{{\mathrm{\ell }}^{\ast },{\mathrm{\ell }}^{\ast \ast }\})=\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 in this time block 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^{\prime }$. That is, $D_{x,v}=2$. Then, there is a temporal path $(x,{\mathrm{\ell }}^{\ast },v)$ in this time block of duration 2. Similarly, the temporal path $(v,{\mathrm{\ell }}^{\ast \ast },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,{\mathrm{\ell }}^{\ast },{\mathrm{\ell }}^{\ast \ast },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$.

• $\mathrm{■}$

  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,{\mathrm{\ell }}_i\}):={\alpha }_i$ and $\lambda (\{{\mathrm{\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},{\mathrm{\ell }}_1^{\prime }\}):={\alpha }_{k+1}$ and $\lambda (\{{\mathrm{\ell }}_1^{\prime },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$.

• $\mathrm{■}$

  Realizing entries between vertices of $V$ of value $\mathrm{𝟐}$. 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 , $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,\mathrm{\dots },M_k$ be a partition of , 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 . 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}:={\bigcup }_{(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 , $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 ${\mathrm{\ell }}_i$ and ${\mathrm{\ell }}_i^{\prime }$ 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,{\mathrm{\ell }}_i\}):=\alpha$ for each $v_a\in A$ and $\lambda (\{v_b,{\mathrm{\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 }^{\prime },{\beta }^{\prime }]$ and set $\lambda (\{v_b,{\mathrm{\ell }}_i^{\prime }\}):=\alpha$ for each $v_b\in B$ and $\lambda (\{v_a,{\mathrm{\ell }}_i^{\prime }\}):=\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={\bigcup }_{i\in [1,k]}{E}_{M_i}$, this implies that we realized the entries $D_{u,v}$ and $D_{v,u}$ of value $2$ by the above time blocks for each edge $\{u,v\}\in E$.