2026/04/30 by Michelle Döring, Niklas Mohrin, George Skretas
Computer Science · #cs.DS
paper · pdf · doi:10.48550/arxiv.2604.27757
arxiv created 2026/08/04 · arxiv updated 2026/08/05
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.