Bounding the Cover Time in Edge-Uniform Stochastic Graphs.
Ioannis Lamprou, Russell Martin, Paul G. Spirakis · arXiv (Cornell University) · 2017
We define a new model of stochastically evolving graphs, namely the \emph{Edge-Uniform Stochastic Graphs}. In this model, each possible edge of an underlying general static graph evolves independently being either alive or dead at each discrete time step of evolution following a (Markovian) stochastic rule. The stochastic rule is identical for each possible edge and may depend on the previous $k \ge 0$ observations of the edge's state. We study the behavior of a simple random walk taking place in such a dynamic graph. At each round of evolution, after the current graph instance is fixed, a single mobile agent moves uniformly at random to a neighboring node of its current placement. We explicitly derive the first upper bounds for the walk's cover time, i.e. the expected time until each node is visited at least once, and focus on the cases $k = 0$ and $k = 1$. For $k = 0$, our technique includes the use of a modified electrical network theory framework. On the other hand, for $k = 1$, we employ a mixing time argument and then reduce this case to the framework for the case $k = 0$. Finally, we discuss how this approach can be extended for any $k > 1$.