Abstract
A temporal graph \(\mathcal {G} = \langle G_1, ..., G_L\rangle \) is a sequence of graphs \(G_i \subseteq G\), for some given underlying graph G of order n. We consider the non-strict variant of the Temporal Exploration problem, in which we are asked to decide if \(\mathcal {G}\) admits a sequence W of consecutively crossed edges \(e \in G\), such that W visits all vertices at least once and that each \(e \in W\) is crossed at a timestep \(t' \in [L]\) such that \(t' \ge t\), where t is the timestep during which the previous edge was crossed. This variant of the problem is shown to be \(\textsf {NP}\)-complete. We also consider the hardness of approximating the exploration time for yes-instances in which our order-n input graph satisfies certain assumptions that ensure exploration schedules always exist. The first is that each pair of vertices are contained in the same component at least once in every period of n steps, whilst the second is that the temporal diameter of our input graph is bounded by a constant c. For the latter of these two assumptions we show \(O(n^{\frac{1}{2}-\varepsilon })\)-inapproximability and \(O(n^{1-\varepsilon })\)-inapproximability in the \(c=2\) and \(c \ge 3\) cases, respectively. For graphs with temporal diameter \(c=2\), we also prove an \(O(\sqrt{n} \log n)\) upper bound on worst-case time required for exploration, as well as an \(\varOmega (\sqrt{n})\) lower bound.
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
References
Akrida, E.C., Mertzios, G.B., Spirakis, P.G.: The temporal explorer who returns to the base. In: Heggernes, P. (ed.) CIAC 2019. LNCS, vol. 11485, pp. 13–24. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17402-6_2
Bodlaender, H.L., van der Zanden, T.C.: On exploring always-connected temporal graphs of small pathwidth. Inf. Process. Lett. 142, 68–71 (2019). https://doi.org/10.1016/j.ipl.2018.10.016
Brodén, B., Hammar, M., Nilsson, B.J.: Online and offline algorithms for the time-dependent TSP with time zones. Algorithmica 39(4), 299–319 (2004). https://doi.org/10.1007/s00453-004-1088-z
Bui-Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(2), 267–285 (2003). https://doi.org/10.1142/S0129054103001728
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. IJPEDS 27(5), 387–408 (2012)
Casteigts, A., Himmel, A.S., Molter, H., Zschoche, P.: The computational complexity of finding temporal paths under waiting time constraints. CoRR abs/1909.06437 (2019). https://arxiv.org/abs/1909.06437
Di Luna, G.A., Dobrev, S., Flocchini, P., Santoro, N.: Live exploration of dynamic rings. In: 36th IEEE International Conference on Distributed Computing Systems (ICDCS 2016), pp. 570–579. IEEE (2016). https://doi.org/10.1109/ICDCS.2016.59
Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 444–455. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47672-7_36
Erlebach, T., Kammer, F., Luo, K., Sajenko, A., Spooner, J.T.: Two moves per time step make a difference. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). LIPIcs, vol. 132, pp. 141:1–141:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.ICALP.2019.141
Erlebach, T., Spooner, J.T.: Faster exploration of degree-bounded temporal graphs. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). LIPIcs, vol. 117, pp. 36:1–36:13. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2018). https://doi.org/10.4230/LIPIcs.MFCS.2018.36
Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theor. Comput. Sci. 469, 53–68 (2013). https://doi.org/10.1016/j.tcs.2012.10.029
Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: Temporal graph classes: a view through temporal separators. Theor. Comput. Sci. 806, 197–218 (2020). https://doi.org/10.1016/j.tcs.2019.03.031
Gotoh, T., Flocchini, P., Masuzawa, T., Santoro, N.: Tight bounds on distributed exploration of temporal graphs. In: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). LIPIcs, vol. 153, pp. 22:1–22:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.OPODIS.2019.22
Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of constantly connected dynamic graphs based on cactuses. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 250–262. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09620-9_20
Ilcinkas, D., Wade, A.M.: Exploration of the T-interval-connected dynamic graphs: the case of the ring. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 13–23. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03578-9_2
Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002). https://doi.org/10.1006/jcss.2002.1829
Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12(4), 239–280 (2016). https://doi.org/10.1080/15427951.2016.1177801
Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Causality, influence, and computation in possibly disconnected synchronous dynamic networks. J. Parallel Distrib. Comput. 74(1), 2016–2026 (2014). https://doi.org/10.1016/j.jpdc.2013.07.007
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1–23 (2016). https://doi.org/10.1016/j.tcs.2016.04.006
Sobin, C.C., Raychoudhury, V., Marfia, G., Singla, A.: A survey of routing and data dissemination in delay tolerant networks. J. Netw. Comput. Appl. 67, 128–146 (2016). https://doi.org/10.1016/j.jnca.2016.01.002
Tovey, C.A.: A simplified NP-complete satisfiability problem. Discr. Appl. Math. 8(1), 85–89 (1984). https://doi.org/10.1016/0166-218X(84)90081-7
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Erlebach, T., Spooner, J.T. (2020). Non-strict Temporal Exploration. In: Richa, A., Scheideler, C. (eds) Structural Information and Communication Complexity. SIROCCO 2020. Lecture Notes in Computer Science(), vol 12156. Springer, Cham. https://doi.org/10.1007/978-3-030-54921-3_8
Download citation
DOI: https://doi.org/10.1007/978-3-030-54921-3_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-54920-6
Online ISBN: 978-3-030-54921-3
eBook Packages: Computer ScienceComputer Science (R0)