Approximating Optimal Labelings for Temporal Connectivity

Daniele Carnevale, Gianlorenzo D'Angelo, Martin OlsenAAAI 2025 · DOI

Introduction to Temporal Connectivity and the MAL Problem

In modern network science, the assumption of static connectivity is often insufficient. Many real-world systems—ranging from satellite constellations and logistics networks to social interactions—are better modeled as temporal graphs, where edges are only available at specific time intervals, denoted by labels. For two nodes to be "temporally connected," there must exist a path where the time labels on the edges are strictly increasing, reflecting the physical reality that a subsequent leg of a journey cannot begin before the previous one has concluded.

This paper investigates the Minimum Aged Labeling (MAL) problem. Given an undirected graph and a maximum allowed time (deadline) $a$, the goal is to assign labels to edges such that every pair of vertices is temporally connected by time $a$, while minimizing the total number of labels used across the entire graph. This problem has significant practical implications for optimizing resource allocation in infrastructure, reducing fuel costs in logistics, and ensuring efficient information dissemination in dynamic networks.

Figure 2: Comparison of three different labeling schedules for a simple star-like graph. Different schedules provide varying trade-offs between the number of labels used and the speed of connectivity.

Complexity and Hardness of Approximation

Prior research established that MAL is NP-complete. This work extends those findings by determining the fundamental limits of how well we can approximate the optimal solution. The authors demonstrate that the problem is remarkably resistant to efficient approximation, particularly for tight deadlines.

Through sophisticated hardness reductions from the Set Cover and MIN-REP problems, the authors prove that for a deadline $a \ge 2$, it is NP-hard to approximate MAL within a factor of $O(\log n)$. When the deadline is slightly more relaxed ($a \ge 3$), the problem becomes even more difficult, with a hardness factor of $2^{\log^{1-\epsilon} n}$, suggesting that polynomial-time algorithms are unlikely to achieve close-to-optimal results for these cases.

Figure 5: A complex graph construction used in the hardness reduction proofs, illustrating the mapping of static set-covering instances into the temporal domain.

The Deadline-Diameter Gap

A key contribution of this paper is identifying the "Deadline-Diameter Gap." The authors show that the difficulty of MAL depends entirely on the relationship between the deadline $a$ and the graph's physical diameter $D_G$ (the longest shortest path in the static version of the graph).

If the deadline $a$ is less than $D_G$, no solution exists. However, as $a$ increases relative to $D_G$, the problem becomes more tractable. The authors establish a formal link between MAL and the Diameter Constrained Spanning Subgraph (DCSS) problem, which seeks a minimum-edge subgraph that maintains a specific diameter. This connection allows for the porting of hardness results and algorithmic techniques from static graph theory into the temporal domain.

Algorithmic Framework and Key Results

To address the MAL problem, the authors introduce a suite of sublinear approximation algorithms that utilize a technique involving "dominating set-pairs." This approach identifies a small set of "hub" nodes that can reach (or be reached by) all other nodes within a certain distance, then carefully schedules temporal paths through these hubs to minimize the total label count.

Their primary algorithmic results are categorized by the generosity of the deadline:

  • Moderate Deadlines: If $a \ge \lceil 1.5 \cdot D_G \rceil$, they provide an algorithm with an approximation ratio of $O(\sqrt{n \log n})$.
  • Generous Deadlines: If $a \ge \lceil 1.67 \cdot D_G \rceil$, the approximation ratio improves to $O(\sqrt[3]{D_G n \log^2 n})$.
  • Very Large Deadlines: When the deadline is sufficiently large ($a \ge 2D_G + 2$), the problem can be solved optimally in polynomial time.

Conclusion and Future Directions

This paper provides a comprehensive map of the complexity landscape for the Minimum Aged Labeling problem. By bridging temporal connectivity with static diameter-constrained problems, the authors offer both strong theoretical bounds and practical approximation strategies.

Future work remains to be done in the "intermediate" deadline range where the current approximation ratios are less tight. Additionally, the authors suggest that exploring MAL directly—without reducing it to the static DCSS problem—might yield even more efficient algorithms that do not depend linearly on the graph's diameter.

Summary updated

BibTeX
@inproceedings{carnevale2025approximating,
  author = {Daniele Carnevale and Gianlorenzo D'Angelo and Martin Olsen},
  title = {{Approximating Optimal Labelings for Temporal Connectivity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34849},
}
Figure