Skip to main content

Research Repository

Advanced Search

How fast can we reach a target vertex in stochastic temporal graphs?

Akrida, Eleni C.; Mertzios, George B.; Nikoletseas, Sotiris; Christoforos, Raptopoulos; Spirakis, Paul G.; Zamaraev, Viktor

How fast can we reach a target vertex in stochastic temporal graphs? Thumbnail


Authors

Sotiris Nikoletseas

Raptopoulos Christoforos

Paul G. Spirakis

Viktor Zamaraev



Contributors

Christel Baier
Editor

Ioannis Chatzigiannakis
Editor

Paola Flocchini
Editor

Stefano Leonardi
Editor

Abstract

Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature, in the sense that the network structure undergoes discrete changes over time. Given a static underlying graph G=(V,E), a temporal graph on G is a sequence of snapshots {G_t=(V,E_t) subseteq G: t in N}, one for each time step t >= 1. In this paper we study stochastic temporal graphs, i.e. stochastic processes G={G_t subseteq G: t in N} whose random variables are the snapshots of a temporal graph on G. A natural feature of stochastic temporal graphs which can be observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges; that is, the probability an edge e in E appears at time step t depends on its appearance (or absence) at the previous k steps. In this paper we study the hierarchy of models memory-k, k >= 0, which address this memory effect in an edge-centric network evolution: every edge of G has its own probability distribution for its appearance over time, independently of all other edges. Clearly, for every k >= 1, memory-(k-1) is a special case of memory-k. However, in this paper we make a clear distinction between the values k=0 ("no memory") and k >= 1 ("some memory"), as in some cases these models exhibit a fundamentally different computational behavior for these values of k, as our results indicate. For every k >= 0 we investigate the computational complexity of two naturally related, but fundamentally different, temporal path (or journey) problems: {Minimum Arrival} and {Best Policy}. In the first problem we are looking for the expected arrival time of a foremost journey between two designated vertices {s},{y}. In the second one we are looking for the expected arrival time of the best policy for actually choosing a particular {s}-{y} journey. We present a detailed investigation of the computational landscape of both problems for the different values of memory k. Among other results we prove that, surprisingly, {Minimum Arrival} is strictly harder than {Best Policy}; in fact, for k=0, {Minimum Arrival} is #P-hard while {Best Policy} is solvable in O(n^2) time.

Citation

Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (131:1-131:14). https://doi.org/10.4230/lipics.icalp.2019.131

Conference Name 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Conference Location Patras, Greece
Start Date Jul 8, 2019
End Date Jul 12, 2019
Acceptance Date Apr 19, 2019
Publication Date Jul 31, 2019
Deposit Date May 20, 2019
Publicly Available Date Mar 29, 2024
Pages 131:1-131:14
Series Title Leibniz International Proceedings inInformatics (LIPIcs)
Series Number 132
Series ISSN 1868-8969
Book Title 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
DOI https://doi.org/10.4230/lipics.icalp.2019.131
Public URL https://durham-repository.worktribe.com/output/1142728

Files


Accepted Conference Proceeding (667 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
© Eleni C. Akrida, George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis, and Viktor Zamaraev; licensed under Creative Commons License CC-BY.





You might also like



Downloadable Citations