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; Baier, Christel; Chatzigiannakis, Ioannis; Flocchini, Paola; Leonardi, Stefano

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., …Leonardi, S. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. In 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: Aug 9, 2019
• 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