2026-09-08T01:21:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26255 2026-09-05T19:39:45Z ddc:004 open_access

Brief Announcement: Revisiting the Realizability of Periodic Temporal Graphs with Bounded Stretch Meusel, Julia Morawietz, Nils Müller-Hannemann, Matthias Reinhardt, Klaus fastest temporal path periodic temporal graphs graph realization In this work, we revisit Stretched Periodic Temporal Graph Realization (STGR) which was recently introduced by Mertzios et al. [MFCS 2025]. Here, the input consists of an undirected graph G = (V,E), a period Δ, and a rational number α ≥ 1, and the question is, whether there is a labeling λ: E → [0,Δ-1], such that the stretch is at most α in the Δ-periodic temporal graph (G,λ), that is, the temporal graph, where for each c ∈ ℕ and each edge e, e appears at time c⋅ Δ + i if and only if λ(e) = i. The stretch of (G,λ) is the maximum stretch between any vertex pair (u,v) in (G,λ), where the stretch of a vertex pair (u,v) is defined as the duration of a fastest temporal path from u to v in (G,λ) divided by the distance between these vertices in the underlying graph. We complete the complexity picture for STGR with respect to Δ by investigating the open case of Δ = 2. It turns out that STGR is NP-hard for each Δ > 1. Moreover, we also answer the open question by Mertzios et al. on whether there are graphs for which the smallest possible stretch is larger than (Δ+1)/2. We show not only that such graphs exist, but also that it remains NP-hard to decide whether the optimal stretch is at most (Δ+1)/2. Our hardness results for Δ = 2 also imply hardness for Δ = 2 for the Fastest Periodic Temporal Graph Realization problem that was introduced by Klobas et al. [TCS 2025]. Finally, we show the existence of classes of graphs with small and large stretch. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julia Meusel and Nils Morawietz and Matthias Müller-Hannemann and Klaus Reinhardt 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.21 urn:nbn:de:0030-drops-262556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.21 eng https://creativecommons.org/licenses/by/4.0/legalcode