2026-10-08T14:22:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24182 2025-11-12T12:34:13Z ddc:004 open_access

Temporal Graph Realization with Bounded Stretch Mertzios, George B. Molter, Hendrik Morawietz, Nils Spirakis, Paul G. Temporal graph periodic temporal labeling fastest temporal path graph realization temporal connectivity stretch A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time steps, where Δ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are "stretched", compared to their physical distances, i.e. their distances in the underlying static (non-temporal) graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be stretched once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple polynomial-time algorithm (the radius-algorithm) which always guarantees an approximation strictly smaller than Δ, and which also computes the optimum stretch in some cases. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most k edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to k. Schloss Dagstuhl – Leibniz-Zentrum für Informatik George B. Mertzios and Hendrik Molter and Nils Morawietz and Paul G. Spirakis 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.75 urn:nbn:de:0030-drops-241829 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.75 eng https://creativecommons.org/licenses/by/4.0/legalcode