Temporal graphs, in which edges are annotated with time-labels indicating their availability at specific time steps, provide a flexible model for dynamic networks. Two nodes are said to be temporally connected if there exists a path between them such that the edges are traversed in strictly increasing order of their time-labels. We study the Minimum Aged Labeling (MAL) problem, which consists of assigning time-labels so that all node pairs are temporally connected within a global deadline , while minimizing the total number of labels used. MAL highlights the trade-of between ensuring temporal connectivity and minimizing the number of edge activations under strict resource constraints. It has significant implications for energy-aware scheduling in domains such as logistics, transportation, and communication, where reducing the number of active time slots can directly translate into lower energy use, reduced emissions, or infrastructure simplification. Our results establish strong inapproximability bounds for MAL: we prove that no algorithm can approximate the minimum number of labels within a factor better than (log ) for ≥ 2, unless P = NP, and not within 2log1− for ≥ 3, unless NP ⊆ DTIME(2polylog()). Subsequently, we develop approximation algorithms that, under certain assumptions, almost match these lower bounds. Notably, the approximation performance depends on the relationship between and the diameter of the input graph. Moreover, we establish a connection with the classical Diameter Constrained Spanning Subgraph (DCSS) optimization problem on static graphs and prove that our hardness results apply to DCSS.
We study a scheduling problem on dynamic networks, inspired by practical applications in logistics, distribution scheduling, and information difusion within social networks. Consider a real-world scenario of parcel delivery where a warehouse serves three cities arranged in a star topology. Each city has parcels destined for the other cities, and for each pair of cities (, ), there is at least one parcel that must be sent from to . A fleet of vehicles located at is responsible for transporting parcels between the warehouse and the cities. Each vehicle can depart from at any hour. Upon arrival at city , a vehicle delivers parcels destined for that were previously stored at , collects parcels originating from , and returns to the warehouse. A round trip from to a city and back is referred to as a trip. For simplicity, we assume travel times are negligible. When a vehicle 1 returns from city to the warehouse, it deposits all parcels originating from and destined for other cities. When another vehicle 2 departs towards city , it carries all parcels currently stored at with final destination . If the trip of 1 is scheduled before that of 2, parcels from to are successfully delivered; otherwise, these parcels must wait for the next trip. Performing a thorough scheduling of all vehicle trips can simultaneously reduce delivery times and operational costs such as the number of trips, vehicle usage, fuel consumption, and greenhouse gas emissions.
For example, the 1st schedule in Figure 1 requires 6 trips to deliver all parcels, with the last deliveries completed at 8 a.m. The 2nd schedule minimizes the latest delivery time, ensuring that all parcels are
;8am 6am 5am ;7am delivered by 6 a.m., two hours earlier than in the first schedule, while still requiring 6 trips. The 3 rd schedule, instead, minimizes the total number of trips, reducing them to 5, but delays the last delivery to 7 a.m., one hour later than in the second case.
The scheduling problem becomes significantly more complex when considering a general network in
which each vertex can act both as a warehouse and as a city, and where connections between vertices
are represented by an arbitrary graph. Moreover, similar challenges arise in other domains such as
distribution scheduling [
Motivated by these applications, we consider the following question: What is the minimum number of trips required to deliver all parcels within a given time frame?
We model a schedule of trips along the edges of a given network using a temporal graph, where
the scheduling time of a vehicle is represented as an edge label. A path in this graph is considered
valid (or temporal) only if its edges are traversed in strictly increasing order of their labels. We then
study the optimization problem of assigning the minimum number of labels to the edges of the given
network so that every pair of vertices is connected by a temporal path, and the largest label does not
exceed a given integer , referred to as the maximum allowed age. This problem, called Minimum Aged
Labeling (MAL), was introduced by Mertzios et al. [
Due to their versatility, temporal graphs have been studied from various perspectives and under diferent
names, such as dynamic, evolving, or time-varying graphs or networks (see [
This extended abstract outlines our main results on the MAL problem, covering both hardness of approximation and the design of eficient approximation algorithms. Further details can be found in the conference version of this work [12], while a full version is available on ArXiv [13]. We denote by the diameter of graph .
We begin by showing that, for any fixed maximum labeling age ≥ 2, the MAL problem cannot be approximated within a factor better than (log ), unless P = NP. Furthermore, under a diferent complexity assumption, we prove a stronger inapproximability bound: for any ∈ (0, 1), there exists no 2log1− -approximation algorithm for MAL, unless NP ⊆ DTIME(2polylog()), even when is fixed to a value at least 3.
These results advance our understanding of the computational complexity of MAL in two directions: from the exact computation perspective and from the approximation point of view.
(1) From the perspective of exact computation, the NP-hardness result in [
(2) From an approximation standpoint, the reduction in [
A summary of our hardness of approximation results is presented in Table 1.
As in [
( · 1/3), otherwise (√ · log ), for ∈ Ω(√︀/ log ) (︀ ( · · log2 )1/3)︀ , for ∈ Ω(log ) ∩ (√︀/ log ) ( · 1/3), otherwise highlight how the approximation guarantees for MAL depend on the relationship between and .
(1) We begin by analyzing the case where is suficiently larger than , the radius of the graph . Specifically, if ≥ 2 (resp., ≥ 2 + 1), we provide a polynomial-time algorithm that computes a solution requiring at most 2 (resp., 1) more labels than the optimum. These additive approximation guarantees translate into asymptotic multiplicative bounds, with approximation factors arbitrarily close to 1 as the input size increases. Furthermore, if ≥ 2 + 2, an optimal solution can be computed in polynomial time. Since MAL does not admit any feasible solution when < , this first set of results leaves open the intermediate regime where ≤ < 2.
(2) We next consider the case where is only slightly larger than , leveraging a connection between MAL and the DCSS problem. Specifically, we show that the approximability of MAL is within a factor of that of DCSS. We begin by showing that when = = 2, MAL admits a logarithmic-factor approximation, which asymptotically matches our first inapproximability bound. Note that if = 2 and = 1, the graph must be a clique. In this case, = 1 and = 2, so MAL can be solved using at most 2 labels more than the optimum. For ≥ + 2, we obtain an ( · 1/2)-approximation, which is sublinear in when is suficiently small. This bound improves as increases: we achieve approximation factors of ( · 2/5) and ( · 1/3) for ≥ + 4 and ≥ + 6, respectively. Finally, for any ≥ , we obtain an approximation factor of ( · 3/5+ ) for any constant > 0. All these approximation factors depend linearly on , as our approach approximates DCSS via generalizations of it, and then transforms the resulting solution into one for MAL.
(3) Our main algorithmic contribution addresses the case ≤ < 2, where we approximate MAL without relying on DCSS, thereby avoiding the linear dependence on in the approximation ratio. We show that when ≥ ⌈ 32 · ⌉ (resp., ≥ ⌈ 53 · ⌉), MAL can be approximated within a factor of (√ log ) (resp., (( log2 )1/3)). Both bounds are sublinear, and the second algorithm yields better performance when = (√︀/ log ), although it requires larger values of .
Table 2 summarizes the approximation guarantees we obtain for MAL.
In this work, we investigated the complexity of approximating the Minimum Aged Labeling problem (MAL). We established strong hardness of approximation results for the case = , summarized in Table 1. When relaxing the parameter to > , we provided approximation algorithms with guarantees that depend on the relationship between and , as detailed in Table 2. Additionally, we highlighted a connection between MAL and the Diameter Constrained Spanning Subgraph problem, showing that comparable hardness and approximation results hold for DCSS.
Several questions remain open. In particular, the computational complexity of MAL when < < 2 + 2 is still unresolved, as our reductions do not seem to extend to cases where ≥ + 1. Furthermore, it is unclear whether the inapproximability results for MAL hold when < < 2.
The authors utilized ChatGPT and Grammarly to enhance language clarity and readability. The authors, who take full responsibility for the final version of the manuscript, carefully reviewed and refined all content generated by these tools.
This work was partially supported by: the European Union - NextGenerationEU under the Italian Ministry of University and Research National Innovation Ecosystem grant ECS00000041 - VITALITY - CUP: D13C21000430001; PNRR MUR project GAMING “Graph Algorithms and MinINg for Green agents” (PE0000013, CUP D13C24000430001); the European Union - Next Generation EU under the Italian National Recovery and Resilience Plan (NRRP), Mission 4, Component 2, Investment 1.3, CUP J33C22002880001, partnership on “Telecommunications of the Future”(PE00000001 - program “RESTART”), project MoVeOver/SCHEDULE (“Smart interseCtions witH connEcteD and aUtonomous vehicLEs”, CUP J33C22002880001); ARS01_00540 - RASTA project, funded by the Italian Ministry of Research PNR 2015-2020. The first and second authors acknowledge the support of the MUR (Italy) Department of Excellence 2023–2027. [11] H. Molter, M. Renken, P. Zschoche, Temporal reachability minimization: Delaying vs. deleting, Journal of Computer and System Sciences 144 (2024) 103549. doi:10.1016/j.jcss.2024.103549. [12] D. Carnevale, G. D’Angelo, M. Olsen, Approximating optimal labelings for temporal connectivity, Proceedings of the AAAI Conference on Artificial Intelligence 39 (2025) 26490–26497. doi: 10. 1609/aaai.v39i25.34849. [13] D. Carnevale, G. D’Angelo, M. Olsen, Approximating optimal labelings for temporal connectivity, 2025. URL: https://arxiv.org/abs/2504.16837. arXiv:2504.16837.