# Approximating Optimal Labelings for Temporal Connectivity

arXiv: https://arxiv.org/abs/2504.16837 · HTML: https://mlsanity.com/paper/2504.16837/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 28 references that are in the map.
- First posted on arXiv 23 Apr 2025.

## Builds on (most cited first, 8 of 8)

- [An Introduction to Temporal Graphs: An Algorithmic Perspective](https://mlsanity.com/paper/1503.00278/) (2015)
- [The complexity of computing optimum labelings for temporal connectivity](https://mlsanity.com/paper/2202.05880/) (2022)
- [Optimizing Reachability Sets in Temporal Graphs by Delaying](https://mlsanity.com/paper/2004.05875/) (2020)
- [Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds](https://mlsanity.com/paper/1607.06068/) (2016)
- [Assigning times to minimise reachability in temporal graphs](https://mlsanity.com/paper/1802.05905/) (2018)
- [Deleting edges to restrict the size of an epidemic in temporal networks](https://mlsanity.com/paper/1805.06836/) (2018)
- [Temporal Reachability Minimization: Delaying vs. Deleting](https://mlsanity.com/paper/2102.10814/) (2021)
- [Minimizing Reachability Times on Temporal Graphs via Shifting Labels](https://mlsanity.com/paper/2112.08797/) (2021)

## Abstract (arXiv)

In a temporal graph the edge set dynamically changes over time according to a set of time-labels associated with each edge that indicates at which time-steps the edge is available. Two vertices are connected if there is a path connecting them in which the edges are traversed in increasing order of their labels. We study the problem of scheduling the availability time of the edges of a temporal graph in such a way that all pairs of vertices are connected within a given maximum allowed time a and the overall number of labels is minimized. The problem, known as Minimum Aged Labeling (MAL), has several applications in logistics, distribution scheduling, and information spreading in social networks, where carefully choosing the time-labels can significantly reduce infrastructure costs, fuel consumption, or greenhouse gases. The problem MAL has previously been proved to be NP-complete on undirected graphs and APX-hard on directed graphs. In this paper, we extend our knowledge on the complexity and approximability of MAL in several directions. We first show that the problem cannot be approximated within a factor better than O(log n) when a≥ 2, unless P = NP, and a factor better than 2^log 1-ε n when a≥ 3, unless NPsubseteq DTIME(2polylog(n)), where n is the number of vertices in the graph. Then we give a set of approximation algorithms that, under some conditions, almost match these lower bounds. In particular, we show that the approximation depends on a relation between a and the diameter of the input graph. We further establish a connection with a foundational optimization problem on static graphs called Diameter Constrained Spanning Subgraph (DCSS) and show that our hardness results also apply to DCSS.