Temporal Routing in Static Networks: The Schedule Completion Problem

Abstract

We introduce the Temporally Edge Disjoint Schedule Completion (TEDSC) problem in which we need to cover a set of temporal edge demands $D$ by routing $k$ temporal walks through a directed static graph while remaining temporally edge disjoint. This problem combines the temporal aspects of train routing and passenger demands with the static nature of real-world rail networks. We show how to solve TEDSC in polynomial time. Motivated by real-world constraints, we next investigate two restricted variants of TEDSC in which each walk can travel only for some bounded distance or time $h$. For both variants, we present a $(2-h^{-1})$-approximation algorithm and fully characterize the parameterized landscape with respect to $k$, $h$, and $|D|$. Surprisingly, if we restrict the underlying train network, the two variants diverge: The distance variant stays $W[1]$-hard parameterized by $k$ even on a path of three vertices, whereas the time variant admits a polynomial-time algorithm on every fixed bidirected star graph.