Realizing temporal transportation trees

George B. Mertzios, Hendrik Molter, Paul G. Spirakis

Abstract

In this paper, we study the complexity of the periodic temporal graph realization problem with respect to upper bounds on the fastest path durations among its vertices. This constraint with respect to upper bounds appears naturally in transportation network design applications where, for example, a road network is given, and the goal is to appropriately schedule periodic travel routes, while not exceeding some desired upper bounds on the travel times. In our work, we focus only on underlying tree topologies, which are fundamental in many transportation network applications. As it turns out, the periodic upper-bounded temporal tree realization problem (TTR) has a very different computational complexity behavior than both (i) the classic graph realization problem with respect to shortest path distances in static graphs and (ii) the periodic temporal graph realization problem with exact given fastest travel times (which was recently introduced). First, we prove that, surprisingly, TTR is NP-hard, even for a constant period $\Delta$ and when the input tree $G$ satisfies at least one of the following conditions: (a) $G$ is a star, or (b) $G$ has constant maximum degree. Second, we prove that TTR is fixed-parameter tractable (FPT) with respect to the number of leaves in the input tree $G$, via a novel combination of techniques for totally unimodular matrices and mixed integer linear programming.

Introduction

Graph realization is a fundamental problem in combinatorial optimization, typically involving the construction of a graph that meets specific distance requirements between its nodes. In modern infrastructure planning, however, static distances are often insufficient. We must consider temporal graphs, where edges are only available at specific times, often following a periodic schedule $\Delta$. This is the reality of rail networks, flight schedules, and bus routes.

This paper investigates the Periodic Upper-Bounded Temporal Tree Realization (TTR) problem. Unlike previous work that focused on exact travel times, TTR seeks to determine if a periodic schedule exists such that the fastest travel times between nodes do not exceed given upper bounds. While trees are the simplest non-trivial topologies, the introduction of temporal constraints and upper bounds creates a surprisingly complex landscape.

The Computational Complexity of TTR

One might expect that satisfying "at most" constraints (upper bounds) would be easier than satisfying exact travel times. However, the authors demonstrate the opposite. While exact realization on trees can be solved in polynomial time, TTR is NP-hard even under very restrictive conditions. Specifically, the problem remains difficult for star graphs when the period $\Delta \ge 3$, and for graphs with constant maximum degree.

A path-based gadget used in the NP-hardness reduction for the TTR problem.

The hardness is established through reductions from problems like $x$-COLORING and Monotone Not-All-Equal 3-SAT. The figure above illustrates a path-based construction where edge labels (e.g., $5i+3$) are used to encode variable assignments into temporal constraints. This demonstrates that even a simple path structure can harbor significant computational complexity when periodic scheduling is involved.

A notable exception is the case where $\Delta = 2$. In this specific scenario, the problem on trees can be reduced to 2-SAT and solved efficiently. Furthermore, for $\Delta = 2$, travel durations are symmetric, a property that fails for larger periods.

Fixed-Parameter Tractability via Network Matrices

Despite the general NP-hardness, the paper identifies a key structural parameter that makes the problem tractable: the number of leaves $\ell$ in the tree. In many transportation hubs, the number of terminal "spokes" is relatively small compared to the total number of stations along those spokes.

The authors develop a Fixed-Parameter Tractable (FPT) algorithm with a running time of $f(\ell) \cdot n^{O(1)}$. The core of this approach involves reducing TTR to a series of Mixed Integer Linear Programming (MILP) instances. The challenge with MILP is generally its exponential complexity; however, the authors prove that the constraint matrix for the continuous variables in their formulation is a network matrix.

Network matrices are a subset of totally unimodular matrices. This mathematical property ensures that the linear programming relaxation of the problem will yield integer solutions for certain variables. By limiting the number of true integer variables to a function of the number of leaves $\ell$, the authors leverage specialized MILP solvers to achieve efficiency.

Conclusion and Future Directions

This research highlights a significant gap between exact and upper-bounded temporal realization. While the latter is generally hard, the identification of leaf-count as a tractable parameter provides a practical path forward for designing hub-and-spoke networks.

Future work remains to be done on graphs with cycles, which are common in urban transit rings. Additionally, exploring other graph parameters like treewidth or distance to clique could broaden the applicability of these algorithmic techniques to more general network topologies.

Summary updated

Abstract

In this paper, we study the complexity of the periodic temporal graph realization problem with respect to upper bounds on the fastest path durations among its vertices. This constraint with respect to upper bounds appears naturally in transportation network design applications where, for example, a road network is given, and the goal is to appropriately schedule periodic travel routes, while not exceeding some desired upper bounds on the travel times. In our work, we focus only on underlying tree topologies, which are fundamental in many transportation network applications. As it turns out, the periodic upper-bounded temporal tree realization problem (TTR) has a very different computational complexity behavior than both (i) the classic graph realization problem with respect to shortest path distances in static graphs and (ii) the periodic temporal graph realization problem with exact given fastest travel times (which was recently introduced). First, we prove that, surprisingly, TTR is NP-hard, even for a constant period $\Delta$ and when the input tree $G$ satisfies at least one of the following conditions: (a) $G$ is a star, or (b) $G$ has constant maximum degree. Second, we prove that TTR is fixed-parameter tractable (FPT) with respect to the number of leaves in the input tree $G$, via a novel combination of techniques for totally unimodular matrices and mixed integer linear programming.
BibTeX
@inproceedings{mertzios2025realizing,
  author = {George B. Mertzios and Hendrik Molter and Paul G. Spirakis},
  title = {{Realizing temporal transportation trees}},
  booktitle = {WG},
  year = {2025},
  doi = {10.1007/978-3-032-11835-6\_28},
}
Figure