License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.131
URN: urn:nbn:de:0030-drops-107071
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10707/
Go to the corresponding LIPIcs Volume Portal


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?

pdf-format:
LIPIcs-ICALP-2019-131.pdf (0.5 MB)


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.

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:1--131:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10707},
  URN =		{urn:nbn:de:0030-drops-107071},
  doi =		{10.4230/LIPIcs.ICALP.2019.131},
  annote =	{Keywords: Temporal network, stochastic temporal graph, temporal path, #P-hard problem, polynomial-time approximation scheme}
}

Keywords: Temporal network, stochastic temporal graph, temporal path, #P-hard problem, polynomial-time approximation scheme
Seminar: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Issue Date: 2019
Date of publication: 08.07.2019


DROPS-Home | Imprint | Privacy Published by LZI