Abstract
In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploration problem in a temporal star is to find a temporal walk which starts at the center of the star, visits all leaves, and eventually returns back to the center. We present here a systematic study of the computational complexity of this problem, depending on the number k of time-labels that every edge is allowed to have; that is, on the number k of time points where each edge can be present in the graph. To do so, we distinguish between the decision version \(\textsc {StarExp}(k)\), asking whether a complete exploration of the instance exists, and the maximization version \(\textsc {MaxStarExp}(k)\) of the problem, asking for an exploration schedule of the greatest possible number of edges in the star. We fully characterize \(\textsc {MaxStarExp}(k)\) and show a dichotomy in terms of its complexity: on one hand, we show that for both \(k=2\) and \(k=3\), it can be efficiently solved in \(O(n\log n)\) time; on the other hand, we show that it is APX-complete, for every \(k\ge 4\) (does not admit a PTAS, unless P = NP, but admits a polynomial-time 1.582-approximation algorithm). We also partially characterize \(\textsc {StarExp}(k)\) in terms of complexity: we show that it can be efficiently solved in \(O(n\log n)\) time for \(k \in \{2,3\}\) (as a corollary of the solution to \(\textsc {MaxStarExp}(k)\), for \(k\in \{2,3\}\)), but is NP-complete, for every \(k\ge 6\).
Partially supported by the NeST initiative of the School of EEE and CS at the University of Liverpool and by the EPSRC Grants EP/P020372/1 and EP/P02002X/1.
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.
A preliminary version of this paper appeared publicly in ArXiv on 12\(^{th}\) May 2018 (https://arxiv.org/pdf/1805.04713.pdf).
- 2.
Note that an undirected edge \(e=\{u,v\}\) is associated with \(2\cdot |L(e)|\) time edges, namely both (u, v, l) and (v, u, l) for every \(l\in L(e)\).
- 3.
APX is the complexity class of optimization problems that allow constant-factor approximation algorithms.
- 4.
We consider here the order \(c_1,c_2,\ldots , c_q\) of the clauses of C; we say that \(x_i\) appears unnegated for the first time in some clause \(c_\mu \) if \(x_i \not \in c_m,~m<\mu \).
References
Aaron, E., Krizanc, D., Meyerson, E.: DMVP: foremost waypoint coverage of time-varying graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 29–41 (2014)
Akrida, E.C., Gasieniec, L., Mertzios, G.B., Spirakis, P.G.: The complexity of optimal design of temporally connected graphs. Theory Comput. Syst. 61(3), 907–944 (2017)
Akrida, E.C., Mertzios, G., Spirakis, P.G., Zamaraev, V.: Temporal vertex covers and sliding time windows. In: International Colloquium on Automata, Languages and Programming (ICALP) (2018)
Ausiello, G., Protasi, M., Marchetti-Spaccamela, A., Gambosi, G., Crescenzi, P., Kann, V.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999). https://doi.org/10.1007/978-3-642-58412-1
Biswas, S., Ganguly, A., Shah, R.: Restricted shortest path in temporal graphs. In: Chen, Q., Hameurlain, A., Toumani, F., Wagner, R., Decker, H. (eds.) DEXA 2015. LNCS, vol. 9261, pp. 13–27. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22849-5_2
Bodlaender, H.L., van der Zanden, T.C.: On exploring temporal graphs of small pathwidth. CoRR, abs/1807.11869 (2018)
Casteigts, A., Flocchini, P.: Deterministic algorithms in dynamic networks: formal models and metrics. Technical report, Defence R&D Canada, April 2013
Chan, T.-H.H., Ning, L.: Fast convergence for consensus in dynamic networks. ACM Trans. Algorithms 10, 15-1 (2014)
Chuzhoy, J., Ostrovsky, R., Rabani, Y.: Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res. 31, 730–738 (2006)
Clementi, A.E.F., Macci, C., Monti, A., Pasquale, F., Silvestri, R.: Flooding time of edge-Markovian evolving graphs. SIAM J. Discrete Math. (SIDMA) 24(4), 1694–1712 (2010)
Demetrescu, C., Italiano, G.F.: Algorithmic techniques for maintaining shortest routes in dynamic networks. Electron. Notes Theor. Comput. Sci. 171, 3–15 (2007)
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
Himmel, A.-S., Molter, H., Niedermeier, R., Sorge, M.: Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs. Soc. Netw. Anal. Min. 7(1), 35:1–35:16 (2017)
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
Kempe, D., Kleinberg, J.M., Kumar, A.: Connectivity and inference problems for temporal networks. In: ACM Symposium on Theory of Computing (STOC), pp. 504–513 (2000)
Kleinberg, J., Tardos, E.: Algorithm Design. Addison-Wesley Longman, Boston (2005)
Mertzios, G.B., Michail, O., Chatzigiannakis, I., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7966, pp. 657–668. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39212-2_57
Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theor. Comput. Sci. 634, 1–23 (2016)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Upper Saddle River (1982)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)
Spieksma, F.C.R.: On the approximability of an interval scheduling problem. J. Sched. 2, 215–227 (1999)
Viard, T., Latapy, M., Magnien, C.: Computing maximal cliques in link streams. Theor. Comput. Sci. 609, 245–252 (2016)
Wagner, D., Willhalm, T., Zaroliagis, C.D.: Dynamic shortest paths containers. Electron. Notes Theor. Comput. Sci. 92, 65–84 (2004)
Zhuang, H., Sun, Y., Tang, J., Zhang, J., Sun, X.: Influence maximization in dynamic social networks. In: International Conference on Data Mining (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Akrida, E.C., Mertzios, G.B., Spirakis, P.G. (2019). The Temporal Explorer Who Returns to the Base. In: Heggernes, P. (eds) Algorithms and Complexity. CIAC 2019. Lecture Notes in Computer Science(), vol 11485. Springer, Cham. https://doi.org/10.1007/978-3-030-17402-6_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-17402-6_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-17401-9
Online ISBN: 978-3-030-17402-6
eBook Packages: Computer ScienceComputer Science (R0)