Brief Announcement: Revisiting the Realizability of Periodic Temporal Graphs with Bounded Stretch

Graph realization problems are a classic and well-researched area of graph theory [2, 8, 10, 12, 17, 18]. The objective is to determine if a graph exists that satisfies certain constraints. Among other restrictions, the following were considered: restrictions on connectivity [10, 18], degrees [2, 12, 16], distances between vertices [3, 17, 29] and eccentricities [21].

Recent research has also addressed such problems for temporal graphs. These are graphs with fixed vertices whose edges are only active at specific points in time, as indicated by the edge labels. The question here is whether the edges of a given graph can be assigned labels in such a way that the resulting temporal graph satisfies certain properties. In this setting, the following were examined, for example: Constraints on connectivity [1, 5, 9, 15, 22, 19], degree sequences [6] and reachability [4, 13, 11].

Periodic temporal graphs are an important subclass of temporal graphs. In these graphs, each edge becomes active once per period and then becomes active again once the period has elapsed. Paths can only traverse active edges, and traversing one edge requires one unit of time. Unlike the non-strict setting, where multiple edges can be traversed in one time step, we only consider the strict setting, in which the times edges are traversed must be strictly increasing. Such models are simplified abstractions of transportation networks, where vertices correspond to destinations and edges connect them periodically. Designing these networks can be seen as follows. We are given a static graph $G=(V,E)$. In public transport, for example, the vertex set $V$ corresponds to stations (or stops) and the edge set $E$ describes which pairs of stations are directly connected based on the available infrastructure. The design task is to decide when each edge should be available, i.e., to assign an integral label from the set $[0,\mathrm{\Delta }-1]$ to each edge defining its periodic activity. The challenge is to find a labeling that achieves certain objectives regarding travel time between pairs of vertices in the resulting periodic temporal graph. The duration of a temporal path $P$ is the travel time needed to traverse it. The fastest paths between vertices are those with the shortest duration. We denote the duration of a fastest temporal path from $u$ to $v$ in a given temporal graph by $\mathrm{dur}(u,v)$. The following problem has been considered by Klobas et al. [19] and Erlebach et al. [14]:

Asking for a such a temporal graph realization is often too restrictive. This motivates to relax the condition of realizing fastest paths between every pair of vertices. Erlebach et al. and Klobas et al. investigated restrictions on the exact duration of the fastest temporal paths in periodic temporal graphs [14, 20], while Mertzios et al. and Meusel et al. focused on upper bounds for durations [23, 24, 25]. The difference of the travel time of a path and the static distance of two vertices is called waiting time. The main focus of previous research has been on additive constraints for waiting times. However, it is well justified to allow for longer waiting times for longer distances. Mertzios et al. [24] defined the stretch, a multiplicative bound on the duration of a fastest path. They introduced the Stretched Temporal Graph Realization problem (STGR), where for some stretch $\alpha$, the duration of a fastest path must be at most $\alpha$ times the distance of the vertices.

Here, $\mathrm{dist}(u,v)$ denotes the distance between vertices $u$ and $v$ in the underlying static graph $G$. In this work, we revisit this problem and address open questions and previous gaps.

Mertzios et al. show that STGR is NP-hard, even if $\mathrm{\Delta }=3$, $\alpha =1$ and the graph has diameter 2 [24]. They also show that STGR is also NP-hard for $\mathrm{\Delta }=3$ with $\alpha \in [1,\frac{\mathrm{\Delta }+1}{2})$ and $\mathrm{\Delta }\ge 4$ with $\alpha \in [\frac{\mathrm{\Delta }}{2},\frac{\mathrm{\Delta }+1}{2})$ even if the diameter is in $𝒪(\mathrm{\Delta })$. They complement this by showing that STGR is FPT when parameterized either (i) by the neighborhood diversity of the input graph and $\mathrm{\Delta }$ or (ii) by the treewidth and diameter of the input graph and $\mathrm{\Delta }$. They further develop a local search algorithm and show that the optimization version of STGR, where the goal is to minimize the stretch, is hard to approximate within a factor of ${\mathrm{\Delta }}^{1-ϵ}$ or $2^{n^c}$ for each fixed and $c>1$, respectively. On the other hand, it is possible to compute a solution with stretch at most $\mathrm{\Delta }-\frac{\mathrm{\Delta }-1}{\min (\mathrm{rad}+1,\mathrm{diam})}$ in polynomial time, where $\mathrm{rad}$ and $\mathrm{diam}$ denote the radius and diameter of the given input graph, respectively.

In this work, we build on the work of Mertzios et al. [24]. Our results are as follows:

1. 1.

   First, we show that the existence of exact fastest temporal graphs can be efficiently decided for period $\mathrm{\Delta }=2$ for a class of underlying static graphs that generalize trees. A graph in which all shortest paths are unique is called geodetic [27, p. 105] or min-unique [28].

   Theorem 3.1.

   Deciding if there is a labeling with stretch $\alpha =1$ and $\mathrm{\Delta }=2$ for a geodetic graph can be solved in polynomial time.

   This follows from Theorem 10 of [25] as the same construction can be used for undirected graphs. This construction uses a reduction to 2-Coloring.

2. 2.

   Furthermore, we answer an open question from [24]: by providing an instance with period $\mathrm{\Delta }=2$ and stretch $\alpha >\frac{5}{3}$, we show the existence of instances with stretch $\alpha >\frac{\mathrm{\Delta }+1}{2}$.

   Lemma 3.2.

   For $\mathrm{\Delta }=2$, there are instances with stretch $\alpha =\frac{5}{3}>\frac{\mathrm{\Delta }+1}{2}=\frac{3}{2}$.

3. 3.

   This result is then extended to better understand the range of possible stretch values. Note that the stretch can never exceed the period $\mathrm{\Delta }$, since for every path a worst-case labeling assigns the same label to all its edges and thereby realizes a stretch factor below $\mathrm{\Delta }$. We show that for every period $\mathrm{\Delta }\ge 2$, there is an instance whose stretch $\alpha$ is arbitrarily close to $\mathrm{\Delta }$. This demonstrates that the stretch can approach its theoretical maximum on certain instances.

   Theorem 3.3.

   For every $\mathrm{\Delta }\ge 2$ and every integral factor $c>0$, there are instances with stretch $\alpha \ge \frac{2c\mathrm{\Delta }+1}{2c+1}>\frac{\mathrm{\Delta }+1}{2}$.

   Corollary 3.4.

   For every $\mathrm{\Delta }\ge 2$ there are instances with stretch $\alpha$ arbitrarily close to $\mathrm{\Delta }$.

4. 4.

   In many cases fastest paths which match the exact distance in the static graph, i.e. a stretch of $\alpha =1$, cannot be realized. Therefore, we ask how close we can come to the lower bound of $\alpha =1$. We complement the previous result by showing that for every period $\mathrm{\Delta }\ge 2$ there also exist instances whose optimal stretch is larger than $1$ but arbitrarily close to $1$. This illustrates that the lower end of the spectrum can likewise be approached.

   Theorem 3.5.

   For every $\mathrm{\Delta }\ge 2$, there are instances with arbitrarily small stretch $\alpha >1$.

5. 5.

   Finally, we extend the complexity landscape established in [24] to include the open case $\mathrm{\Delta }=2$, which we characterize for both the range addressed in earlier work for larger periods $\alpha \in [1,\frac{\mathrm{\Delta }+1}{2})$ as well as the newly-established case $\alpha \in [\frac{\mathrm{\Delta }+1}{2},\frac{\mathrm{\Delta }+3}{\mathrm{\Delta }+1})$.

   Theorem 3.6.

   For $\mathrm{\Delta }=2$, STGR is NP-hard for each $\alpha \in [1,\frac{3}{2})$.

   Theorem 3.7.

   For each $\alpha \in [\frac{3}{2},\frac{5}{3})$, STGR is NP-hard even if $\mathrm{\Delta }=2$.

   Corollary 3.8.

   For $\mathrm{\Delta }=2$ and each $\alpha \in [1,\frac{5}{3}=\frac{\mathrm{\Delta }+3}{\mathrm{\Delta }+1})$, STGR is NP-hard.

6. 6.

   Furthermore, as we showed hardness for $\alpha =1$, this also implies hardness for $\mathrm{\Delta }=2$ for the Fastest Periodic Temporal Graph Realization problem considered by Klobas et al., Erlebach et al., and Cauvi et al. [14, 20, 7]. This case was also left open by all previous works. The hardness result follows by taking an instance of STGR with $\mathrm{\Delta }=2$ and $\alpha =1$, and asking whether the matrix $D$ can be realized, where $D$ is the distance matrix of the underlying graph itself.

   Hence, we complete the following dichotomy for both problems with respect to $\mathrm{\Delta }$ by combining our hardness results for $\mathrm{\Delta }=2$ with the previous hardness results for each $\mathrm{\Delta }\ge 3$ for STGR [24] and Fastest Periodic Temporal Graph Realization [19, 14]: Both problems are trivial if $\mathrm{\Delta }=1$ and become NP-hard for each $\mathrm{\Delta }>1$.

   Theorem 3.9.

   STGR and Fastest Periodic Temporal Graph Realization are polynomial time solvable if $\mathrm{\Delta }=1$ and NP-hard for each $\mathrm{\Delta }\ge 2$.

For future work, many aspects are worth further consideration. It remains to determine whether STGR is also NP-hard for $\mathrm{\Delta }\ge 3$ for values of at least $\alpha =\frac{\mathrm{\Delta }+1}{2}$. Furthermore, the case of $\mathrm{\Delta }>3$ with $\alpha \in [1,\frac{\mathrm{\Delta }}{2})$ has not been considered yet. Meusel et al. [25] showed that there are parameter combinations for the Temporal Tree Realization problem that are hard for undirected graphs but become tractable for bidirected graphs of the same structure. It would be interesting to show whether similar effects occur for STGR.

Another direction is to consider the case of STGR in restricted graph classes. For example, can STGR be solved in polynomial time on planar graphs? Our hardness proofs involve Not-All-Equal 3-Sat, which is known to be solvable in polynomial time if the formula is planar [26]. Finally, it might be worth to consider a multi-label version of the problem, where each edge is allowed up to $\mathrm{\ell }$ labels per period.