Abstract
Temporal graphs are used to abstractly model reallife 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 reallife 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 memoryk, k >= 0, which address this memory effect in an edgecentric 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(k1) is a special case of memoryk. 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 #Phard while {Best Policy} is solvable in O(n^2) time.
BibTeX  Entry
@InProceedings{akrida_et_al:LIPIcs:2019:10707,
author = {Eleni C. Akrida and George B. Mertzios and Sotiris Nikoletseas and Christoforos Raptopoulos and Paul G. Spirakis and Viktor Zamaraev},
title = {{How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs\l{}}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {131:1131:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10707},
URN = {urn:nbn:de:0030drops107071},
doi = {10.4230/LIPIcs.ICALP.2019.131},
annote = {Keywords: Temporal network, stochastic temporal graph, temporal path, #Phard problem, polynomialtime approximation scheme}
}
Keywords: 

Temporal network, stochastic temporal graph, temporal path, #Phard problem, polynomialtime approximation scheme 
Collection: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 
Issue Date: 

2019 
Date of publication: 

04.07.2019 