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

Graph realization problems are a central area of research that has been studied extensively since the 1960s for undirected [5, 8, 9] and directed graphs [1, 4, 7]. Given a set of constraints, the objective is to find a graph that satisfies them, or to decide that no such graph exists. Restrictions on degrees [2, 5, 9], distances between vertices [3, 8, 16], eccentricities [12], and connectivity have been studied in detail. Recently, the study of realization problems on temporal graphs was started by Klobas et al. [10, 11]. Temporal graphs are graphs that have a fixed set of vertices and a set of edges that changes over time. Each edge of a static graph is assigned a set of timestamps at which it is active. Informally, a temporal path is a sequence of consecutive edges in the underlying static graph and corresponding timestamps at which they are active. We only consider the strict version of temporal paths where all timestamps on a path are strictly ascending. Klobas et al. and Mertzios et al. examined restrictions on the travel time between pairs of vertices in periodic temporal graphs: upper bounds as well as exact values [10, 11, 13]. In a periodic temporal graph, the set of timestamps is repeated periodically for all edges. There are several variants of the Temporal Graph Realization problem (TGR) that have been studied: In the periodic TGR, all timestamps are repeated periodically. The simple periodic TGR allows only one timestamp per period, unlike the multi-label periodic TGR. The constraints on fastest travel times can be either exact values or upper bounds. If the given underlying graph is a tree, we call the problem Temporal Tree Realization (TTR). In addition to communication networks such as social networks or satellite links, Klobas et al. mention transportation networks as examples of potential applications for the TTR [10, 11]. However, unlike the flow of information in satellite links, transportation networks typically do not carry passengers on an edge in both directions at the same time. Therefore, we examine the directed case as a natural generalization.

With an application in public transport in mind, the input graph models the infrastructure network where vertices correspond to locations of stops (or stations) and edges connect neighboring stops served by a bus, tram, train or the like. In public transport, typical values for the period $\mathrm{\Delta }$ are 5, 10, 15 or 20 minutes in urban transport, and 30, 60 or 120 minutes in long-distance train networks. The timestamp of an edge $(u,v)$ can be interpreted as the departure time of some vehicle at $u$. In a practical setting, traveling along an edge $e$ requires ${\mathrm{\ell }}_e\in \mathbb{N}$ time. An edge of length $\mathrm{\ell }$ can be equivalently replaced by a simple path of $\mathrm{\ell }$ edges of unit length. While such a transformation blows up the graph size, it does not change the complexity of the problem (since hardness results are established even for unit length graphs). For simplicity, we will therefore consider only unit-length graphs. We assume that a faster travel time is never detrimental and therefore consider upper bounds on the travel time instead of exact values. Since most public transportation lines run in both directions, we will mostly consider bidirected graphs throughout the paper. In tree structures this is necessary to ensure that every vertex is reachable from every other vertex.

Informally, given a directed, strongly connected graph as the underlying static graph as well as a period $\mathrm{\Delta }$ and upper bounds on the travel time between each pair of vertices, the objective is to compute a (single) timestamp for each directed edge such that a fastest temporal path between any two vertices does not exceed the given upper bound. The upper bounds between pairs of vertices can be interpreted as a guaranteed quality of service that must be met. The bounds are specified by a matrix $D$ of integers or $\mathrm{\infty }$. The latter means that we do not impose any restriction on the fastest path between the corresponding vertices. Motivated by transportation networks with fixed traffic lines, we consider only one global period instead of allowing different periods for all edges. Since waiting times are unavoidable and natural, for example, due to transfer times at transit hubs, we assume that there is a small amount of waiting time allowed on all paths and introduce a minimum slack parameter $k$ that specifies how much waiting time is at least acceptable on all routes.

Klobas et al. show that the Simple Periodic TGR with exact given fastest travel times is NP-hard even for a small constant period $\mathrm{\Delta }\ge 3$ [10, 11, Theorem 3]. However, if the underlying static graph is a tree, the problem is solvable in polynomial time [10, 11, Theorem 27]. It is fixed-parameter tractable (FPT) with respect to the feedback edge number of the underlying graph but W[1]-hard when parameterized by the feedback vertex number of the underlying graph [10, 11, Theorem 29 and Theorem 4]. While the Simple Periodic Temporal Graph Realization problem with exact given fastest travel times is solvable in polynomial time on trees, Mertzios et al. showed that the problem given upper bounds on the fastest travel times is NP-hard even if the underlying static graph is a tree [13]. This still holds for a constant period $\mathrm{\Delta }=5$ and when the input tree $G$ has a constant diameter or a constant maximum degree [13]. However, it is FPT with respect to the number of leaves in the input tree $G$ [13]. While Klobas et al. and Mertzios et al. only allow one timestamp per edge, Erlebach et al. consider several timestamps per edge [6]. They examine both the periodic and the non-periodic variant with exact given fastest travel times. Among other results, they show that the Multi-Label Periodic Temporal Graph Realization problem is NP-hard, even if the underlying static graph is a star for any number $\mathrm{\ell }\ge 5$ of labels per edge. All these models have in common that labels (periodic timestamps) are assigned to edges. Important related problem versions assign periodic labels to vertices. The Periodic Event Scheduling Problem (PESP), introduced by Serafini and Ukovich in 1989 [15], is widely used to schedule reoccurring events in public transport. Here the input is a so-called event-activity network $N=(V,A)$, a period $\mathrm{\Delta }$, and time windows $[{\mathrm{\ell }}_a,u_a]$ for each activity $a\in A$. The set $V$ models events (think of an arrival or departure of a vehicle at a stop) and the set $A\subset V\times V$ so-called activities. Activities model driving between neighboring stops, dwelling at a stop, transfers between different vehicles or safety constraints (minimal headways). In PESP, one seeks a periodic timestamp ${\pi }_v\in \{0,1,\mathrm{\dots },\mathrm{\Delta }-1\}$ for each event $v\in V$ such that $({\pi }_w-{\pi }_v)mod\mathrm{\Delta }\in [{\mathrm{\ell }}_{(v,w)},u_{(v,w)}]$ for all $(v,w)\in A$. The time window $[{\mathrm{\ell }}_a,u_a]$ of an activity models lower and upper bounds on the difference of the timestamps between the corresponding events. In other words, the difference $u_a-{\mathrm{\ell }}_a$ bounds the slack (waiting time) which can be introduced on activity $a$. In stark contrast to our model, these restrictions are local constraints between adjacent events, not global constraints between arbitrary events as considered in this paper. The PESP is known to be NP-complete for fixed $\mathrm{\Delta }\ge 3$ [15], but efficiently solvable for $\mathrm{\Delta }=2$ [14, page 87].

In this paper, we investigate the complexity of the Periodic Upper-Bounded Temporal Directed Graph Realization (DiTGR). In order to define the problem, we first need the following preliminaries: The duration of a temporal graph is the difference between the last and the first timestamp of the path, increased by one. Denote by $\widehat{d}(u,v)$ the distance of $u$ and $v$ in a static graph.

The restriction of DiTGR to inputs of such graphs derived from trees by adding two directed edges $(u,v)$ and $(v,u)$ for every undirected edge $\{u,v\}$ is called DiTTR.

Our main results are as follows:

1. 1.

   We provide efficiently checkable necessary conditions for feasibility in DiTTR when all or a subset of all pairs of vertices must be realized on shortest paths without waiting time. The basic insight is that the solvability for such instances depends on the distance between branching vertices of the given graph topology. We show:

   Lemma 1.

   An instance of DiTTR with $\forall u,v\in V:D_{u,v}=\widehat{d}(u,v)$ is realizable if and only if the distance of any pair of branching vertices is a multiple of $\mathrm{\Delta }/2$.

   We generalize this sufficient condition to a necessary one for instances in which no waiting is allowed on only some paths.

2. 2.

   We then introduce the parameter $k$, which specifies the minimum waiting time to be allowed on each path (the slack), i.e., for all pairs of vertices $u$ and $v$ we require that the duration bound $D_{u,v}$ is at least the distance $\widehat{d}(u,v)$ of $u$ and $v$ in the underlying static graph plus the constant $k$: $\forall u,v\in V:D_{u,v}\ge \widehat{d}(u,v)+k$. Note that the parameter $k$ is an implicit parameter of $D$. We call the version of DiTTR where the parameters $\mathrm{\Delta }$ and $k$ are fixed $\mathrm{\Delta }$-$k$-DiTTR. We fully characterize the complexity of the problem for bidirected tree topologies in terms of period $\mathrm{\Delta }$ and slack parameter $k$. For each possible combination of parameters $\mathrm{\Delta }$ and $k$, we either prove that the problem is easily solvable or hard, see Figure 1. We show:

   Theorem 2.

   For $\mathrm{\Delta }=1$ all instances of TGR and DiTGR are feasible.

   Theorem 3.

   All instances of DiTTR with $\mathrm{\Delta }\le k+1$ for odd $\mathrm{\Delta }$ and with $\mathrm{\Delta }\le k+2$ for even $\mathrm{\Delta }$ are feasible.

   Theorem 4.

   Instances of DiTTR with period $\mathrm{\Delta }=2$ are always feasible.

   Theorem 5.

   For the remaining parameters $\mathrm{\Delta }$ and $k$ (see Figure 1), the $\mathrm{\Delta }$-$k$-DiTTR is NP-complete.

   For some combinations of parameters, our NP-completeness reductions require gadgets of quadratic size in $\mathrm{\Delta }$, while for other combinations we even found gadgets of linear size (for details see Figure 1).

3. 3.

   For $\mathrm{\Delta }\ge 3$, we give a simple proof that the undirected version of the Upper-Bounded Periodic Temporal Tree Realization problem is NP-complete, even if the underlying static graph is a star and thus has a constant diameter¹¹1After our submission to SAND, the authors of [13] independently of us included essentially the same result in version 2 of their arxiv paper, while raising it as an open question in version 1..

4. 4.

   We also investigate in more detail the special case of a given period $\mathrm{\Delta }=2$. This turns out to be NP-complete in general (for both directed and undirected^††footnotemark: graphs), but can be solved efficiently on directed bipartite graphs and some special cases where the corresponding undirected graph contains at most one single odd cycle. The following theorem can be formulated as a generalization of Theorem 4:

   Theorem 6.

   All instances of DiTGR where the input is restricted to a directed bipartite graph $G=(U,V,E)$ with $E\subseteq (U\times V)\cup (V\times U)$ and period $\mathrm{\Delta }=2$ are feasible.