Efficiently Testing T-Interval Connectivity in Dynamic Graphs

Many types of dynamic networks are made up of durable entities whose links evolve over time. When considered from a {\em global} and {\em discrete} standpoint, these networks are often modelled as evolving graphs, i.e. a sequence of graphs $\mathcal{G}=(G_1,G_2,\mathrm{.}\mathrm{.}\mathrm{.},G_{\delta })$ such that $G_i=(V,E_i)$ represents the network topology at time step $i$. Such a sequence is said to be $T$-interval connected if for any $t\in [1,\delta -T+1]$ all graphs in $\{G_t,G_{t+1},\mathrm{.}\mathrm{.}\mathrm{.},G_{t+T-1}\}$ share a common connected spanning subgraph. In this paper, we consider the problem of deciding whether a given sequence ${\cal G}$is$T$-intervalconnectedforagiven$T$. We also consider the related problem of finding the largest $T$ for which a given $\mathcal{G}$ is $T$-interval connected. We assume that the changes between two consecutive graphs are arbitrary, and that two operations, {\em binary intersection} and {\em connectivity testing}, are available to solve the problems. We show that $\mathrm{\Omega }(\delta )$ such operations are required to solve both problems, and we present optimal $O(\delta )$ online algorithms for both problems. We extend our online algorithms to a dynamic setting in which connectivity is based on the recent evolution of the network.