  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.
