A graph is temporally connected if a strict temporal path exists from every vertex u to every other vertex v. This paper studies temporal design problems for undirected temporally connected graphs. Given a connected undirected graph G, the goal is to determine the smallest total number of time-labels |λ| needed to ensure temporal connectivity, where |λ| denotes the sum, over all edges, of the size of the set of labels associated to an edge. The basic problem, called Minimum Labeling (ML) can be solved optimally in polynomial time. We introduce the Min. Aged Labeling (MAL) problem, which involves connecting the graph with an upper-bound on the maximum label, the Min. Steiner Labeling (MSL) problem, focusing on connecting specific important vertices, and the age-restricted version of MSL, Min. Aged Steiner Labeling (MASL). We show that MAL is NP-complete, MASL is W[1]- hard, and while MSL remains NP-hard, it is FPT with respect to the number of terminals.

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or Delta-TVC for time-windows of a fixed-length Delta) have been established as natural extensions of the classic Vertex Cover problem on static graphs with connections to areas such as surveillance in sensor networks. In this paper we initiate a systematic study of the complexity of TVC and Delta-TVC on sparse graphs. Our main result shows that for every Delta geq 2, Delta-TVC is NP-hard even when the underlying topology is described by a path or a cycle. This resolves an open problem from literature and shows a surprising contrast between Delta-TVC and TVC for which we provide a polynomial-time algorithm in the same setting. To circumvent this hardness, we present a number of exact and approximation algorithms for temporal graphs whose underlying topologies are given by a path, that have bounded vertex degree in every time step, or that admit a small-sized temporal vertex cover.

A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|λ|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,λ)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MIN. AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,λ)$. Second we consider the problem MIN. STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of "terminals" vertices which lie in a subset $R\subseteq V$. This relaxed problem resembles STEINER TREE in static graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MIN. AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL is NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder.

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never use the same vertex at the same time; otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. On the one extreme, we show that on general graphs the problem is computationally hard. The "walk version" is W[1]-hard when parameterized by the number of routes. However, it is polynomial-time solvable for any constant number of walks. The "path version" remains NP-hard even if we want to find only two temporally disjoint paths. On the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counterintuitively, we find NP-hardness in general but also identify natural tractable cases.