Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

First we observe that a vertex with a static degree of at least 6 corresponds to a vertex with a static degree of at least 3 in the underlying undirected tree. As can easily be seen from the following argument, all branching vertices have fixed arrival and departure times, i.e. all incoming edges of a branching vertex have the same label, as well as all outgoing edges. Let $v$ be a branching vertex and let for some neighbor $w$ of $v$ w.l.o.g. $\lambda (w,v)=\mathrm{\Delta }-1$. For all outgoing edges $(v,x)$ of $v$ excluding $(v,w)$ this means $\lambda (v,x)=0$ as no waiting is allowed. This in turn requires $\lambda (x,v)=\mathrm{\Delta }-1$ for the remaining incoming edges $(x,v)$. The latter implies $\lambda (v,w)=0$. Let $y$ and $z$ be two branching vertices with distance $\widehat{d}(y,z)$ and let $t(y)$, $t(z)$ be the timestamps of their incoming edges. Then the timestamps of their outgoing edges have to be $(t(y)+1)mod\mathrm{\Delta }$ and $(t(z)+1)mod\mathrm{\Delta }$, respectively. Let $P=(y=v_0,v_1,t_1)\mathrm{\dots }(v_{\mathrm{\ell }-1},z=v_{\mathrm{\ell }},t_{\mathrm{\ell }})$ be a fastest temporal $y$-$z$-path and its length $\mathrm{\ell }$. By Definition 4, the duration of $P$ is $d(P)=t_{\mathrm{\ell }}-t_1+1$. We note that for any feasible solution $d(P)=d(y,z)=\widehat{d}(y,z)$. To not exceed $D_{y,z}=\widehat{d}(y,z)$ the following must hold: $\exists i\in {\mathbb{N}}_0:i\cdot \mathrm{\Delta }+t(z)=t_{\mathrm{\ell }}=d(P)+t_1-1=\widehat{d}(y,z)+(t(y)+1)-1$. By definition and due to symmetry, this means: $t(z)\equiv \widehat{d}(y,z)+t(y)(mod\mathrm{\Delta })$ and $t(y)\equiv \widehat{d}(y,z)+t(z)(mod\mathrm{\Delta })$. Therefore, the following must also apply: $0\equiv 2\cdot \widehat{d}(y,z)(mod\mathrm{\Delta })$.

If the distance of any pair of branching vertices is a multiple of $\mathrm{\Delta }/2$, we can start at an arbitrary branching vertex r and set its arrival time to $\mathrm{\Delta }-1$. Without waiting, the departure time of this vertex is $0$. Then we can assign labels iteratively as enforced by already labeled adjacent edges as specified in Algorithm 1. (However, we emphasize that we have to choose the root as a branching vertex here.) As all branching vertices have a distance of a multiple of $\mathrm{\Delta }/2$, this procedure assigns them fixed arrival and departure times with no waiting. Hence, with such a labeling there is a temporal path between every pair of vertices without waiting. If there are no branching vertices at all, we can assign increasing labels independently for both directions of the path. $◀$

This necessary and sufficient condition implies immediately a linear time algorithm for these instances. This does not contradict our observation that the problem becomes NP-complete if waiting times are allowed, i.e., $D_{u,v}\ge \widehat{d}(u,v)$. This is even true for the slack parameter $k=0$, since $k$ is a only lower bound for the allowed waiting time.

Obviously, all labels are forced to have the same value $\lambda =0$. Since the period $\mathrm{\Delta }$ is 1, there is no waiting time at all at any vertex. So every shortest path in the underlying static graph can be realized as a fastest temporal path with duration equal to its length, which means that all instances are realizable. $◀$

All instances with $\mathrm{\Delta }\le k+1$ for odd $\mathrm{\Delta }$ and with $\mathrm{\Delta }\le k+2$ for even $\mathrm{\Delta }$ can be realized by a simple algorithm detailed in Algorithm 1. First, choose an arbitrary vertex $r$ as the root. Then, traverse the tree and, depending on its distance from the root and whether it points to or away from the root, assign a label to each edge as specified in Algorithm 1. Two realizations computed by this algorithm can be seen in Figure 3. There are three cases for the direction of a path between two vertices:

1. 1.

   The path runs entirely towards the root.

2. 2.

   The path leads strictly away from the root.

3. 3.

   The path first heads towards the root and then changes direction away from it.

In the first two cases there is no delay at all. For the last case, it is easy to see that waiting time can only occur when changing direction and therefore only once per path. Thus, the maximum waiting time is at most $\mathrm{\Delta }-1$ on any path. If $\mathrm{\Delta }$ is even, the waiting time is at most $\mathrm{\Delta }-2$, because by construction incoming and outgoing edges of every vertex are assigned values of different parity. Hence, there cannot be two identical labels in a row on a path. $◀$

This follows from Theorem 7 with $\mathrm{\Delta }=2$ and $k=0$ and can easily be generalized to directed bipartite graphs.

Given any directed, bipartite graph $G=(U,V,E)$ with $E\subseteq (U\times V)\cup (V\times U)$ and $\mathrm{\Delta }=2$, set $\lambda (e_0)=0$ for all $e_0\in E\cap (U\times V)$ and $\lambda (e_1)=1$ for all $e_1\in E\cap (V\times U)$. Since every path in $G$ alternates between vertices in $U$ and vertices in $V$, there is no waiting time. $◀$

A graph where all shortest paths are unique is called geodetic [18, p. 105] or min-unique [20].

We show this by giving a reduction to 2–Vertex-Coloring as shown in Figure 4. Note that as the graph is geodetic there is by definition a unique shortest path in the underlying static graph for every pair of vertices $(v,w)$ [18, p. 105]. Given an instance $(G=(V,E),D,\mathrm{\Delta })$, let $𝙿\subseteq 2^E$ be the set of all edge sets of paths in $G$ and let ${𝙿}_{𝚎}\subseteq 𝙿\setminus \{\mathrm{\varnothing }\}$ be the set of edge sets of all shortest paths where no waiting time is allowed. We construct an undirected auxiliary graph $G^{\prime }=(E,E^{\prime })$ with $E^{\prime }=\{\{(x,y),(y,z)\}\mid \exists P\in {𝙿}_{𝚎}:(x,y),(y,z)\in P\}$. This means that the labeling has to be chosen such that $\lambda (x,y)=(1-\lambda (y,z))mod\mathrm{\Delta }$ for any $\{(x,y),(y,z)\}\in E^{\prime }$ since waiting at $y$ on the way from $x$ to $z$ is not allowed. As $\mathrm{\Delta }=2$, this is true if and only if $\lambda (x,y)\ne \lambda (y,z)\text{ for all }\{(x,y),(y,z)\}\in E^{\prime }$. Thus, given a feasible coloring $C:E\to \{0,1\}$ for $G^{\prime }$, we can set $\lambda (x,y)=C((x,y))\text{ for all }(x,y)\in E$. Therefore, the instance is feasible if and only if $G^{\prime }$ is bipartite which can be decided in polynomial time. $◀$

In sharp contrast, we will show in the following section, that DiTGR is NP-complete for general graphs even for the special case that $\mathrm{\Delta }=2$.

We reduce 3-SAT to DiTGR as follows: Given a 3-CNF formula $\mathrm{\Phi }=\{C_1,\mathrm{\dots },C_m\}$ with a set of variables $X$, construct a graph $G=(V,E)$ with

as shown in Figure 5 and set the upper bounds $D$ as follows:

All other values of $D$ are set to $\mathrm{\infty }$. For each pair of vertices with a finite distance bound, this enforces that we have to realize a labeling without waiting on some shortest path. Let without loss of generality $\lambda (T,1)=0$. Then the upper bounds $D$ between the vertices $2$, $3$ and $F$ enforce that $\lambda (T,1)=\lambda (1,T)=\lambda (T,0)=\lambda (0,T)=\lambda (1,0)=\lambda (0,1)=0$ and $\lambda (3,T)=\lambda (T,3)=\lambda (2,1)=\lambda (1,2)=\lambda (F,0)=\lambda (0,F)=1$.

For each variable $x\in X$, there exist two possible shortest paths from $0$ and therefore from $T$ respectively $F$ to $x^{\prime }$: one over $x$ and one over $\overline{x}$. Since the paths from $T$ and the paths from $F$ start with different labels ($0$ respectively $1$), they also have to continue with different labels to avoid waiting. This means $\lambda (0,x)=1-\lambda (0,\overline{x})=1-\lambda (x,x^{\prime })=\lambda (\overline{x},x^{\prime })$. The same holds for the opposite direction: $\lambda (x,0)=1-\lambda (\overline{x},0)=1-\lambda (x^{\prime },x)=\lambda (x^{\prime },\overline{x})$. Then $D_{x,\overline{x}}=D_{\overline{x},x}=2$ enforces that the labels in both directions have to be the same, i.e. $\lambda (0,x)=\lambda (x,0)$: Going without waiting from $x$ to $\overline{x}$ over 0 requires $\lambda (x,0)=1-\lambda (0,\overline{x})=\lambda (0,x)$. Going over $x^{\prime }$ requires $\lambda (x,x^{\prime })=1-\lambda (x^{\prime },\overline{x})=\lambda (x^{\prime },x)$ which results in the same labeling.

For every clause $C=\{l_1,l_2,l_3\}$ there are three shortest paths from $T$ to $C$: each one leads over one of the literals $l_1$, $l_2$ and $l_3$ in C. A fastest path can only have a duration of 3 as enforced by the upper bounds, if the edge $(0,l)$ to the literal $l$ has the label $1$. Therefore at least one of the edges $(0,l_1)$, $(0,l_2)$, $(0,l_3)$ has to have the label $1$.

An assignment $a:X\mapsto \{0,1\}$ corresponds to the labeling of the edges from $0$ to the variables, i.e. $\lambda (0,x)=\lambda (x,0)=a(x)$ for all $x\in X$. If $\mathrm{\Phi }\in$ 3-SAT and $a$ is a satisfying assignment, then we extend $\lambda$ to $\lambda (l,C)=\lambda (C,l)=1-\lambda (0,l)$ for every clause $C\in \mathrm{\Phi }$ which is satified by the literal $l$, which leads to no waiting on the path between $T$ and $C$ and thus $(G,D,2)\in$ DiTGR. If $(G,D,2)\in$ DiTGR with the labeling $\lambda$, then the corresponding assignment $a$ must satisfy $\mathrm{\Phi }\in$ 3-SAT. $◀$ From the proof, we can therefore conclude:

Let $I=(G=(V,E),D,\mathrm{\Delta })$ be an instance of TTR and $(\widehat{G},\widehat{D},\mathrm{\Delta })$ be a gadget enforcing $\lambda (a,b)=\lambda (b,a)$. First we create a directed graph $G^{\prime }$ by replacing every undirected edge of $G$ by two antiparallel directed edges. Then we enforce $\lambda (v,w)=\lambda (w,v)$ for every edge $e=\{u,v\}\in E$ by inserting a copy of the gadget into $G^{\prime }$, identifying $(u,v)$ with $(a,b)$ and $(v,u)$ with $(b,a)$, and setting $D^{\prime }$ consistently with $D$ and $\widehat{D}$. Since the resulting graph is a tree ($G$ and the gadget $G^{\prime }$ are trees that are connected by one common edge) and any two copies of the gadget share at most one common vertex the construction does not produce any shortcuts.

Thus, every valid solution ${\lambda }^{\prime }$ for DiTTR with respect to $G^{\prime }$ and $D^{\prime }$ immediately implies a valid solution $\lambda$ for TTR if we set $\lambda (\{u,v\})={\lambda }^{\prime }((u,v))={\lambda }^{\prime }((v,u))$. Conversely, we can construct a valid solution for DiTTR from a valid solution for TTR by setting ${\lambda }^{\prime }((u,v))={\lambda }^{\prime }((v,u))=\lambda (\{u,v\})$. Since the gadget is feasible, there exists a solution where the timestamp of the edges $(a,b)$ and $(b,a)$ is 0. We can then set the labels in the copy of the gadget for each edge $\{u,v\}$ to a solution that is shifted modulo $\mathrm{\Delta }$ by $\lambda (\{u,v\})$. Since $\mathrm{\Delta }$ and $k$ are fixed, this construction is possible in polynomial time if the time to compute the gadget is a function of only $\mathrm{\Delta }$ and $k$. $◀$

We construct this gadget as follows:

All other values of $D$ are set to $\mathrm{\infty }$. As no waiting time is allowed, vertex 3 has a fixed arrival/departure time (see proof for ˜5). Let $t(3)$ be the timestamps of its incoming edges. For the sake of convenience, let us assume that $t(3)=\mathrm{\Delta }-1$ and that the departure time is $0$. This implies $\lambda (3,4)=0$ and therefore $\lambda (3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor ,4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor )=\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$. Symmetrically, the following is also true: $\lambda (4,3)=\mathrm{\Delta }-1$ and $\lambda (4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor ,3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor )=\mathrm{\Delta }-1-\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$. As $\mathrm{\Delta }$ is odd this means $\lambda (4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor ,3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor )=\lambda (3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor ,4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor )=\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$. Therefore we can enforce $\lambda (v_1,v_2)=\lambda (v_2,v_1)$ for the vertices $v_1=3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$ and $v_2=4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor$. $◀$ For $\mathrm{\Delta }=3$ the gadget is shown in Figure 8. In this gadget, $\lambda (5,4)=\lambda (4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor ,3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor )=\lambda (3+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor ,4+\lfloor \frac{\mathrm{\Delta }}{2}\rfloor )=\lambda (4,5)$ is enforced. This gadget has a size linear in $\mathrm{\Delta }$ and only six values in $D$ that are not infinity. Furthermore, $D$ is symmetric.

The following gadget enforces $\lambda (3+\lfloor \frac{k}{2}\rfloor ,3+\lceil \frac{k}{2}\rceil )=\lambda (3+\lceil \frac{k}{2}\rceil ,3+\lfloor \frac{k}{2}\rfloor )$:

All other values of $D$ are set to $\mathrm{\infty }$. Let w.l.o.g. $\lambda (k+4,k+3)=0$. We show that there is only one solution by looking at possible values of $\lambda$ for the edges from and to leaves. We observe $\widehat{d}(k+4,1)=\widehat{d}(2,k+5)=k+2$. As there is no waiting required but at most a waiting time of $k$ allowed on the path from vertex $k+4$ to vertex $1$, the following must hold: $\lambda (3,1)\in \{k+1,\mathrm{\dots },2\cdot k+1\}$ (recall $\mathrm{\Delta }\ge 4\cdot k+1$). That means in turn that $\lambda (2,3)$ is in the range $\{0,1,\mathrm{\dots },2\cdot k\}$. The corner case $\lambda (2,3)=0$ occurs when $\lambda (3,1)=k+1$ and with maximum waiting time. Conversely, with $\lambda (3,1)=2\cdot k+1$ and with no waiting time, $\lambda (2,3)$ is at most $2\cdot k$.

In the same way we can conclude that $\lambda (k+3,k+5)\in \{k+1,\mathrm{\dots },4\cdot k,(4\cdot k+1)mod\mathrm{\Delta }\}$. Because $\mathrm{\Delta }\ge 4\cdot k+1$ only the last item may be affected by the modulo operator and would be assigned the value 0 in that case. Suppose now that $\lambda (k+3,k+5)\in \{k+2,\mathrm{\dots },4\cdot k,(4\cdot k+1)mod\mathrm{\Delta }\}$, i.e. any other possible value than $k+1$. Then $d(k+4,k+5)\ge k+2-0+1=k+3>D_{k+4,k+5}=k+2$ and thus, the solution cannot be valid for these values of $\lambda (k+3,k+5)$. Therefore $\lambda (k+3,k+5)=k+1$ which means that there is no waiting time at all on the paths from $k+4$ to $1$ and from $2$ to $k+5$ but a waiting time of $k$ on the paths from $2$ to $1$ and from $k+4$ to $k+5$. Thus, $\lambda (3+\lfloor \frac{k}{2}\rfloor ,3+\lceil \frac{k}{2}\rceil )=\lceil \frac{k}{2}\rceil =\lambda (3+\lceil \frac{k}{2}\rceil ,3+\lfloor \frac{k}{2}\rfloor )$. Therefore we can enforce $\lambda (v_1,v_2)=\lambda (v_2,v_1)$ for the vertices $v_1=3+\lceil \frac{k}{2}\rceil$ and $v_2=3+\lfloor \frac{k}{2}\rfloor$. $◀$ Figure 8 shows the gadget for $\mathrm{\Delta }=5$ and $k=1$. This gadget also has a size linear in $k$ and therefore also in $\mathrm{\Delta }$ and a constant amount of values in $D$ that are not infinity. The constraints $D$ are not symmetric; however, setting them as such doesn’t affect the proof: For all feasible solutions $\lambda (3+\lfloor \frac{k}{2}\rfloor ,3+\lceil \frac{k}{2}\rceil )=\lambda (3+\lceil \frac{k}{2}\rceil ,3+\lfloor \frac{k}{2}\rfloor )$ holds and there is still at least one feasible solution.

The rough idea is that we need a break in symmetry. So we start with two copies of a known gadget (see Lemma 14) that we merge at the edges for which we can enforce equality of the labels. The resulting gadget would be infeasible, so we relax the constraints $D$ slightly, making them asymmetric, and thereby obtain a feasible gadget of constant size with the claimed property.

The following gadget enforces $\lambda (4,5)=\lambda (5,4)$. It is shown in Figure 8. On the path from vertex 8 to vertex 1, waiting time is allowed, but only at vertex 4. Symmetrically, there can be no waiting time on the path from 2 to 6 except at vertex 5.

All other values of $D$ are set to $\mathrm{\infty }$. Let w.l.o.g. $\lambda (8,6)=1$. As no waiting is allowed at vertex $6$, it has a fixed arrival/departure time of $2$. This leads to $\lambda (5,6)=\lambda (7,6)=1$, $\lambda (6,5)=\lambda (6,7)=\lambda (6,8)=2$ and combined with $D_{8,4}=3$ to $\lambda (5,4)=3$. On the path from vertex $2$ to vertex $7$, waiting time is only allowed at vertex $5$ and must not exceed one time step. Thus, $\lambda (4,5)\in \{3,0\}$ and $\lambda (3,4)\in \{2,3\}$. Furthermore the following holds: $\lambda (4,3)\in \{0,1\}$. Because there can be no waiting time at vertex 3, it has a fixed arrival/departure time and $\lambda (3,4)-\lambda (4,3)\equiv 1(mod\mathrm{\Delta })$. Therefore only $\lambda (4,3)=1$ and $\lambda (3,4)=2$ is feasible. Hence, $\lambda (4,5)=3=\lambda (5,4)$. $◀$

We show the result for $k=\mathrm{\Delta }-2$. This inherits to all smaller $k$ since the limitation for those is weaker and thus complements to Theorem 7 for odd $\mathrm{\Delta }$.

The following gadget enforces $\lambda (0,\overline{0})=\lambda (\overline{0},0)$ as shown in Figure 10:

All other values of $D$ are set to $\mathrm{\infty }$. In the following, we will call the part that consists of the vertices $\{0,\mathrm{\dots },(k+1)\mathrm{\Delta }\}$ the main path. We call the direction from $0$ to $(k+1)\mathrm{\Delta }$ the forward direction. The reverse direction is called the backward direction.

We investigate the increase of the maximum waiting time in forward direction to (respectively in backward direction from) $i$ defined by

We show that both $w_{\lambda }^{+}$ and $w_{\lambda }^{-}$ have to increase after every $\mathrm{\Delta }$ edges on the main path. This means there is waiting time in one direction on the main path at all vertices $i\cdot \mathrm{\Delta }$.

We have $w_{\lambda }^{+}(0)=w_{\lambda }^{-}(0)=-\mathrm{\infty }$ since there is no . We can easily choose $\lambda$ such that $w_{\lambda }^{+}(1)=w_{\lambda }^{-}(1)=0$. An equivalent inductive definition is