Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911569460330496 |
|---|---|
| author | Sudo, Yuichi Kitamura, Naoki Shibata, Masahiro Nakamura, Junya Tixeuil, Sébastien Masuzawa, Toshimitsu Wada, Koichi |
| author_facet | Sudo, Yuichi Kitamura, Naoki Shibata, Masahiro Nakamura, Junya Tixeuil, Sébastien Masuzawa, Toshimitsu Wada, Koichi |
| contents | 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 = Ω(m)$ is necessary. We also present deterministic algorithms whose required window size is $O(ε(n,m)\cdot m + n \log^2 n)$, where $ε(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+Θ(1)}$. The same algorithms also yield optimal or near-optimal exploration time: we prove lower bounds of $Ω((m - n + 1)n)$ in the $KT_0$ model and $Ω(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+Θ(1)}$. This yields tight bounds when parameterized solely by $n$: $Θ(n^3)$ for $KT_0$ and $Θ(n^2)$ for $KT_1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04619 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity Sudo, Yuichi Kitamura, Naoki Shibata, Masahiro Nakamura, Junya Tixeuil, Sébastien Masuzawa, Toshimitsu Wada, Koichi Distributed, Parallel, and Cluster Computing 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 = Ω(m)$ is necessary. We also present deterministic algorithms whose required window size is $O(ε(n,m)\cdot m + n \log^2 n)$, where $ε(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+Θ(1)}$. The same algorithms also yield optimal or near-optimal exploration time: we prove lower bounds of $Ω((m - n + 1)n)$ in the $KT_0$ model and $Ω(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+Θ(1)}$. This yields tight bounds when parameterized solely by $n$: $Θ(n^3)$ for $KT_0$ and $Θ(n^2)$ for $KT_1$. |
| title | Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2604.04619 |