# A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs

Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti, Laurent Viennot

► To cite this version:

Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti, Laurent Viennot. A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs. 2023. [hal-04054527](https://hal-04054527)

HAL Id: hal-04054527

https://inria.hal.science/hal-04054527

Preprint submitted on 31 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs

Alkida Balliu¹, Filippo Brunelli*², Pierluigi Crescenzi¹, Dennis Olivetti¹, and Laurent Viennot*²

¹GSSI, I-67100 L’Aquila, Italy

²Inria, Irif, Université de Paris, F-75013 Paris, France

March 31, 2023

## Abstract

A temporal graph is a graph in which edges are assigned a time label. Two nodes *u* and *v* of a temporal graph are connected one to the other if there exists a path from *u* to *v* with increasing edge time labels. We consider the problem of assigning time labels to the edges of a digraph in order to maximize the total reachability of the resulting temporal graph (that is, the number of pairs of nodes which are connected one to the other). In particular, we prove that this problem is NP-hard. We then conjecture that the problem is approximable within a constant approximation ratio. This conjecture is a consequence of the following graph theoretic conjecture: any strongly connected directed graph with *n* nodes admits an out-arborescence and an in-arborescence that are edge-disjoint, have the same root, and each spans $\Omega(n)$ nodes.

*Keywords:* temporal graph; temporal path; time assignment; temporal reachability.

## 1 Introduction

Temporal graphs have received increasing attention over the last two decades [11, 12, 15, 19] and have been defined in several different ways [1, 10, 13, 2, 6, 5, 14] (see [3] for a classification of temporal graphs). Here, we say that a temporal graph $G = (V, E)$ is a list $E$ of temporal edges $(u, v, t)$, where $u, v \in V$ are two nodes of the graph (called, respectively, *tail* and *head* of the temporal edge) and

<footnote>*This work was partly supported by the French National Research Agency (ANR) through the projects Multimod (ANR-17-CE22-0016) and Temporal (ANR-22-CE48-0001).</footnote>
<figure><img src="image_1.png" /><figcaption>Figure 1: A digraph *D* (left), and an edge temporalisation of *D* (right). The temporal reachability of the resulting temporal graph is 16, since each node is temporally reachable from any other node.</figcaption></figure>

$t$ is the *appearing time* of the temporal edge. For each temporal edge $(u, v, t)$, we can traverse the edge starting from $u$ at time $t$ and arrive in $v$ at time $t+1$, which is the *arrival time* of the temporal edge.

We study a network optimisation problem related to the notion of reachability in temporal graphs. Given a temporal graph $G$, a (temporal) *path* from a node $u$ to a node $v$ is a sequence $e_1, e_2, \dots, e_k$ of temporal edges such that the tail of $e_1$ is $u$, the head of $e_k$ is $v$, and, for any $i$ with $1 < i \le k$, the tail of $e_i$ is equal to the head of $e_{i-1}$ and the appearing time of $e_i$ is greater than the appearing time of $e_{i-1}$. The *temporal reachability* of $G$ is the number of pairs of nodes $u$ and $v$ such that $v$ is *temporally reachable* from $u$, that is, there exists a temporal path from $u$ to $v$. The **MAXIMUM REACHABILITY EDGE TEMPORALISATION (MRET)** problem consists of, given a directed graph (in short, digraph) $D = (V, E)$, find an *edge temporalisation* $\tau: E \to N$ such that the temporal reachability of the resulting temporal graph is maximized. For example, let us consider the digraph shown in the left part of Figure 1. In the right part of the figure, we show an edge temporalisation of a digraph $D$ with four nodes, such that the temporal reachability of the resulting temporal graph is equal to 16, which is clearly the maximum possible temporal reachability.

The MRET problem restricted to undirected graphs has been studied in [9], where it is shown that the problem of deciding whether the resulting temporal graph is temporally connected (that is, for any two nodes $u$ and $v$, $v$ is temporally reachable from $u$) is NP-complete (clearly, this implies that the MRET problem restricted to undirected graphs is NP-hard). It is also easy to see that the MRET problem restricted to undirected connected graphs can be approximated within a constant approximation ratio, since this simply requires to look for a “centroid” in a spanning tree as a temporalisation where half of the nodes can reach the other half can then easily be computed. Note, however, that temporalising a symmetric digraph is not equivalent to temporalising an undirected graph as different times can be assigned to an edge $(u, v)$ and the symmetric edge $(v, u)$.

In the following, we prove that the MRET problem is NP-hard, even when restricted to strongly connected digraphs. We will conclude by conjecturing
<figure><img src="image_2.png" /><figcaption>Figure 2: An example of the reduction of 3-SAT to MRET. The 3-SAT formula is $(x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor \neg x_2 \lor \neg x_3)$.</figcaption></figure>

**Block gadget V** contains the nodes $u_1, u_2, u_3$, and $u_4$, and the nodes $b_i$, for $i \in [M]$ (the value of $M$ will be specified later in the proof). **E** contains the edges $\{(b_i, u_1) : i \in [M]\}$, $(u_1, u_2)$, $\{(u_2, d_j^l) : j \in [m], l \in [K]\}$, $\{(e_j^l, u_3) : j \in [m], l \in [K]\}$, $(u_3, u_4)$, and $\{(u_4, b_i) : i \in [M]\}$.

Note that **D** is strongly connected. Indeed, let us consider the cycles

$$C_{i,j,l,p} = \langle u_1, u_2, d_j^l, c_j^1, t_i^1, f_i^2, f_i^1, t_i^2, c_j^2, e_j^l, u_3, u_4, b_p, u_1 \rangle,$$

where $j \in [m]$, $i$ is such that $x_i$ is a literal of the clause $c_j$, $l \in [K]$, and $p \in [M]$, and the cycles

$$C_{i,j,l,p} = \langle u_1, u_2, d_j^l, c_j^1, f_i^1, t_i^2, t_i^1, f_i^2, c_j^2, e_j^l, u_3, u_4, b_p, u_1 \rangle,$$
where $j \in [m]$, $i$ is such that $\neg x_i$ is a literal of the clause $c_j$, $l \in [K]$, and $p \in [M]$. The union of these cycles contains each node in $V$, and each of these cycles contains node $u_1$. This proves the strong connectivity of $D$.

In the following, $B$ denotes the set $\{b_i : i \in [M]\}$ and $H$ denotes the set of nodes which do not belong to the block gadget, that is, $H = V \setminus (\{u_1, u_2, u_3, u_4\} \cup B)$ (note that $|V| = M + |H| + 4$ and that $|H| = 2(K + 1)m + 4n$).

**Activation of pairs of nodes in a variable gadget.** Consider a variable $x_i$ and the associated variable gadget and a schedule $S$ of the 4 edges associated to the variable gadget. We say that $S$ activates the pair $(t_i^1, t_i^2)$ (respectively, $(f_i^1, f_i^2)$) if $t_i^2$ (respectively, $f_i^2$) is $S$-reachable from $t_i^1$ (respectively, $f_i^1$) within the gadget, that is $(t_i^1, f_i^2)$, $(f_i^2, f_i^1)$, and $(f_i^1, t_i^2)$ (respectively, $(f_i^1, t_i^2)$, $(t_i^2, t_i^1)$), $(t_i^1, f_i^2)$) are scheduled in that order. Note that no schedule can activate both $(t_i^1, t_i^2)$ and $(f_i^1, f_i^2)$ as the edge $(t_i^1, f_i^2)$ is scheduled either before or after the edge $(f_i^1, t_i^2)$.

**Constructing a schedule from a satisfying assignment.** Suppose that there is an assignment $\alpha$ that satisfies $\Phi$, and let us consider the following schedule $S$. First we schedule the edges in $\{(b_i, u_1) : i \in [M]\}$ (in any arbitrary order), then the edge $(u_1, u_2)$, and then the edges in $\{(u_2, d_j^i) : j \in [m], i \in [K]\}$ (in any arbitrary order). Then we schedule the edges $\{(d_j^i, c_j^1) : j \in [m], i \in [K]\}$ (in any arbitrary order), and, then, the edges going out from the nodes $c_j^1$, for $j \in [m]$ (in any arbitrary order). Then, for each $i \in [n]$, if $\alpha(x_i) = \text{TRUE}$, we schedule the edges $(t_i^1, f_i^2)$, $(f_i^2, f_i^1)$, $(f_i^1, t_i^2)$, and $(t_i^2, t_i^1)$ in this order (thus activating $(t_i^1, t_i^2)$). Otherwise (that is, $\alpha(x_i) = \text{FALSE}$), we schedule the edges $(f_i^1, t_i^2)$, $(t_i^2, t_i^1)$, $(t_i^1, f_i^2)$, and $(f_i^2, f_i^1)$ in this order (thus activating $(f_i^1, f_i^2)$). Then we schedule all the edges entering the nodes $c_j^2$, for $j \in [m]$ (in any arbitrary order), and then all the edges going out from the nodes $c_j^2$, for $j \in [m]$ (in any arbitrary order). Finally, we schedule the edges in $\{(e_j^l, u_3) : j \in [m], l \in [K]\}$ (in any arbitrary order), then the edge $(u_3, u_4)$, and all the edges in $\{(u_4, b_i) : i \in [M]\}$ (in any arbitrary order). Let $G$ be the temporal graph induced by $D$ and the schedule $S$.

First observe that, for any clause $c_j$ with $j \in [m]$, there exists a literal that satisfies $c_j$ according to the assignment $\alpha$. Let $x_i$ (respectively, $\neg x_i$) be a literal satisfying $c_j$. Since $(t_i^1, t_i^2)$ (respectively, $(f_i^1, f_i^2)$) is activated, there exists a temporal path from $c_j^1$ to $c_j^2$ that goes through variable gadget corresponding to $x_i$. This means that $c_j^2 \in \mathcal{R}_G(c_j^1)$ and that, for $l, l' \in [K]$, $e_j^{l'} \in \mathcal{R}_G(d_j^l)$. We now prove a lower bound $\mathbb{L}$ on the $S$-reachability by showing a lower bound on the number of nodes temporally reachable from each possible source.

* For any $v \in V$ and for $i \in [M]$, $v \in \mathcal{R}_G(b_i)$. This adds $M(M + |H| + 4)$ to $\mathbb{L}$.

* For $i \in [4]$ and for $j \in [M]$, $b_j \in \mathcal{R}_G(u_i)$. Moreover, $\{u_1, u_2, u_3, u_4\} \cup H \subseteq \mathcal{R}_G(u_1)$, $\{u_2, u_3, u_4\} \cup H \subseteq \mathcal{R}_G(u_2)$, $u_3, u_4 \in \mathcal{R}_G(u_3)$, and $u_4 \in \mathcal{R}_G(u_4)$. This adds $4M + 2|H| + 10$ to $\mathbb{L}$.
* For $j, h \in [m]$, $i, l \in [K]$, and $p \in [M]$, $c_h^2, e_h^l \in \mathcal{R}_G(d_j^i)$ (because of the above observation) and $b_p \in \mathcal{R}_G(d_j^i)$. This adds $Km(M+Km+m)$ to $\mathbb{L}$.

* For $j, h \in [m]$, $l \in [K]$, and $i \in [M]$, $c_h^2, e_h^l, b_i \in \mathcal{R}_G(c_j^1)$. This adds $m(M+Km+m)$ to $\mathbb{L}$.

* For $i \in [n]$, there exists $j \in [m]$ such that $c_j$ is satisfied by $\alpha(x_i)$. Hence, for $p \in [2]$, $l \in [K]$, and $h \in [M]$, $e_j^l, b_h \in \mathcal{R}_G(t_i^p)$ and $e_j^l, b_h \in \mathcal{R}_G(f_i^p)$. This adds $4n(M+K)$ to $\mathbb{L}$.

* For $j \in [m]$, $l \in [K]$, and $h \in [M]$, $e_j^l, b_h \in \mathcal{R}_G(c_j^2)$. This adds $m(M+K)$ to $\mathbb{L}$.

* For $j \in [m]$, $l \in [K]$, and $h \in [M]$, $b_h \in \mathcal{R}_G(e_j^l)$. This adds $MKm$ to $\mathbb{L}$.

Thus, the S-reachability is at least

$$ \mathbb{L} = M(M + |H| + 4) + (4M + 2|H| + 10) + Km(M + Km + m) + m(M + Km + m) + 4n(M + K) + m(M + K) + MKm. $$

**Bounding reachability when $\Phi$ is not satisfiable.** Let us set $M$ equal to any value greater than $(|H| + 5)^2$. We now prove that, if there exists no truth-assignment satisfying the formula $\Phi$, then no schedule $S$ can have S-reachability greater than or equal to $\mathbb{L}$. First notice that if $S$ assigns to the edge $(u_3, u_4)$ a starting time smaller than the starting time assigned to $(u_1, u_2)$, then the S-reachability is less than $\mathbb{L}$. This is because, in this case, for $i, j \in [M]$ with $i \neq j$, $b_j$ is not S-reachable from $b_i$. Hence, the S-reachability is bounded by $\mathbb{U}_1 = M(|H|+4+1)+(|H|+4)(M+|H|+4)$: this would happen if, for each node $v \notin B$, $\mathcal{R}_G(v) = V$. Since $\mathbb{L} > M^2$, $\mathbb{U}_1 = M(|H|+4+1)+(|H|+4)(M+|H|+4) = 2M(|H|+4) + (|H|+4)^2 + M < M(|H|+5)^2$, and $M > (|H|+5)^2$, it holds that $\mathbb{L} > \mathbb{U}_1$. We can then focus on schedules that assign to the edge $(u_1, u_2)$ a starting time smaller than the starting time assigned to the edge $(u_3, u_4)$. Let $S$ be such a schedule and let $G$ be the temporal graph induced by $D$ and $S$. We now prove an upper bound $\mathbb{U}_2$ on the S-reachability by giving an upper bound on the nodes reachable from each possible source. Observe that, for any two nodes $u$ and $v$, $v$ might belong to $\mathcal{R}_G(u)$ only if in $D$ there exists a path from $u$ to $v$ that does not include the edge $(u_3, u_4)$ before the edge $(u_1, u_2)$.

* For $i \in [M]$, $|\mathcal{R}_G(b_i)| \le |V|$. This adds $M(M + |H| + 4)$ to $\mathbb{U}_2$.

* For $i \in [2]$, $|\mathcal{R}_G(u_i)| \le |V|$, while $|\mathcal{R}_G(u_3)| \le M+3$ and $|\mathcal{R}_G(u_4)| \le |V| = M + |H| + 4$.

* For $j \in [m]$ and $i \in [K]$, in the best case $\mathcal{R}_G(d_j^i)$ contains $d_j^i$, $c_j^1$, the 12 nodes corresponding to the three variables appearing in $c_j$, and the nodes in $\{c_h^2 : h \in [m]\} \cup \{e_h^l : h \in [m], l \in [K]\} \cup \{u_1, u_3, u_4\} \cup B$, yielding $|\mathcal{R}_G(d_j^i)| \le M + Km + m + 17$. However, we can show that there exists an index $j^*$ such that, for $l, l' \in [K]$, $e_{j^*}^{l'} \notin \mathcal{R}_G(d_{j^*}^l)$, implying that the
d-nodes add at most $Km(M + Km + m + 17) - K^2$ to $U_2$. For defining $j^*$, we consider the following truth-assignment $\alpha$: for any variable $x_i$ with $i \in [n]$, $\alpha(x_i) = \text{TRUE}$ if $(t_i^1, f_i^2)$ is scheduled before $(f_i^1, t_i^2)$, otherwise $\alpha(x_i) = \text{FALSE}$. Note that if $\alpha(x_i) = \text{TRUE}$ (respectively, $\alpha(x_i) = \text{FALSE}$) we know that $S$ does not activate $(f_i^1, f_i^2)$ (respectively, $(t_i^1, t_i^2)$). Since the formula $\Phi$ is not satisfiable there exists $j^* \in [m]$ such that $c_{j^*}$ is not satisfied by $\alpha$. Let $x_i$ (respectively, $\neg x_i$) be a literal in $c_{j^*}$. Since $c_{j^*}$ is not satisfied by $\alpha$, we that $\alpha(x_i) = \text{FALSE}$ (respectively, $\alpha(x_i) = \text{TRUE}$) and that $(t_i^1, t_i^2)$ (respectively, $(f_i^1, f_i^2)$) is not activated. It is thus impossible to reach $c_{j^*}^2$ from $c_{j^*}^1$ through the variable gadget of $x_i$. On the other hand, in all the other walks in $D$ that connect $c_{j^*}^1$ to $c_{j^*}^2$ the edge $(u_3, u_4)$ appears before the edge $(u_1, u_2)$. Hence, $c_{j^*}^2 \notin \mathcal{R}_G(c_{j^*}^1)$ and $e_{j^*}^{l'} \notin \mathcal{R}_G(d_{j^*}^l)$ for $l, l' \in [K]$.

* For $j \in [m]$, in the best case $\mathcal{R}_G(c_j^1)$ contains $c_j^1$, the 12 nodes corresponding to the three variables appearing in clause $c_j$, and the nodes in $\{c_h^2 : h \in [m]\} \cup \{e_h^l : h \in [m], l \in [K]\} \cup \{u_1, u_3, u_4\} \cup B$. This adds $m(M + Km + m + 16)$ to $U_2$.

* For $i \in [n]$ and for $j \in [2]$, in the best case $\mathcal{R}_G(t_i^j)$ and $\mathcal{R}_G(f_i^j)$ contain the corresponding four variable nodes and the nodes in $\{c_h^2 : h \in [m]\} \cup \{e_h^l : h \in [m], l \in [K]\} \cup \{u_1, u_3, u_4\} \cup B$. This adds $4n(M + Km + m + 7)$ to $U_2$.

* For $j \in [m]$, in the best case $\mathcal{R}_G(c_j^2)$ contains $c_j^2$ and the nodes in $\{e_j^l : l \in [K]\} \cup \{u_1, u_3, u_4\} \cup B$. This adds $m(M + K + 4)$ to $U_2$.

* For $j \in [m]$ and $i \in [K]$, in the best case $\mathcal{R}_G(e_j^i)$ contains $e_j^i$ and the nodes in $\{u_1, u_3, u_4\} \cup B$. This adds with $Km(M + 4)$ to $U_2$.

In summary,

$$ U_2 = M(M + |H| + 4) + (4M + 3|H| + 15) + (Km(M + Km + m + 17) - K^2) \\ +m(M + Km + m + 16) + 4n(M + Km + m + 7) + m(M + K + 4) \\ +Km(M + 4). $$

We have that $\mathbb{L} - U_2 = -|H| - 5K^2 - 21Km - 4n(K(m-1) + m + 7) - 20m = K^2 - 23Km - 4n(K(m-1) + m + 8) - 22m - 5 > K^2 - Knm(23 + 4(1 + 1 + 8) + 22 + 5) = K^2 - 90Knm$ using $K, n, m \ge 1$. Let us set $K$ equal to any value greater than or equal to $91nm$. We then have $K^2 > 90Knm$ and, thus, $\mathbb{L} > U_2$. That is, the $S$-reachability has to be smaller than $\mathbb{L}$.

**Conclusion.** We have thus proved that the formula $\Phi$ is satisfiable if and only if there exists a schedule $S$ such that the $S$-reachability of $D$ is at least $\mathbb{L}$. This completes the proof of the theorem. □
# 3 Conclusion and open problems

In this paper, we have considered MRET problem, that is, the problem of assigning appearing times to the edges of a digraph in order to maximize the total reachability of the resulting temporal graph. We have proved that this problem is NP-hard, even when the digraph is strongly connected. We conjecture that the MRET problem can be approximated within a constant approximation ratio. In particular, we conjecture that any strongly connected digraph admits an edge temporalisation with temporal reachability at least equal to $c \cdot n^2$ for some constant $c > 0$. One way to prove such a statement would be to prove the following interesting graph theory conjecture.

**Almost Spanning Two Rooted-Arborescences conjecture (ASTRA).** Any strongly connected digraph admits an out-arborescence and an in-arborescence that are edge-disjoint, have the same root, and each spans $\Omega(n)$ nodes.

Note that it is not difficult to prove that the root of the two arborescences mentioned in the ASTRA conjecture cannot be any node in the graph. For example, let us consider the graph shown in Figure 3. In this case, the node $x_1$ cannot be the common root of the two arborescences, since the only in-arborescence and the only out-arborescence with root $x_1$ share the edge $(x_2, y_2)$, so that one of the two arborescences cannot include more than one node (of course, this example can be generalized to any even number of nodes).

Note also that the ASTRA conjecture is false if we require that the two arborescences span at least $\frac{n}{3-\epsilon}$ nodes, for any positive constant $\epsilon$. For example, consider the digraph $G = (V, E)$ shown in Figure 4, where, for some integer parameter $k > 0$, the set of nodes is $V = \{x, y, x_1, y_1, x_2, y_2, x_3, y_3\} \cup \{z_{i,j} \mid 1 \le i \le 3, 1 \le j \le k\}$, and the set of edges is $E = \{(x, y)\} \cup \{(y, x_i), (x_i, y_i), (y_i, x), (y_i, z_{i,1}), (z_{i,k}, x_i) \mid 1 \le i \le 3\} \cup \{(z_{i,j}, z_{i,j+1}) \mid 1 \le i \le 3, 1 \le j < k\}$. Observe that the total number of nodes is $n = 3k + 8$. Let us first give an upper bound on the minimum between the amount of nodes in the in-arborescence and in the out-arborescence in the case where the root is not $x$ nor $y$. For any such node, either the in-arborescence or the out-arborescence can contain at most $k + 3$ nodes, since the edge $(x, y)$ can be in one arbores-

<figure><img src="image_3.png" /><figcaption>Figure 3: An example of a digraph for which only some nodes can be roots of two arborescences each spanning $\Omega(n)$ nodes.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 4: An example of a digraph for which there are no two edge-disjoint arborescences with a common root and each spanning more than $n/3 + c$ nodes, for some positive constant $c$.</figcaption></figure>

cence only. Consider now the case in which either $x$ or $y$ is the root. Let us suppose that the root is $x$ (the other case can be analysed in a similar way). Since, for each $i = 1, 2, 3$, the edge $(x_i, y_i)$ can be in one arborescence only, then either the in-arborescence or the out-arborescence rooted at $x$ can contain at most $n - 2k = k + 8$ nodes. We thus obtained that, in all cases, either the in-arborescence or the out-arborescence is upper bounded by $k+8 = n/3+O(1)$.

## References

[1] Kenneth A. Berman. Vulnerability of scheduled networks and a generalization of menger's theorem. Networks, 28(3):125-134, 1996.

[2] S. Bhadra and A. Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In *ADHOC-NOW*, pages 259-270, 2003.
[3] F. Brunelli, P. Crescenzi, and L. Viennot. On computing pareto optimal paths in weighted time-dependent networks. *Information Processing Letters*, 168:106086, 2021.

[4] Filippo Brunelli, Pierluigi Crescenzi, and Laurent Viennot. Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks. *Networks*, pages 1–27, 2002.

[5] A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. *IJPEDS*, 27(5):387–408, 2012.

[6] Eddie Cheng, Jerrold W Grossman, and Marc J Lipman. Time-stamped graphs and their associated influence digraphs. *Discrete Applied Mathematics*, 128(2):317–335, 2003.

[7] F. Corò, G. D'Angelo, and Y. Velaj. Recommending links to maximize the influence in social networks. In *IJCAI*, pages 2195–2201, 2019.

[8] J.A. Enright, K. Meeks, G.B. Mertzios, and V. Zamaraev. Deleting edges to restrict the size of an epidemic in temporal networks. In *MFCS*, pages 57:1–57:15, 2019.

[9] F. Göbel, J. Orestes Cerdeira, and H.J. Veldman. Label-connected graphs and the gossip problem. *Discrete Mathematics*, 87(1):29–40, 1991.

[10] F. Harary and G. Gupta. Dynamic graph models. *Mathematical and Computer Modelling*, 25(7):79–87, 1997.

[11] P. Holme and J. Saramäki. Temporal networks. *Physics Reports*, 519(3):97–125, 2012.

[12] Petter Holme and Jari Saramäki. *Temporal Networks*. Springer, Berlin, Heidelberg, 2013.

[13] D. Kempe, J. Kleinberg, and A. Kumar. Connectivity and inference problems for temporal networks. *Journal of Computer and System Sciences*, 64(4):820–842, 2002.

[14] M. Latapy, T. Viard, and C. Magnien. Stream graphs and link streams for the modeling of interactions over time. *Social Netw. Analys. Mining*, 8(1):61:1–61:29, 2018.

[15] Naoki Masuda and Renaud Lambiotte. *A Guide to Temporal Networks*. World Scientific, Singapore, 2016.

[16] G.B. Mertzios, O. Michail, I. Chatzigiannakis, and P.G. Spirakis. Temporal network optimization subject to connectivity constraints. In *ICALP*, pages 657–668, 2013.
[17] G.B. Mertzios, O. Michail, and P.G. Spirakis. Temporal network optimization subject to connectivity constraints. *Algorithmica*, 81(4):1416–1449, 2019.

[18] George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The complexity of transitively orienting temporal graphs. In *MFCS*, volume 202 of *LIPIcs*, pages 75:1–75:18, 2021.

[19] O. Michail. An introduction to temporal graphs: An algorithmic perspective. *Internet Mathematics*, 12(4):239–280, 2016.

[20] Hendrik Molter, Malte Renken, and Philipp Zschoche. Temporal reachability minimization: Delaying vs. deleting. In *MFCS*, volume 202 of *LIPIcs*, pages 76:1–76:15, 2021.