2026-09-21T06:45:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25513 2026-09-05T19:18:41Z ddc:004 open_access

Foremost, Fastest, Shortest: Temporal Graph Realization Under Various Path Metrics Cauvi, Justine Morawietz, Nils Viennot, Laurent network design temporal paths foremost paths fastest paths shortest paths non-strict paths periodic temporal graphs In this work, we follow the current trend on temporal graph realization, where one is given a property P and the goal is to determine whether there is a temporal graph, that is, a graph where the edge set changes over time, with property P. We consider the problems where the given property P is a prescribed matrix for the duration, length, or earliest arrival time of pairwise temporal paths. This means that we are given a matrix D and ask whether there is a temporal graph such that for any ordered pair of vertices (s,t), D_{s,t} equals the duration (length, or earliest arrival time, respectively) of any temporal path from s to t minimizing that specific temporal path metric. For shortest and earliest arrival temporal paths, we are the first to consider these problems as far as we know. We analyze these problems for many settings such as: strict and non-strict paths, periodic and non-periodic temporal graphs, and limited number of labels per edge (limited number of occurrences per edge over time). In contrast to all other path metrics, we show that for the earliest arrival times, we can achieve polynomial-time algorithms in periodic and non-periodic temporal graphs and for strict and and non-strict paths. However, the problem becomes NP-hard when the matrix does not contain a single integer but a set or range of possible allowed values. As we show, the problem can still be solved efficiently in this scenario, when the number of entries with more than one value is small, that is, we develop an FPT-algorithm for the number of such entries. For the setting of fastest paths, we achieve new hardness results that answers an open question by Klobas, Mertzios, Molter, and Spirakis [Theor. Comput. Sci. '25] about the parameterized complexity of the problem with respect to the vertex cover number and significantly improves over a previous hardness result for the feedback vertex set number. When considering shortest paths, we show that the periodic versions are polynomial-time solvable whereas the non-periodic versions become NP-hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Justine Cauvi and Nils Morawietz and Laurent Viennot 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.24 urn:nbn:de:0030-drops-255139 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.24 eng https://creativecommons.org/licenses/by/4.0/legalcode