  In this work we extend the concept of out/in-branchings spanning the vertices
of a digraph (also called directed spanning trees) to temporal graphs, which
are digraphs where arcs are available only at prescribed times. While the
literature has focused on minimum weight/earliest arrival time Temporal
Out-Branchings (TOB), we solve the problem for other optimization criteria. In
particular, we define five different types of TOBs based on the optimization of
the travel duration (FT-TOB), of the departure time (LD-TOB), of the number of
transfers (MT-TOB), of the total waiting time (MW-TOB), and of the travelling
time (ST-TOB). For D$\in \{$LD,MT,ST$\}$, we provide necessary and sufficient
conditions for the existence of a spanning D-TOB; when it does not exist, we
characterize the maximum vertex set that a D-TOB can span. Moreover, we provide
a log linear algorithm for computing such branchings. For D$\in \{$FT,MW$\}$,
we prove that deciding the existence of a spanning D-TOB is NP-complete; we
also show that the same results hold for optimal temporal in-branchings.
Finally, we investigate the related problem of computing a spanning temporal
subgraph with the minimum number of arcs and optimizing a chosen criterion D.
This problem turns out to be NP-hard for any D. The hardness results are quite
surprising, as computing optimal paths between nodes can always be done in
polynomial time.

Data Structures and Algorithms;Discrete Mathematics