Approximating Optimal Labelings for Temporal Connectivity

Daniele Carnevale, Gianlorenzo D’Angelo, Martin Olsen · 2025

Read Approximating Optimal Labelings for Temporal Connectivity by Daniele Carnevale, Gianlorenzo D’Angelo, Martin Olsen (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-16837.txt.

Introduction

Daniele Carnevale, Gianlorenzo D'Angelo, and Martin Olsen study a scheduling problem for networks that change over time in a 2025 paper. Each link in such a network is open only at set times, and a valid path must use links in rising time order. The task is to choose open times so all pairs stay linked within a time limit, using as few labels as possible.

The authors show the problem is hard to approximate beyond set bounds, unless major open questions in computing break the other way. They then give methods whose quality nearly matches those bounds under set conditions. The results also carry over to a classic problem on static networks.

Catalog record

CREATORDaniele Carnevale, Gianlorenzo D’Angelo, Martin Olsen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE92 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Approximating Optimal Labelings for Temporal Connectivity Daniele Carnevale, Gianlorenzo D’Angelo, Martin Olsen Abstract 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 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 ) O(\log n) when a ≥ 2 a\geq 2 , unless P = NP \text{P}=\text{NP} , and a factor better than 2 log 1 − ϵ ⁡ n 2^{\log^{1-\epsilon}n} when a ≥ 3 a\geq 3 , unless NP ⊆ DTIME ​ ( 2 polylog ​ ( n ) ) \text{NP}\subseteq\text{DTIME}(2^{\text{polylog}(n)}) , where n 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 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 . 1 Introduction We consider a scheduling problem on dynamic networks that is motivated by several applications in logistics, distribution scheduling, and information diffusion in social networks. As a real-world example, consider a parcel-delivery scenario where there is a warehouse W serving three cities as the center of a star topology, see Figure 1 for an illustration. Each city has a bunch of parcels to be delivered to the other cities and, for each pair of cities (A,B) , there is at least one parcel that must be delivered from A to B . There is a set of vehicles in W that are used to deliver the parcels from the warehouse to the cities and vice-versa. Each vehicle can possibly depart from W at every hour. Upon arrival at one of the cities A , it delivers at A the parcels destined to A that were previously deposited at W , collects the parcels originating from A , and returns to the warehouse. A round trip of a vehicle from W to one of the cities and back is called a trip . For simplicity, we assume that the travel time is negligible. When a vehicle V_{1} returns from city A to the warehouse W , it deposits in W all the parcels that depart from A and whose final destination is any of the other cities. When a vehicle V_{2} departs to another city B , it brings to B all the parcels that have been deposited in W so far and whose final destination is B . If the trip of V_{1} is scheduled earlier than that of V_{2} , the parcels directed from A to B are delivered. Otherwise, these parcels must wait for the next trip. Carefully scheduling the trips of all vehicles might reduce, at the same time, the delivery time and the costs in terms of number of required trips, vehicles used, fuel consumption, pollutants, and emission of greenhouse gases. For example, the 1 st schedule in Figure 1 , requires 6 trips to deliver all parcels and the last parcels are delivered at 9am. The 2 nd schedule optimizes the latest arrival time and ensures that the last parcels are delivered two hours earlier than the previous solution, at 7am, but still requires 6 trips to deliver all parcels. The 3 rd schedule, instead, optimizes the required number of trips, reducing them to 5, but the last parcels are delivered at 8am, one hour later than the previous case. W A B C 7am;9am 7am;8am 6am;8am 1 st schedule W A B C 6am;7am 6am;7am 6am;7am 2 nd schedule W A B C 6am;8am 7am 6am;8am 3 rd schedule Figure 1: The scheduled time of trips are reported close to the edges. 1 st schedule : All the 6 scheduled trips are needed to deliver all parcels and the last parcel is delivered at 9am. 2 nd schedule : All the parcels are deposited in W with the 3 trips at 6am and then are delivered from W to the right cities at 7am; still 6 trips are needed but the last parcel is delivered at 7am. 3 rd schedule : The parcels leaving cities A and C are deposited in W with the trips at 6am; the single trip to B at 7am brings the parcels directed to B previously deposited at 6am and deposits the parcels from B in W ; finally, the trips at 8am deliver the parcels directed to A and C . Only 5 trips are needed, but the last parcel is delivered at 8am. The problem of scheduling trips becomes much more complex if we consider a general network in which each vertex might serve both as a warehouse and as a city, and connections among vertices are given by an arbitrary underlying graph. Moreover, similar problems arise in other contexts such as distribution scheduling [ 11 ] and information spreading, where the aim is to schedule a small number of meetings among employees of a company in such a way that each employee can share its own information with any other by a given time, see [ 10 ] . Motivated by these applications, we consider the following question: What is the minimum number of trips needed to deliver all parcels within a given time? We model a schedule of trips along edges of a network with a temporal graph (a.k.a. dynamic graph) in which the scheduling time of a vehicle is represented as an edge-label and a path in a graph is valid (or temporal ) only if the edges are traversed in increasing order of their labels. We then consider the optimization problem of assigning the minimum number of labels to the edges of a graph in such a way that each pair of vertices is connected via a temporal path and the largest label is not greater than a given integer a , called the maximum allowed age . This problem, called Minimum Aged Labeling ( MAL ), has been introduced by Mertzios et al. [ 21 ] , who proved that it is APX -hard in directed graphs . Later, Klobas et al. [ 18 ] showed

Read the complete text