Abstract
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 \(\textsc {d}\in \{{\textsc {st}},{\textsc {mt}},{\textsc {ld}}\}\), we provide necessary and sufficient conditions for the existence of spanning \(\textsc {d}\)-tobs; when those do not exist, we characterize the maximum vertex set that a \(\textsc {d}\)-tob can span. Moreover, we provide a log linear algorithm for computing such \(\textsc {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 \(\textsc {d}\)-tobs. Finally, we show that the same results hold for optimal temporal in-branchings.
Daniela Bubboloni is partially supported by GNSAGA of INdAM (Italy). Daniela Bubboloni, Costanza Catalano and Andrea Marino are partially supported by Italian PNRR CN4 Centro Nazionale per la Mobilità Sostenibile, NextGeneration EU - CUP, B13C22001000001. Ana Silva is partially supported by: FUNCAP MLC-0191-00056.01.00/22 and PNE-0112-00061.01.00/16, CNPq 303803/2020-7 (Brazil).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
They do not necessarily satisfy the triangle inequality.
- 2.
Notice that [2] deals with waiting-time constrains. Nonetheless, to the best of our knowledge, their algorithms provide the best running time for distances such as mt and ft also when there are no time-constrains or restrictions on the elapsed times.
- 3.
- 4.
The literature often focused on nonstrict/strict variations to provide stronger negative results. In this paper, we have used the more general model to provide stronger positive results, while using the nonstrict/strict when providing negative ones.
References
Himmel, A.-S., Bentert, M., Nichterlein, A., Niedermeier, R.: Efficient computation of optimal temporal walks under waiting-time constraints. In: Cherifi, H., Gaito, S., Mendes, J.F., Moro, E., Rocha, L.M. (eds.) COMPLEX NETWORKS 2019. SCI, vol. 882, pp. 494–506. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-36683-4_40
Brunelli, F., Viennot, L.: Minimum-cost temporal walks under waiting-time constraints in linear time. arXiv:2211.12136 (2023)
Calamai, M., Crescenzi, P., Marino, A.: On computing the diameter of (weighted) link streams. ACM J. Exp. Algorithmics 27, 4.3:1–4.3:28 (2022)
Campos, V., Lopes, R., Marino, A., Silva, A.: Edge-disjoint branchings in temporal graphs. Electronic J. Combinatorics 28 (2020). https://doi.org/10.1007/978-3-030-48966-3_9
Casteigts, A.: Finding structure in dynamic networks. arXiv:1807.07801 (2018)
Cook, S.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151–158 (1971)
Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. McGraw-Hill, MIT Press, third ed. edn. (2001)
Deligkas, A., Potapov, I.: Optimizing reachability sets in temporal graphs by delaying. Inf. Comput. 285, 104890 (2022)
Dibbelt, J., Pajor, T., Strasser, B., Wagner, D.: Connection scan algorithm. ACM J. Exp. Algorithmics 23 (2018)
Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012)
Huang, S., Fu, A.W.C., Liu, R.: Minimum spanning trees in temporal graphs. In: ACM SIGMOD International Conference on Management of Data, pp. 419–430 (2015)
Kamiyama, N., Kawase, Y.: On packing arborescences in temporal networks. Inf. Process. Lett. 115(2), 321–325 (2015)
Kuwata, Y., Blackmore, L., Wolf, M., Fathpour, N., Newman, C., Elfes, A.: Decomposition algorithm for global reachability analysis on a time-varying graph with an application to planetary exploration. In: Intelligent Robot and System, pp. 3955–3960 (2009)
Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. 8(1), 611–6129 (2018)
Levin, L.: Universal sequential search problems. Problemy peredachi informatsii 9(3), 115–116 (1973)
Marino, A., Silva, A.: Eulerian walks in temporal graphs. Algorithmica 85, 805–830 (2023)
Nicosia, V., Tang, J., Musolesi, M., Russo, G., Mascolo, C., Latora, V.: Components in time-varying graphs. Chaos: Interdisc. J. Nonlinear Sci. 22(2) (2012)
Ranshous, S., Shen, S., Koutra, D., Harenberg, S., Faloutsos, C., Samatova, N.: Anomaly detection in dynamic networks: a survey. WIREs Comput. Stat. 7(3), 223–247 (2015)
Tang, J.K., Mascolo, C., Musolesi, M., Latora, V.: Exploiting temporal complex network metrics in mobile malware containment. In: 2011 IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks, pp. 1–9 (2010)
Wu, H., Cheng, J., Huang, S., Ke, Y., Lu, Y., Xu, Y.: Path problems in temporal graphs. Proc. VLDB Endow. 7(9), 721–732 (2014)
Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., Wu, H.: Efficient algorithms for temporal path computation. Knowl. Data Eng. 28(11), 2927–2942 (2016)
Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding small separators in temporal graphs. J. Comp. Syst. Sci. 107, 72–92 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bubboloni, D., Catalano, C., Marino, A., Silva, A. (2023). On Computing Optimal Temporal Branchings. In: Fernau, H., Jansen, K. (eds) Fundamentals of Computation Theory. FCT 2023. Lecture Notes in Computer Science, vol 14292. Springer, Cham. https://doi.org/10.1007/978-3-031-43587-4_8
Download citation
DOI: https://doi.org/10.1007/978-3-031-43587-4_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-43586-7
Online ISBN: 978-3-031-43587-4
eBook Packages: Computer ScienceComputer Science (R0)