Temporal Network Optimization: Algorithms, Complexity and Approximation

In a temporal graph, each edge is assigned a set of discrete time labels indicating the time steps at which it is present, and paths must traverse edges in chronological order. A vertex u can temporally reach a vertex v if there is a temporal path from u to v; if this holds for every pair of vertices, the temporal graph is said to be temporally connected. Temporal graphs model dynamic networks, enabling the analysis of dynamic processes in real-world systems such as social networks, transportation, and communication infrastructures. This thesis focuses on temporal network optimization problems, where the goal is to modify a temporal graph through an operation to optimize a given criterion while satisfying specific properties. We study three distinct but complementary problems. First, we study the Minimum Aged Labeling (MAL) problem, which consists of assigning time labels to the edges of a graph so that every vertex can temporally reach every other vertex within a given global deadline a, while minimizing the total number of labels used. We establish strong inapproximability results when a is equal to the diameter of the input graph. Moreover, we give a set of approximation algorithms that, under some conditions, nearly match these lower bounds. In particular, we show that the approximation guarantees depend on a relation between a and the graph’s diameter. We also show a connection between MAL and the Diameter Constrained Spanning Subgraph (DCSS) problem on static graphs. Second, we introduce the D-Temporal Multi-Broadcast (D-TMB) family of optimization problems, which asks for an assignment of time labels to edges so that a given subset of vertices, called sources, can reach all other vertices while optimizing the worst-case temporal distance D. We show that D-TMB is polynomial-time solvable for certain temporal distance measures (earliest arrival and latest departure) when the source set is a singleton, while it is NP-complete for the other considered measures (fastest time, shortest traversal, minimum-hop, and minimum waiting). Moreover, when the source set contains two vertices, we establish that the problem is NP-hard under any temporal distance measure. We complement this result by identifying restrictions that enable tractability for earliest arrival and latest departure, regardless of the source set size. Third, we revisit the problem of finding a minimum-size spanning subgraph that preserves temporal connectivity, known as temporal spanner, in temporal cliques. While it is known that temporal cliques admit a spanner of size O(n log n), it remains open whether they admit a linear-size spanner. We focus on the structural property of dismountability, which was previously used in combination with other techniques to obtain this result. We then analyze the conditions under which a clique is non-dismountable for increasing hop distances. In particular, we characterize the properties a temporal clique must possess to be 1-, 2-, or 3-hop non-dismountable, and we show that no additional structure can be obtained beyond the three-hop case. Together with the strategy of Angrick et al., this allows us to recover the O(n log n) result for cliques using only dismountability. Furthermore, we show a connection between dismountability and another structural property called pivotability, and we introduce a new family of temporal graphs that possess both properties.