Akrida, Eleni C. ;
Mertzios, George B. ;
Nikoletseas, Sotiris ;
Raptopoulos, Christoforos ;
Spirakis, Paul G. ;
Zamaraev, Viktor
How Fast Can We Reach a Target Vertex in Stochastic Temporal Graphs?
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}
}
04.07.2019
Keywords: 

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

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

Issue date: 

2019 
Date of publication: 

04.07.2019 