On Computing Optimal Temporal Branchings

The computation of out/in-branchings spanning the vertices of a digraph (also called directed spanning trees) is a central problem in theoretical computer science due to its application in reliable network design. This concept can be extended to temporal graphs, which are graphs where arcs are available only at prescribed times and paths make sense only if the availability of the arcs they traverse is non-decreasing. In this context, the paths of the out-branching from the root to the spanned vertices must be valid temporal paths. While the literature has focused only on minimum weight temporal out-branchings or the ones realizing the earliest arrival times to the vertices, the problem is still open for other optimization criteria. In this work we define four different types of optimal temporal out-branchings (TOB) based on the optimization of the travelling time (ST-TOB), of the travel duration (FT-TOB), of the number of transfers (MT-TOB) or of the departure time (LD-TOB). For D∈{ST,MT,LD} , we provide necessary and sufficient conditions for the existence of spanning D -TOBs; when those do not exist, we characterize the maximum vertex set that a D -TOB can span. Moreover, we provide a log linear algorithm for computing such D -TOBs. Oppositely, we show that deciding the existence of an FT-TOB spanning all the vertices is NP-complete. This is quite surprising, as all the above distances, including FT, can be computed in polynomial time, meaning that computing temporal distances is inherently different from computing D -TOBs. Finally, we show that the same results hold for optimal temporal in-branchings.