Temporal graph realization with bounded stretch ☆

Mertzios, George B.

Temporal graph realization with bounded stretch ☆

2026-05-01

0

PRE

AI

DOI：

Original request for help

Save

Abstract

En 中文

A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first A time steps, and then it reappears recurrently every A time step, where A is a given period length. 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 distances in the underlying static graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and A such that, in the resulting periodic temporal graph with period A, the duration of the fastest temporal path from any vertex u to any other vertex v is at most alpha times the distance between u and vin 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 algorithm which guarantees an approximation strictly smaller than A. 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 kedges. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

Keywords:

Temporal graph

Periodic temporal labeling

Fastest temporal path

Graph realization

Temporal connectivity

Stretch

Temporal graph realization with bounded stretch ☆

Abstract

Journal

Organization

Cited Papers