Temporal Graph Realization With Bounded Stretch

George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis · 2025

Read Temporal Graph Realization With Bounded Stretch by George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-14258.txt.

Introduction

Think of a bus network where every link runs on a repeating schedule. George Mertzios and three co-authors model such systems as periodic temporal graphs, where each connection appears once per period and the design task is to assign its time slot. They measure quality by stretch: how much longer the fastest timed route becomes, against the plain map distance.

The authors ask which stretch values can be guaranteed. They give approximation methods and hardness results, including a simple polynomial-time method whose guarantee always beats the trivial one and sometimes finds the optimum. They also study a repair version, where an existing schedule may be changed on at most a few links. The repair version proves hard in one sense, yet solvable with effort growing in the number of changes.

Catalog record

CREATORGeorge B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE130 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-14258

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Temporal Graph Realization With Bounded Stretch George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis Abstract A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ \Delta time steps, and then it reappears recurrently every Δ \Delta time steps, where Δ \Delta 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 G , the task is to assign to each edge one time-label between 1 and Δ \Delta such that, in the resulting periodic temporal graph with period Δ \Delta , the duration of the fastest temporal path from any vertex u u to any other vertex v v is at most α \alpha times the distance between u u and v v in G G . Here, the value of α \alpha 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 Δ \Delta , 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 k edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to k k . \crefname claimClaimClaims Department of Computer Science, Durham University, [email protected]://orcid.org/0000-0001-7182-585XSupported by the EPSRC grant EP/P020372/1. Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, [email protected]://orcid.org/0000-0002-4590-798XSupported by the Israel Science Foundation, grant nr. 1470/24, by the European Union’s Horizon Europe research and innovation programme under grant agreement 949707, and by the European Research Council, grant nr. 101039913 (PARAPATH). Institute of Computer Science, Friedrich Schiller University Jena, Germany LaBRI, Université de Bordeaux, [email protected]://orcid.org/0000-0002-7283-4982Supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL) Department of Computer Science, University of Liverpool, [email protected]://orcid.org/0000-0001-5396-3749Supported by the EPSRC grant EP/P02002X/1. ccs Theory of computation Graph algorithms analysis ccs Mathematics of computing Discrete mathematics keywords Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, stretch. † † runningauthor: George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis † † copyright: George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis 1 Introduction Graph realization is a classical problem where one is asked to decide whether a graph with a certain property, such as prescribed distances between vertex pairs or prescribed degrees for vertices, exists [ 6 , 19 , 27 , 28 ] . These types of problems have a natural analog in the temporal graph setting 1 1 1 A temporal graph is a graph where one or more time-labels are assigned to every edge, indicating at which times this edge is active. We give a formal definition in \cref sec:prelims. . Here we are given a static graph, and the task is to assign time-labels to each edge in order to create a temporal graph with some desired property. Temporal graph realization is an emerging topic in temporal graph algorithmics, and several connectivity-related properties have been considered. Previous work considered the property of temporal connectivity between every vertex pair or subsets thereof [ 3 , 31 , 37 ] , the size of so-called reachability sets [ 18 ] , exact reachability graphs [ 20 ] , fastest temporal paths 2 2 2 A temporal path uses edges with strictly increasing time-labels. A fastest temporal path is a temporal path that minimizes the difference between the arrival time and the starting time. We give a formal definition in \cref sec:prelims. of a prescribed (exact) duration between every vertex pair [ 22 , 32 ] , and fastest temporal paths with a prescribed upper bound on the duration for every vertex pair [ 38 , 39 ] . The latter two problems have been studied in the periodic setting , where every edge reappears after some given period length \Delta . We focus on the last among the mentioned problem settings, where we assume that the input consists of a graph and an upper bound for every (ordered) vertex pair that shall be respected by a fastest temporal path connecting the vertices. This problem is naturally motivated in the area of network design: we are given a transportation infrastructure and are tasked to develop a (periodic) schedule that guarantees fast delivery. In previous work [ 38 ] , we showed that this problem is NP-hard even if the input graph is a star and the period length \Delta is constant. This suggests that a lot of complexity is “hidden” in the prescribed upper bounds. However, it is, arguably, unnatural to have arbitrary upper bounds in the input that can be completely unrelated to the topology of the input graph. This leads us to the following problem. We investigate the setting where we wish that the durations of all fastest temporal paths to be by at most some factor \alpha times the distances of the respective vertex pairs in the (static) input graph. We then say that the realization has a bounded (multiplicative) stretch . This is a well-motivated and well-established concept in network design, especially in the context of spanning trees [ 1 , 2 , 7 , 15 , 16 ] or temporal spanners [ 5 ] . It allows the duration of connections between entities of the network to be related to the physical distance of those entities in a natural way. We formally define the problem as follows. All used terminology is formally defined in \cref sec:prelims. Stretched Temporal Graph Realization ( STGR ) Input: A graph G (static, undirected), \Delta\in\mathbb{N} , and a rational number \alpha\geq 1 . Question: Let D_{G} be the distance matrix of G . Can we assign one label in \{1,\ldots,\Delta\} to every edge such that in the resulting \Delta -periodic temporal graph, for every vertex pair u,v the duration of a fastest path from u to v is at most \alpha\cdot D_{G}(u,v) ? Our Contribution. STGR is a natural and well-motivated special case of the problem that we investigated in previous work [ 38 ] , where the upper bounds can be arbitrary. In this work, we show that STGR is NP-hard and hard to approximate, where we consider the goal of the optimization version of the problem to minimize the stretch \alpha . Formally, we prove the following in \cref sec:approxhardness. • For every 0<\varepsilon<1 and every c>1 , STGR is NP-hard to approximate within a factor of \Delta^{1-\varepsilon} or within a factor

Read the complete text