×

How fast can we reach a target vertex in stochastic temporal graphs? (English) Zbl 1456.68124

A temporal graph (or evolving graph) is a sequence of spanning subgraphs \((G_t : t \in {\mathbb N})\) of an underlying graph \(G\). One subgraph in the sequence is a snapshot. A stochastic temporal graph is a stochastic process on snapshots, forming a temporal graph on \(G\). This paper considers processes in which the probability that each edge \(e\in E\) appears at time step \(t\) depends on its status in the previous \(k\) steps. Edges behave independently of one another over time, each with its own probability distribution. A detailed examination of the complexity of two temporal path problems, Minimum Arrival and Best Policy, is presented for this stochastic temporal graph model.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
68W25 Approximation algorithms

Software:

cliques
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Aaron, E.; Krizanc, D.; Meyerson, E., DMVP: foremost waypoint coverage of time-varying graphs, (Proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (2014)), 29-41 · Zbl 1417.68048
[2] Akrida, E.; Mertzios, G.; Spirakis, P.; Zamaraev, V., Temporal vertex cover with a sliding time window, (Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (2018)), 148:1-148:14 · Zbl 1499.68243
[3] Akrida, E. C.; Gasieniec, L.; Mertzios, G. B.; Spirakis, P. G., Ephemeral networks with random availability of links: the case of fast networks, J. Parallel Distrib. Comput., 87, 109-120 (2016)
[4] 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) · Zbl 1379.68250
[5] Anagnostopoulos, A.; Lacki, J.; Lattanzi, S.; Leonardi, S.; Mahdian, M., Community detection on evolving graphs, (Proceedings of the 30th Conference on Neural Information Processing Systems (NIPS) (2016)), 3522-3530
[6] Avin, C.; Koucký, M.; Lotker, Z., How to explore a fast-changing world (cover time of a simple random walk on evolving graphs), (International Colloquium on Automata, Languages and Programming, ICALP (2008)), 121-132 · Zbl 1152.68476
[7] Basu, P.; Bar-Noy, A.; Ramanathan, R.; Johnson, M. P., Modeling and analysis of time-varying graphs (2010), CoRR
[8] Basu, P.; Guha, S.; Swami, A.; Towsley, D., Percolation phenomena in networks under random dynamics, (Proceedings of the 4th International Conference on Communication Systems and Networks (COMSNETS) (2012)), 1-10
[9] Basu, P.; Yu, F.; Bar-Noy, A.; Rawitz, D., To sample or to smash? Estimating reachability in large time-varying graphs, (Proceedings of the SIAM International Conference on Data Mining (2014)), 983-991
[10] Basu, P.; Yu, F.; Johnson, M. P.; Bar-Noy, A., Low expected latency routing in dynamic networks, (Proceedings of the 11th IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS) (2014)), 267-271
[11] 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) · Zbl 1075.68545
[12] Casteigts, A.; Flocchini, P., Deterministic Algorithms in Dynamic Networks: Formal Models and Metrics (April 2013), Defence R&D Canada, Technical report
[13] Casteigts, A.; Flocchini, P., Deterministic Algorithms in Dynamic Networks: Problems, Analysis, and Algorithmic Tools (April 2013), Defence R&D Canada, Technical report
[14] Casteigts, A.; Flocchini, P.; Godard, E.; Santoro, N.; Yamashita, M., On the expressivity of time-varying graphs, Theor. Comput. Sci., 590, 27-37 (2015) · Zbl 1327.68174
[15] Clementi, A.; Macci, C.; Monti, A.; Pasquale, F.; Silvestri, R., Flooding time of edge-Markovian evolving graphs, SIAM J. Discrete Math., 24, 4, 1694-1712 (2010) · Zbl 1221.68170
[16] Clementi, A.; Monti, A.; Pasquale, F.; Silvestri, R., Information spreading in stationary Markovian evolving graphs, IEEE Trans. Parallel Distrib. Syst., 22, 9, 1425-1432 (2011)
[17] Durrett, R., Probability: Theory and Examples (2011), Cambridge University Press
[18] Enright, J.; Meeks, K.; Mertzios, G.; Zamaraev, V., Deleting edges to restrict the size of an epidemic in temporal networks, (Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS) (2019)), 57:1-57:15 · Zbl 07561701
[19] Erlebach, T.; Hoffmann, M.; Kammer, F., On temporal graph exploration, (Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP) (2015)), 444-455 · Zbl 1440.68186
[20] Ferreira, A., Building a reference combinatorial model for MANETs, IEEE Netw., 18, 5, 24-29 (2004)
[21] Flocchini, P.; Mans, B.; Santoro, N., On the exploration of time-varying networks, Theor. Comput. Sci., 469, 53-68 (2013) · Zbl 1258.68103
[22] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM, 34, 3, 596-615 (1987) · Zbl 1412.68048
[23] Henri, S.; Shneer, S.; Thiran, P., On the delays in time-varying networks: does larger service-rate variance imply larger delays?, (Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2018)), 201-210
[24] Himmel, A.; 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)
[25] (Holme, P.; Saramäki, J., Temporal Networks (2013), Springer)
[26] Janson, S., Tail bounds for sums of geometric and exponential variables, Stat. Probab. Lett., 135, 1-6 (2018) · Zbl 1392.60042
[27] Kempe, D.; Kleinberg, J. M.; Kumar, A., Connectivity and inference problems for temporal networks, (Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC) (2000)), 504-513 · Zbl 1296.68015
[28] Lamprou, I.; Martin, R.; Spirakis, P. G., Cover time in edge-uniform stochastically-evolving graphs, Algorithms, 11, 10, 149 (2018) · Zbl 1461.60027
[29] Mertzios, G.; Michail, O.; Chatzigiannakis, I.; Spirakis, P., Temporal network optimization subject to connectivity constraints, Algorithmica, 1416-1449 (2019) · Zbl 1421.68139
[30] Mertzios, G.; Molter, H.; Zamaraev, V., Sliding window temporal graph coloring, (Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI) (2019)), 7667-7674
[31] Michail, O.; Spirakis, P., Elements of the theory of dynamic networks, Commun. ACM, 61, 2, 72 (Jan. 2018)
[32] Nain, P.; Towsley, D.; Johnson, M. P.; Basu, P.; Bar-Noy, A.; Yu, F., Computing traversal times on dynamic Markovian paths (2013), Technical report, available at
[33] Norris, J., Markov Chains, Cambridge Series in Statistical and Probabilistic Mathematics (1998), Cambridge University Press · Zbl 0938.60058
[34] Ogier, R.; Rutenburg, V., Minimum-expected-delay alternate routing, (Proceedings of the Annual IEEE International Conference on Computer Communications (INFOCOM) (1992)), 617-625
[35] Orda, A.; Rom, R., Distributed shortest-path protocols for time-dependent networks, Distrib. Comput., 10, 1, 49-62 (1996) · Zbl 1448.68153
[36] Pittel, B., On spreading a rumor, SIAM J. Appl. Math., 47, 1, 213-223 (1987) · Zbl 0619.60068
[37] Provan, J.; Ball, M., The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput., 12, 4, 777-788 (1983) · Zbl 0524.68041
[38] Santoro, N., Computing in time-varying networks, (Proceedings of the 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (2011)), 4
[39] Scheideler, C., Models and techniques for communication in dynamic networks, (Proceedings of the 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS) (2002)), 27-49 · Zbl 1054.68011
[40] Vaidya, P., Speeding-up linear programming using fast matrix multiplication, (Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS) (1989)), 332-337
[41] Valdes, J.; Tarjan, R. E.; Lawler, E. L., The recognition of series parallel digraphs, SIAM J. Comput., 11, 2, 298-313 (1982) · Zbl 0478.68065
[42] Viard, T.; Latapy, M.; Magnien, C., Computing maximal cliques in link streams, Theor. Comput. Sci., 609, 245-252 (2016) · Zbl 1331.68158
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.