Search papers, labs, and topics across Lattice.
This paper establishes tight bounds on the window size $T$ and exploration time for a single agent deterministically exploring $T$-interval-connected graphs, where the agent lacks knowledge of $T$, $n$, or $m$. The authors prove a lower bound of $T = \Omega(m)$ for the required window size and develop algorithms with window size $O(\epsilon(n,m)\cdot m + n \log^2 n)$, which is tight for dense graphs. Furthermore, they provide algorithms that achieve optimal or near-optimal exploration time, matching lower bounds of $\Omega((m - n + 1)n)$ and $\Omega(m)$ for the $KT_0$ and $KT_1$ visibility models, respectively.
Exploring dynamic networks requires a surprisingly large window size proportional to the number of edges, even when the network is guaranteed to be connected within each window.
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, $KT_0$ and $KT_1$, depending on whether the agent can observe the identifiers of neighboring nodes. 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. We also present deterministic algorithms whose required window size is $O(\epsilon(n,m)\cdot m + n \log^2 n)$, where $\epsilon(n,m) = \frac{\ln n}{1 + \ln m - \ln n}$. These bounds are tight for a wide range of $m$, in particular when $m = n^{1+\Theta(1)}$. The same algorithms also yield optimal or near-optimal exploration time: we prove lower bounds of $\Omega((m - n + 1)n)$ in the $KT_0$ model and $\Omega(m)$ in the $KT_1$ model, and show that our algorithms match these bounds up to a polylogarithmic factor, while being fully time-optimal when $m = n^{1+\Theta(1)}$. This yields tight bounds when parameterized solely by $n$: $\Theta(n^3)$ for $KT_0$ and $\Theta(n^2)$ for $KT_1$.
