Online Graph Exploration under T-Interval Connectivity

Abstract

We study deterministic exploration by a single agent in $T$-interval-connected graphs, a standard model of dynamic networks in which, for every time window of length $T$, the intersection of the graphs within the window is connected. The agent does not know the window size $T$, nor the number of nodes $n$ or edges $m$, and must visit all nodes of the graph. We consider two visibility models: in $K{T}_0$, the agent observes only its current node's identifier and port information; in $K{T}_1$, it additionally observes the identifiers of its currently available neighbors. We investigate two fundamental questions: the minimum window size that guarantees exploration, and the optimal exploration time under sufficiently large window size. For both models, we show that a window size $T=\Omega (m)$ is necessary, and we present deterministic algorithms whose required window size is $O(\xi (n,m)\cdot m+n{\log }^{2}n)$, where $\xi (n,m)=\frac{\ln n}{1+\ln m-\ln n}$. This window-size bound is tight for a wide range of $m$, in particular when $m=n^{1+\Theta (1)}$. Separately, for exploration time, we prove lower bounds of $\Omega ((m-n+1)n)$ in the $K{T}_0$ model and $\Omega (m)$ in the $K{T}_1$ model, even when the dynamic graph is $\infty$-interval-connected (i.e., even when all snapshots share a common spanning tree), and our algorithms match these time bounds up to a polylogarithmic factor. These bounds are also tight when parameterized solely by $n$: $\Theta (n^3)$ for $K{T}_0$ and $\Theta (n^2)$ for $K{T}_1$.