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

Julia Meusel, Matthias Müller-Hannemann, Klaus Reinhardt · 2025

Read Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases by Julia Meusel, Matthias Müller-Hannemann, Klaus Reinhardt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-07920.txt.

Introduction

Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt mapped the hardness of designing train and bus timetables in 2025. A periodic timetable repeats through the day, and its quality is caught by a grid of promised fastest travel times between major stops. Realization asks whether departure times exist achieving at least those promises. Requiring exact equality is too rigid, so the authors add a slack setting bounding the waiting time any fastest path may include. And they allow each direction of a link its own departure time, as real networks do.

Restricting to tree-shaped networks, they give a complete characterization of when the realization problem is easy and when it is hard. As a function of just two amounts: the period length and the minimum slack. Such a full hardness landscape tells timetable builders exactly which relaxations buy them a lean method.

Catalog record

CREATORJulia Meusel, Matthias Müller-Hannemann, Klaus Reinhardt
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-07920

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases Julia Meusel, Matthias Müller-Hannemann, Klaus Reinhardt Abstract We study the complexity of the directed periodic temporal graph realization problem. This work is motivated by the design of periodic schedules in public transport with constraints on the quality of service. Namely, we require that the fastest path between (important) pairs of vertices is upper bounded by a specified maximum duration, encoded in an upper distance matrix D D . While previous work has considered the undirected version of the problem, the application in public transport schedule design requires the flexibility to assign different departure times to the two directions of an edge. A problem instance can only be feasible if all values of the distance matrix are at least shortest path distances. However, the task of realizing exact fastest path distances in a periodic temporal graph is often too restrictive. Therefore, we introduce a minimum slack parameter k k that describes a lower bound on the maximum allowed waiting time on each path. We concentrate on tree topologies and provide a full characterization of the complexity landscape with respect to the period Δ \Delta and the minimum slack parameter k k , showing a sharp threshold between NP-complete cases and cases which are always realizable. We also provide hardness results for the special case of period Δ = 2 \Delta=2 for general directed and undirected graphs. \declaretheorem [name=Lemma, sibling=theorem]lem \declaretheorem [name=Theorem, sibling=theorem]thm Martin Luther University Halle-Wittenberg, [email protected]://orcid.org/0009-0001-2880-1390 Martin Luther University Halle-Wittenberg, [email protected]://orcid.org/0000-0001-6976-0006 Martin Luther University Halle-Wittenberg, [email protected]://orcid.org/0009-0002-7002-4051 ccs Theory of computation Graph algorithms analysis ccs Mathematics of computing Discrete mathematics keywords Periodic timetabling, service quality, temporal graph, graph realization, complexity, fastest temporal path † † runningtitle: Directed Temporal Tree Realization for Periodic Public Transport † † runningauthor: J. Meusel, M. Müller-Hannemann, K. Reinhardt † † copyright: Julia Meusel, Matthias Müller-Hannemann, Klaus Reinhardt † † related-version: A 5-page version has appeared as a brief announcement in SAND 2025 : https://doi.org/10.4230/LIPIcs.SAND.2025.21 † † related-version: Full version to appear in ATMOS 2025 : https://doi.org/10.4230/OASIcs.ATMOS.2025.8 1 Introduction Designing periodic schedules for public transport is notoriously difficult. Periodic schedules are desirable for several practical and operational reasons. They are easier to memorize, and travelers can better plan their journeys if services run at regular intervals. Periodicity also enables coordinated connections between different lines at central hubs and simplifies crew and vehicle scheduling. In this paper, we consider the quality of service provided by a periodic schedule from a passenger’s perspective. Specifically, we address the question of whether it is possible to design a periodic schedule for a given network that guarantees travel time bounds between important pairs of stops. We model this as a graph realization problem. Graph realization problems are a central area of research that has been studied extensively since the 1960s for undirected [ 6 , 9 , 10 ] and directed graphs [ 1 , 4 , 8 ] . 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 , 6 , 10 ] , distances between vertices [ 3 , 9 , 22 ] , eccentricities [ 14 ] , and connectivity [ 5 , 11 ] have been studied in detail. Recently, the study of realization problems on temporal graphs was started by Klobas et al. [ 12 , 13 ] . 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. In a periodic temporal graph, the set of timestamps is repeated periodically for all edges. Informally, a temporal path is a sequence of consecutive edges in the underlying static graph and corresponding increasing timestamps at which they are active. 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 [ 12 , 13 , 16 ] . This leads to 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 [ 12 , 13 ] . 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. Since most public transportation lines run in both directions, we will mostly consider bidirected graphs. In tree structures this is necessary to ensure that every vertex is reachable from every other vertex. 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 \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 \ell_{e}\in\mathbb{N} time. An edge of length \ell can be equivalently replaced by a simple path of \ell edges of unit length as shown in Figure 3 . 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. {subfigure} [t]0.23 {subfigure} [t]0.74 Figure 1: An infrastructure network G labeled with distances (in minutes) between vertices (stops). Figure 2: A graph in which phantom stops have been inserted so that all edges have unit length. Here, the labels define a schedule where each value denotes a departure time with respect to a global period of \Delta=5 . The resulting graph with its labeling forms a periodic temporal graph. Figure 3: Example: The infrastructure network G=(V,E) with edge lengths (left) can be modelled with unit length edges by inserting phantom stops between already existing stops (right). No upper bounds are set for travel times from and to these phantom stops. Suppose we have a period of \Delta=5 and the following upper bounds: D_{a,e}=17 , D_{a,b}=9 , and D_{f,b}=13 . Assuming, without loss of generality, that the label of the edge connecting a to the first phantom stop is assigned the timestamp 0, the given upper bounds on the travel times enforce the black edge labels. A temporal graph with edge labels as specified respects these upper bounds. The timestamps

Read the complete text