Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T -Interval Connectivity Yuichi Sudo1 , Naoki Kitamura2 , Masahiro Shibata3 , Junya Nakamura4 , Sébastien Tixeuil5 , Toshimitsu Masuzawa6 , and Koichi Wada1
arXiv:2604.04619v1 [cs.DC] 6 Apr 2026
1
Hosei University, Tokyo, Japan The University of Osaka, Osaka, Japan 3 Kyushu Institute of Technology, Fukuoka, Japan 4 Toyohashi University of Technology, Aichi, Japan 5 Sorbonne University, Paris, France 6 Notre Dame Seishin University, Okayama, Japan 2
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, KT0 and KT1 , 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)·m+n log2 n), where ϵ(n, m) = ln n 1+Θ(1) . The 1+ln m−ln n . These bounds are tight for a wide range of m, in particular when m = n same algorithms also yield optimal or near-optimal exploration time: we prove lower bounds of Ω((m − n + 1)n) in the KT0 model and Ω(m) in the KT1 model, and show that our algorithms match these bounds up to a polylogarithmic factor, while being fully time-optimal when m = n1+Θ(1) . This yields tight bounds when parameterized solely by n: Θ(n3 ) for KT0 and Θ(n2 ) for KT1 .
1
Introduction
This paper studies deterministic exploration by a single mobile agent (i.e., an entity that autonomously traverses edges from node to node) in T -interval-connected graphs, a well-studied model of dynamic networks where every time window of length T has a connected intersection graph. In this section, we review related work, formalize our problem setting, and present our contributions in Sections 1.1, 1.2, and 1.3, respectively.
1.1
Related Work
Graph exploration by a single mobile agent in unknown undirected graphs is one of the most fundamental problems in distributed computing with mobile agents. The goal is to visit every node of the graph starting from an arbitrary node. Exploration algorithms often serve as foundational tools for solving other fundamental problems, such as rendezvous [Pel12, TSZ14, PP24], gathering [DPP14, DLFP+ 20, SKS+ 20, SKE+ 23, BDP23], dispersion [AMJ18, SSKM20, SSN+ 24, KS25, KKM+ 25], and gossiping [MT10, BDP23]. This problem has been studied extensively in the standard port-numbering model, where edges are locally labeled by port numbers at each endpoint. If nodes are labeled, it is well known that a simple depth-first search explores any connected graph in 2m edge traversals. Panaite and Pelc [PP99] improved the move complexity to m + 3n, where m is the number of edges and n is the number of nodes. Even if nodes are anonymous, a Universal Traversal Sequence (UTS) [AKL+ 79] and a Universal Exploration Sequence (UXS) [Kou02, Rei08, TSZ14, Xin07] enable graph exploration, provided that an upper bound on n is known. Whiteboards (i.e., local memory at each node) also enable exploration in anonymous graphs [PDDK96, YWB03, MT10, SBN+ 15, SOK25]. Using whiteboards, the algorithm of Priezzhev, Dhar, Dhar, and Krishnamurthy [PDDK96], known as the rotor-router, is self-stabilizing and explores any connected graph from any initial configuration. The cover time, i.e., the number of edge traversals until all nodes are visited, is bounded by O(mD) [YWB03], where D is the diameter. Sudo, Ooshita, and Kamei [SOK25] studied time–space trade-offs of deterministic and randomized self-stabilizing graph exploration. All the above results assume that the underlying graph is static. In many modern systems, however, the network topology evolves over time due to mobility, failures, or intermittent connectivity. Such systems are commonly modeled as time-varying graphs or temporal graphs, where the node set is fixed and the edge set changes over discrete time steps. Casteigts, Flocchini, Quattrociocchi, and Santoro [CFQS12] introduced a unifying framework for time-varying graphs and organized temporal connectivity assumptions into a hierarchy that has been influential in distributed computing, and Michail [Mic16] surveys algorithmic aspects of temporal graphs. In dynamic graphs, exploration can be substantially harder and may even be impossible without additional assumptions on the dynamics. One line of research considers offline temporal-graph problems where the entire evolution is given as input and the goal is to compute an exploration schedule (a temporal walk) that minimizes the exploration time. Michail and Spirakis [MS16] introduced the temporal graph exploration (TEXP) problem, and Erlebach, Hoffmann, and Kammer [EHK21] studied it extensively, establishing strong inapproximability bounds and presenting algorithms for special graph classes. In contrast, in many distributed settings the future evolution is not known. Under this online viewpoint, the algorithm must succeed under structural restrictions on the dynamics (e.g., periodicity or recurrence), as in the exploration of carrier-based time-varying graphs studied by Flocchini, Mans, and Santoro [FMS13], where edges are induced by the periodic movements of mobile entities called carriers. A particularly strong and algorithmically useful stability condition is T -interval connectivity: 1
for every time window of length T , the intersection of the graphs in the window is connected. Kuhn, Lynch, and Oshman [KLO10] introduced this notion in distributed computing to quantify robustness in highly dynamic networks. Intuitively, T -interval connectivity guarantees that in every window there exists a connected spanning subgraph that remains continuously present throughout the window, enabling algorithms to exploit a temporarily stable structure. Exploration under T -interval connectivity has been investigated primarily for restricted topologies. Ilcinkas and Wade [IW18] studied exploration of T -interval-connected dynamic rings and obtained tight bounds on the worst-case exploration time. In their offline setting, the agent knows the entire evolution of the graph, while in the online setting they additionally require δ-recurrence, meaning that every edge appears at least once in every δ consecutive time steps, to guarantee that all nodes can be visited. Beyond rings, Ilcinkas, Klasing, and Wade [IKW14] studied√exploration O( log n) n-time of 1-interval-connected √ cacti graphs (i.e., T = 1) in the offline setting, giving a 2 Ω( log n) algorithm and a 2 n-time lower bound. There is also a substantial body of work on dynamic graphs under different models and objectives. Gotoh, Sudo, Ooshita, and Masuzawa [GSOM20] study exploration with partial predictions about future edge availability, representing a middle ground between the offline and online settings. Di Luna, Dobrev, Flocchini, and Santoro [DDFS16] studied online exploration of 1-intervalconnected rings with multiple agents, focusing on minimizing the number of agents and the cover time. Building on these results, Gotoh, Sudo, Ooshita, Kakugawa, and Masuzawa [GSO+ 21] studied online exploration of an i × j dynamic torus by multiple agents, where each row and each column forms a 1-interval-connected ring. Finally, Gotoh, Flocchini, Masuzawa, and Santoro [GFMS21] provided tight bounds on the number of agents required to explore temporal graphs of arbitrary topology in the online setting under temporal connectivity and stronger connectivity assumptions. These works collectively highlight the impact of connectivity assumptions and the number of agents on the feasibility and complexity of exploration in dynamic networks. Despite this progress, the minimum window size and the exploration time for single-agent exploration on T -interval-connected graphs with arbitrary topology remain unknown.
1.2
Models and Notations
Let N = {0, 1, . . . } and N≥1 = {1, 2, . . . } denote the sets of non-negative and positive integers, respectively. For real numbers x and y, we define the integer interval [x..y] = {k ∈ N | x ≤ k ≤ y}. We use log to denote the base-2 logarithm, and ln to denote the natural logarithm. For any graph G = (V, E), we denote by dG (u, v) the distance between nodes u and v. We consider a dynamic graph G = (V, E) with an underlying graph G = (V, E), where V is a common set of nodes and E : N → 2E is a function such that E(t) denotes the set of edges that appear at time t ∈ N. For each t ∈ N, we denote the static snapshot T of G at time t by Gt = (V, E(t)). For T ∈ N≥1 , G is said to be T -interval-connected if V, i∈[t..t+T −1] E(i) is connected for all t ∈ N. We say that an edge e ∈ E appears or is present at time t if e ∈ E(t). The number of nodes (resp. edges) of G refers to that of its underlying graph G, i.e., |V | (resp. |E|), which we often denote by n (resp. m). We say that u, v ∈ V are neighbors if {u, v} ∈ E, and denote by N (v) = {u ∈ V | {u, v} ∈ E} the set of neighbors of v. The degree of a node v is δ(v) = |N (v)|. Each node v ∈ V has a unique label id (v), and we use v and id (v) interchangeably when clear from the context. Each edge incident to v is assigned a locally unique port number. Formally, for each v ∈ V , there is a bijection λv : N (v) → [1..δ(v)], and for p ∈ [1..δ(v)] we denote by N (v, p) the unique neighbor u with λv (u) = p. For each t ∈ N, we denote by ν(t) ∈ V the node at which the agent is located at time t. For t ≥ 1, we define pin (t) = λν(t) (ν(t − 1)), that is, pin (t) is the incoming port through which the 2
Table 1: The required window size and exploration time Theorem 1 (GreedyExp0 ) Theorem 3 (lower bound) Theorem 4 (lower bound) Theorem 2 (GreedyExp1 ) Theorem 3 (lower bound) Theorem 5 (lower bound)
model KT0 KT0 KT0 KT1 KT1 KT1
required window size O(ϵm + n log2 n) Ω(m) any O(ϵm + n log2 n) Ω(m) any
exploration time O((m − n + 1)n + n log2 n) any Ω((m − n + 1)n) O(ϵm + n log2 n) any Ω(m)
agent arrived at its current location ν(t).1 We define pin (0) = ⊥. For t ∈ N and v ∈ V , we define P (v, t) = {λv (u) | {u, v} ∈ E(t)}, that is, the set of available ports at v at time t. We consider two visibility models, KT0 and KT1 , depending on whether the agent can observe the identifiers of its neighboring nodes. This distinction allows us to quantify the impact of local visibility on graph exploration in T -interval-connected graphs. In the KT0 model, at each time t ∈ N, the agent receives as input (id (ν(t)), δ(ν(t)), P (ν(t), t), pin (t)) and selects a port p ∈ P (ν(t), t), moving to the neighbor N (ν(t), p). Alternatively, it may choose to terminate. In the KT1 model, the agent additionally learns Vobs (t) = {v ∈ V | {ν(t), v} ∈ E(t)} and λν(t) (v) for each v ∈ Vobs (t), i.e., the identifiers of all neighbors of ν(t) in Gt together with the corresponding port numbers. The agent does not know the window size T , the number of nodes n, or the number of edges m a priori.
1.3
Our Contribution
This paper addresses the following two natural questions for single-agent exploration on T -intervalconnected graphs: • What is the minimum window size T that enables the exploration of any T -interval-connected graph with n nodes (and m edges)? • Given a sufficiently large T , what is the optimal exploration time? To formalize the first question, we define the functions ψk (n) and ψk (n, m) for the KTk model, where k ∈ {0, 1}, as follows: Definition 1. For n ≥ 3 and m ∈ [n.. n2 ], let ψk (n, m) denote the minimum T such that there exists a deterministic algorithm under which a single agent explores every T -interval-connectedgraph with n nodes and m edges in the KTk model. We define ψk (n) = max{ψk (n, m) | m ∈ [n.. n2 ]}. Note 1. We assume m ≥ n, although the underlying graph may be connected even when m = n−1. We impose this assumption because we study exploration on T -interval-connected dynamic graphs: if m = n − 1, every edge must be present at all times to satisfy T ≥ 1, and hence the problem reduces to the static case. This assumption also implies n ≥ 3 for simple graphs. Throughout this paper, for any n ≥ 3 and m ≥ n, we define ϵ(n, m) =
ln n 1 + ln m − ln n
1
We assume without loss of generality that ν(t − 1) ∈ N (ν(t)) (i.e., the agent moves to a neighboring node at each time step), since the stay option only consumes the window size and does not contribute to solving single-agent graph exploration on T -interval-connected graphs.
3
which is chosen so that n1+1/ϵ(n,m) = em. When n and m are clear from the context, we simply write ϵ for ϵ(n, m). To answer the above questions, we first present the following upper bounds. Theorem 1. In the KT0 model, there exist a function τ (n, m) = O(ϵ(n, m) · m + n log2 n) and n a deterministic algorithm A such that, for any n ≥ 3 and m ∈ [n.. 2 ], a single agent running A explores any τ (n, m)-interval-connected graph with n nodes and m edges in O((m−n+1)n+n log2 n) time. Theorem 2. In the KT1 model, there exist a function τ (n, m) = O(ϵ(n, m) · m + n log2 n) and a n deterministic algorithm A such that, for any n ≥ 3 and m ∈ [n.. 2 ], a single agent running A explores any τ (n, m)-interval-connected graph with n nodes and m edges in at most τ (n, m) time. Corollary 1. For any k ∈ {0, 1}, ψk (n, m) = O(ϵ(n, m) · m + n log2 n). The above upper bounds on the minimum window size are tight for a wide range of m, i.e., when m = n1+Ω(1) , since we prove the following lower bounds. Theorem 3. For any k ∈ {0, 1}, ψk (n, m) = Ω(m). Even if m = n1+o(1) , the gap between the above upper and lower bounds is at most ϵ(n, m) + (n log2 n)/m = O(log2 n). Moreover, when parameterized solely by n, these bounds are tight: we obtain the following corollary by substituting m = n2 . Corollary 2. For any k ∈ {0, 1}, ψk (n) = Θ(n2 ). This paper also establishes the following lower bounds on the exploration time: Theorem 4. In the KT0 model, every deterministic algorithm requires Ω((m − n + 1)n) time to explore every ∞-interval-connected graph with n ≥ 3 nodes and m ∈ [n.. n2 ] edges. Theorem 5. In the KT1 model, every deterministic algorithm requires Ω(m) time to explore every ∞-interval-connected graph with n ≥ 3 nodes and m ∈ [n.. n2 ] edges. Thus, we obtain a tight bound on the exploration time in the KT0 model whenever m = n + Ω(log2 n). The bound for the KT1 model is also nearly tight, with the same multiplicative gap as that for the minimum window size. Notably, these theorems establish tight bounds on the exploration time when parameterized solely by n: Θ(n3 ) for KT0 and Θ(n2 ) for KT1 . Our contributions are summarized in Table 1. Since the upper bound results (Theorems 1 and 2) are more technically involved than the others, we present them in the first ten pages.
2
Upper Bounds
In this section, we present two algorithms, GreedyExp1 and GreedyExp0 , for the KT1 and KT0 models, respectively. Throughout this section, we define τ (n, m) = c · ⌈ϵ(n, m) · m + n ln2 n⌉, where c ∈ N≥1 is a constant that will be chosen sufficiently large. In the remainder of this section, we fix a τ (n, m)-interval-connected graph G = (V, E) with underlying graph G = (V, E), where n = |V | and m = |E|. We then show, for a sufficiently large constant c, that GreedyExp1 explores G within τ (n, m) time in the KT1 model in Section 2.1, whereas GreedyExp0 explores G within O((m − n + 1)n) time in the KT0 model in Section 2.2. These results immediately prove Theorems 2 and 1, respectively. In what follows, we denote by vcur ∈ V the current location of the agent, particularly in the pseudocode (Algorithms 1 and 2). In other words, vcur = ν(t) at time t. 4
Algorithm 1: GreedyExp1 . The update rules of Vvis , Vmap , Λmap , and Pdel are omitted from the pseudocode; see the main text for these rules. Initially: Vvis = {ν(0)}, Vmap = {ν(0)} ∪ Vobs (0), Pdel (ν(0)) = [1..δ(ν(0))] \ P (ν(0), 0), ( λu (v) if u = ν(0) ∧ v ∈ Vobs (0) Λmap (u, v) = ⊥ otherwise 1 while Vmap \ Vvis ̸= ∅ do 2 Move to the next node on a shortest path from vcur to w in Gmap , where w is an arbitrary closest node in Vmap \ Vvis from vcur in Gmap
2.1
With 1-hop view
The strategy of GreedyExp1 , whose pseudocode is given in Algorithm 1, is very simple. During exploration, the agent constructs a map of the subgraph it has observed so far, removing all edges that it has observed to be unavailable at least once, and always moves toward the closest unvisited node in the map. We describe this more precisely below. The agent maintains two sets of nodes Vmap , Vvis and two functions Λmap : Vmap × Vmap → N and Pdel : Vmap → 2N . The set Vmap (resp. Vvis ) is the set of nodes that the agent has observed (resp. visited) so far. Formally, at time t, Vmap = {ν(0)} ∪ Vobs (0) ∪ Vobs (1) ∪ · · · ∪ Vobs (t),
Vvis = {ν(i) | i ∈ [0..t]}.
Note that Vvis ⊆ Vmap always holds. For each pair u, v ∈ Vmap , the agent memorizes Λmap (u, v) = λu (v) once it learns λu (v), which occurs at time t when either (i) ν(t) = u and v ∈ Vobs (t), or (ii) ν(t−1) = v and ν(t) = u (possibly {u, v} ̸∈ E(t) in the second case). Until then, i.e., before learning λu (v), Λmap (u, v) returns ⊥. For each node v ∈ Vmap , Pdel (v) is the set of all ports that have been unavailable at v at least once so far. Initially, Pdel (v) = ∅, and at each time t, all ports observed as unavailable at time t (i.e., [1..δ(ν(t))] \ P (ν(t), t)) are added to Pdel (ν(t)). We then define the map 1 2 ), where Gmap = (Vmap , Emap ∪ Emap 1 Emap = {{u, v} | u, v ∈ Vvis ∧ Λmap (u, v) ∈ / Pdel (u) ∪ {⊥} ∧ Λmap (v, u) ∈ / Pdel (v) ∪ {⊥}},
and
2 Emap = {{u, v} | u ∈ Vvis ∧ v ∈ Vmap \ Vvis ∧ Λmap (u, v) ∈ / Pdel (u) ∪ {⊥}}.
1 2 Intuitively, Emap ∪ Emap represents the set of edges that have always been present whenever the agent is located at one of their endpoints. At each time, the agent chooses any node w ∈ Vmap \ Vvis closest to vcur in Gmap and moves to the next node on a shortest path from vcur to w in Gmap (line 2). Note that the newly selected shortest path after the move may not be a suffix of the previous one, because the edge incident to the current node on that path may disappear at that time. The agent terminates when Vmap = Vvis , i.e., when no unvisited nodes remain in the map (line 1). In the remainder of Section 2.1, we prove that under GreedyExp1 , a single agent visits all nodes of G and terminates within τ (n, m) = O(ϵm + n log2 n) time.
Remark 1. Since the window size of G equals the target upper bound τ (n, m) on the exploration time, we may assume w.l.o.g. that all snapshots share a common spanning tree T∩ , i.e., every edge in T∩ is always present in G. Indeed, this assumption does not affect the behavior of GreedyExp1 within τ (n, m) steps. 5
Lemma 1. Vmap = Vvis implies Vvis = V . Proof. Assume for contradiction that at some time t, we have Vmap = Vvis ⊊ V . Let ET be the edge set of the spanning tree T∩ mentioned in Remark 1. Then there exists an edge {u, v} ∈ ET with u ∈ Vvis and v ∈ / Vvis . Since u ∈ Vvis at time t, the agent has visited u by time t, and hence v ∈ Vmap , because {u, v} ∈ ET and is therefore always present. This contradicts Vmap = Vvis . Lemma 1 guarantees the correctness of GreedyExp1 provided that it terminates within τ (n, m) time. To bound the exploration time by τ (n, m), we introduce the potential ( min{dGmap (vcur , u) | u ∈ Vmap \ Vvis } if Vvis ⊊ Vmap , dcur = 0 if Vvis = Vmap . Since vcur ∈ Vvis at all times, dcur = 0 if and only if Vmap = Vvis . Thus, it suffices to show that dcur reaches zero within τ (n, m) time. At any time, dcur is determined by vcur , Vvis , Vmap , Λmap , and Pdel . At time 0, we have dcur = 1 because Vvis = {ν(0)} and Gmap is the star graph centered at ν(0) with leaf set Vobs (0). For convenience of the analysis, when the agent moves from ν(t) to ν(t + 1) at time t, we consider the following two steps to occur sequentially in this order: 1. In the first step, the current node vcur changes from ν(t) to ν(t + 1). If ν(t + 1) ∈ / Vvis , then ν(t + 1) is added to Vvis . Simultaneously, Vmap and Λmap are updated according to Vobs (t + 1). 2. In the second step, Pdel is updated according to Vobs (t + 1). In the first step, if ν(t+1) has already been visited, then dcur decreases by exactly one; otherwise, dcur may remain unchanged or increase. We define ιV : V → N ∪ {−1} as follows: for any v ∈ V \ {ν(0)}, ιV (v) is the amount by which dcur increases during the first step when the agent visits v for the first time. If v is the last node visited by the agent, then dcur decreases from 1 to 0 at that time, and we define ιV (v) = −1 for this node. For simplicity, we set ιV (ν(0)) = 0. In the second step, some edges incident to ν(t + 1) may be eliminated from Gmap . We fix an arbitrary order of these edges and assume that they are eliminated sequentially. Each elimination may increase dcur , but each edge e ∈ E can be eliminated at most once throughout the execution of GreedyExp1 . To capture this increase, we define ιE : E → N as follows: for each edge e ∈ E, ιE (e) is the amount by which dcur increases when e is eliminated, and ιE (e) = 0 if e is never eliminated from Gmap . P P Lemma 2. Vmap = Vvis holds within at most n + v∈V ιV (v) + e∈E ιE (e) time. Proof. Let Vt denote Vvis at time t, and let Ēt be the set of edges eliminated from Gmap when the agent moves from ν(t) to ν(t + 1) in the second step of time t. In the first step of time t, dcur increases by ιV (v) if Vt+1 = Vt ∪ {v} for some P v ∈ V ; otherwise, dcur decreases by exactly one. In the second step of time t, dcur increases by e∈Ēt ιE (e). Since dcur = 1 at time 0, we have dcur = 1 − (t − |Vt | + 1) +
X v∈Vt
ιV (v) +
t X X j=0 e∈E¯j
ιE (e) ≤ −t + n +
X v∈V
ιV (v) +
X
ιE (e)
e∈E
P P at time t. Since dcur is non-negative, it reaches zero within n + v∈V ιV (v) + e∈E ιE (e) time, and dcur = 0 holds only when Vmap = Vvis . P P By Remark 1 andPLemmas 1 and 2, it suffices to show v∈V ιV (v) + e∈E ιE (e) = O(ϵm + P n log2 n). We prove v∈V ιV (v) ≤ 2n log n in Lemma 4 and e∈E ιE (e) = O(ϵm + n log2 n) in Lemma 6. We use the following lemma to prove Lemma 4. 6
Lemma 3. Let G′ = (V ′ , E ′ ) be any simple, undirected, and connected graph with n′ ≥ 1 nodes, P and let v1 , v2 , . . . , vn′ be the nodes of G′ in any order. Then, i∈[1..n′ −1] f (i) ≤ 2n′ log n′ , where f (i) = min{dG′ (vi , vj ) | j ∈ [i + 1..n′ ]}. Proof. We prove the lemma by induction on n′ . The base case n′ = 1 is trivial, as both sides are equal to 0. Consider the general case n′ ≥ 2. Let TG′ be any spanning tree of G′ . Let cT be a 2 centroid of TG′ , and let T1 , T2 , . . . , Tℓ be the connected components of TG′ − cP T . For each r ∈ [1..ℓ], ′ let nr = |V (Tr )|. Since cT is a centroid, we have nr ≤ n /2 for every r, and ℓr=1 nr = n′ − 1. Fix r. Let x1 , . . . , xnr be the nodes of Tr in the order they appear in the sequence v1 , v2 , . . . , vn′ , and let ar = xnr . For s ∈ [1..nr − 1], define fr (s) = min{dTr (xs , xt ) | t ∈ [s + 1..nr ]}. Then, for each vi = xs ̸= ar , we have f (i) ≤ fr (s). by the induction hypothesis, the total contribution of PnrTherefore, −1 all nodes in Tr \ {ar } is at most s=1 fr (s) ≤ 2nr log nr ≤ 2nr log(n′ /2) = 2nr (log n′ − 1). We also need to bound the contribution of the exceptional nodes a1 , a2 , . . . , aℓ together with the centroid cT . Let b1 , b2 , . . . , bℓ+1 be these nodes in the order they appear in the sequence v1 , v2 , . . . , vn′ . Note that bℓ+1 = vn′ , and thus we ignore its contribution. Since bi+1 appears later than Pℓbi in the sequence, the total contribution of the remaining nodes b1 , b2 , . . . , bℓ is bounded by i=1 dTG′ (bi , bi+1 ) ≤ ′ 2(n1 + n2 + · · · + nℓ ) ≤ 2n . Consequently, ′ −1 nX
i=1
Lemma 4.
f (i) ≤
ℓ X
2nr (log n′ − 1) + 2n′ ≤ 2n′ (log n′ − 1) + 2n′ ≤ 2n′ log n′ .
r=1
P
v∈V ιV (v) ≤ 2n log n.
Proof. Let v1 , v2 , . . . , vn be the distinct nodes visited by thePagent in this order, and let T∩ be n−1 the spanning tree mentioned in Remark 1. By Lemma 3, i=1 f (i) ≤ 2n log n, where f (i) = min{dT∩ (vi , vj ) | j ∈ [i + 1..n]}. Since ιV (vn ) = −1, it suffices to show that ιV (vi ) ≤ f (i). By definition, in T∩ , there exists a path u0 , u1 , . . . , uf (i) such that u0 = vi and uf (i) = vj for some j ∈ [i + 1..n]. Since every edge in T∩ is always present, there exists k ∈ [1..f (i)] such that Gmap contains the path u0 , u1 , . . . , uk and uk is unvisited at the time vi is first visited. This implies ιV (vi ) ≤ k ≤ f (i). P To bound e∈E ιE (e) in Lemma 6, for each k ∈ N, we define F ′ (k) = |{e ∈ E | ιE (e) ≥ k}| , that is, the number of edges whose deletion increases dcur by at least k. We bound F ′ (k) using the following well-known theorem from extremal graph theory relating the girth and the number of edges. Here, the girth of a graph G′ is defined as the length of a shortest cycle in G′ . If G′ does not contain any cycle, its girth is defined as ∞. Theorem 6 (Theorem 4.1 in [FS13]3 ). Let g ∈ N≥1 . For any graph G′ = (V ′ , E ′ ) with girth at least 2g + 1, 1 1 |E ′ | ≤ |V ′ |1+1/g + |V ′ |. 2 2 Lemma 5. For any k ∈ N≥1 , F ′ (2k − 1) ≤ 12 n1+1/k − n2 + 1. 2 3
Every tree has one or two centroids. According to [FS13], an essentially equivalent inequality was proved by Alon, Hoory, and Linial [AHL02].
7
Proof. Consider the subgraph GX = (V, X ∪ ET ), where X = {e ∈ E | ιE (e) ≥ 2k − 1}, and ET is the edge set of the spanning tree T∩ mentioned in Remark 1. By Theorem 6, it suffices to show that GX has girth at least 2k + 1, since F ′ (2k − 1) = |X ∪ ET | − |ET | ≤ 21 n1+1/k − n2 + 1. Note that every edge in ET is always present, and thus X ∩ ET = ∅. Assume for contradiction that GX = (V, X ∪ ET ) contains a cycle C of length at most 2k. Since T∩ is a tree, C contains at least one edge in X. Let e = {u, v} be the first edge removed from Gmap among those in C, and let G′ = (V, E ′ ) be Gmap immediately before the removal of e. Then dG′ −e (u, v) − dG′ (u, v) ≥ 2k − 1, since otherwise the removal of e would not increase dcur by at least 2k − 1. Thus, dG′ −e (u, v) ≥ 2k − 1 + dG′ (u, v) = 2k, implying that G′ does not contain the cycle C, i.e., C \ E ′ ̸= ∅. Let Y = C \ E ′ , which is non-empty. Every edge in ET is always present, and e is the first edge in C removed from Gmap . Therefore, at the time immediately after the removal of e, (i) the agent is at either u or v, i.e., vcur ∈ {u, v}, (ii) both endpoints of every edge in Y are unvisited, and (iii) all edges in C \ (Y ∪ {e}) are present. Hence, at this moment, there exists a path from vcur to some unvisited node consisting only of edges in C \ (Y ∪ {e}), and thus dcur ≤ |C| − 1 ≤ 2k − 1. Since dcur ≥ 1 before the removal of e, this contradicts ιE (e) ≥ 2k − 1. n Corollary 3. For any integer k ≥ 2 ln n, F ′ (2k − 1) ≤ n ln k + 1.
Proof. For any real number 0 ≤ x < 1, we have ex ≤ (1 − x)−1 . Thus, letting y = (ln n)/k ≤ 1/2, ny n n1+1/k = ney ≤ 1−y = n+ 1−y ≤ n+2ny = n+ 2n kln n . The corollary then follows from Lemma 5. Lemma 6.
P
e∈E ιE (e) = O(ϵm + n log
2
n).
Proof. By definition, F ′ (k) ≤ m for any k ∈ N. Moreover, since dcur is always at most n − 1, F ′ (n) = 0. Therefore, we have X X X ιE (e) ≤ 2k(F ′ (2k − 1) − F ′ (2k + 1)) ≤ 2 F ′ (2k − 1) k∈[1.. n ] 2
e∈E
k∈[1.. n ] 2
≤2
X
m+
k∈[1..ϵ]
X
=
X k∈[ϵ..2 ln n]
n1+1/k
+
1 1+1/k n + 2
X
k∈[2 ln n.. n ] 2
n ln n +1 k
O(ϵm + n log2 n).
k∈[ϵ..2 ln n]
Thus, the first term is bounded by X X n1+1/k + n1+1/k ≤ (ϵ+1)n1+1/ϵ +2n1+1/(2ϵ) ln n ≤ (ϵ+1)n1+1/ϵ +2ϵn1+1/ϵ = O(ϵm), k∈[ϵ..2ϵ]
k∈[2ϵ..2 ln n]
where in the third inequality we use the fact that, for any real number x > 0, ln n < xn1/(2x) . A proof of this fact is provided in the appendix for completeness (Lemma 10). Thus, Theorem 2 follows from Remark 1 and Lemmas 1, 2, 4, and 6.
2.2
With 0-hop view
In the KT1 model, at each time t, the agent obtains Vobs (t) and λν(t) (v) for each v ∈ Vobs (t). In contrast, in the KT0 model, the agent does not have access to this information. Therefore, the 8
Algorithm 2: GreedyExp0 . The update rules of Vmap , Λmap , and Pdel are omitted from the pseudocode except for line 5; see the main text for these rules. Initially: Vmap = {ν(0)}, Λmap (ν(0), ν(0)) = ⊥, Pdel (ν(0)) = [1..δ(ν(0))] \ P (ν(0), 0) Notation: Popen (v) = {p ∈ [1..δ(v)] | ∀u ∈ Vmap : p ̸= Λmap (v, u)}, Vtarget = {v ∈ Vmap | Popen (v) \ Pdel (v) ̸= ∅} 3 while Vtarget ̸= ∅ do 4 timer ← 0 5 Reset Pdel P 1 |+⌈ 6 while Vtarget ̸= ∅ and timer < τ (|Vmap |, |Emap v∈Vmap |Popen (v)|/2⌉) do 7 if vcur ∈ Vtarget then 8 Move via an arbitrary port in Popen (vcur ) \ Pdel (vcur ) 9 else 10 Move to the next node on a shortest path from vcur to w in G′map , where w is an arbitrary closest node in Vtarget from vcur in G′map 11
timer ← timer + 1
previous algorithm GreedyExp1 no longer works in the KT0 model, and we modify it to obtain a new algorithm GreedyExp0 . The pseudocode of GreedyExp0 is given in Algorithm 2. Fortunately, only a few modifications are needed. First, in the KT0 model, the agent learns λu (v) only when it traverses the edge {u, v} in either direction, in which case it sets Λmap (u, v) = λu (v) in GreedyExp0 . Second, in GreedyExp1 , the agent always moves toward a closest node in Vmap \ Vvis in the map. However, in the KT0 model, the agent learns the identifiers only of visited nodes, and thus Vmap \ Vvis is always empty, i.e., Vmap = Vvis . Therefore, we introduce the set of unused (or open) ports at each v ∈ Vmap , as well as the set of target nodes (that have at least one unused port that was always observed when visited), as follows: Popen (v) = {p ∈ [1..δ(v)] | ∀u ∈ Vmap : p ̸= Λmap (v, u)}, Vtarget = {v ∈ Vmap | Popen (v)\Pdel (v) ̸= ∅}. By the update rule of Λmap , for any port p ∈ [1..δ(v)], we have p ∈ Popen (v) if and only if the edge {v, N (v, p)} has not been used before. At any time t, the agent behaves as follows, provided that Vtarget ̸= ∅. If ν(t) ∈ / Vtarget , it moves ′ 1 1 toward a closest node in Vtarget in the map Gmap = (Vmap , Emap ), where Emap is the edge set defined 2 in Section 2.1. (We do not use Emap because Vmap \ Vvis = ∅ at all times.) Otherwise (that is, when ν(t) ∈ Vtarget ), the agent chooses any unused port p ∈ Popen (ν(t)) \ Pdel (ν(t)) and moves to the neighbor N (ν(t), p), i.e., it traverses an unused edge. The agent terminates once Vtarget = ∅. The main issue here is that, unlike GreedyExp1 , the exploration time may exceed the target window size τ (n, m). Therefore, the claim of Remark 1 no longer holds, and for t ≥ τ (n, m), G′map may become disconnected. This may break the correctness of the above strategy. To address this issue, the agent periodically resets Pdel : it sets Pdel (v) = ∅ for all v ∈ V \ {vcur }, while setting Pdel (vcur ) to the set of unavailable ports at the current time. A round is a segment of the exploration that starts either at the beginning or at a reset of Pdel and ends at the next reset or termination. In each round, the agent stores in the variable timer the number of time steps that have elapsed since the beginning of the round. Whenever timer reaches τ (n′ , m′ ), where n′ = |Vmap | 1P ′ 1 and m = |Emap | + ⌈ 2 v∈Vmap |Popen (v)|⌉, the agent resets Pdel and proceeds to the next round. We use n′ and m′ here because the agent does not know the actual values of n and m. Since n′ ≤ n and m′ ≤ m, we have τ (n′ , m′ ) ≤ τ (n, m). Therefore, in each round, there exists a spanning tree 9
all of whose edges are present throughout the round. Hence, we can use an analysis similar to that in Section 2.1. Lemma 7. While Vtarget ̸= ∅, there exists at least one node in Vtarget in the connected component of G′map that contains vcur . Moreover, the agent terminates only after it has visited all nodes in V . Proof. In each round r, there exists a spanning tree Tr such that all its edges are present throughout the round. At any time during round r, one of the following holds: (i) G′map contains every edge of Tr , or (ii) some node incident with an unused edge in Tr is reachable from vcur in G′map . Therefore, if Vtarget ̸= ∅, there exists a node in Vtarget that is reachable from vcur in G′map ; otherwise, G′map contains all edges of Tr , implying that all nodes have already been visited. P 1 | + ⌈1 Let nr = |Vmap | and mr = |Emap v∈Vmap |Popen (v)|⌉ at the end of round r. By definition, 2 each round r completes in τ (nr , mr ) time. If the agent traverses an unused edge e = {u, v} from u to v, but the destination v has already been visited, we call this movement a redundant movement. Such movements are inevitable in the KT0 model, since the agent does not know the destinations of unused edges. Let zr be the number of redundant movements made by the agent during round r. Then the following lemma holds. r ,mr ) Lemma 8. If Vtarget ̸= ∅ at the end of round r, then zr ≥ τ (n2n .
Proof. Before the end of the round, we always have Vtarget ̸= ∅. Define the potential d′cur = min{dG′map (vcur , u) | u ∈ Vtarget }. By Lemma 7, we have d′cur ≤ nr − 1 at all times. Whenever ν(t) ∈ / Vtarget at time t, the agent moves toward a closest node in Vtarget , and thus d′cur decreases by one. However, the agent then observes the unavailable ports at ν(t + 1), which may increase d′cur . We consider two cases: (i) ν(t + 1) leaves Vtarget due to this observation, and (ii) Vtarget remains unchanged. In the first case, d′cur may increase at most by nr − 1. To bound this increase, we define ι′V (ν(t + 1)) as the increase in d′cur when ν(t + 1) leaves Vtarget . In the second case, let Ēt′ be the set of edges removed from G′map due to this observation (and set Ēt′ = ∅ in the first case). We fix an arbitrary order on these edges and assume that they are removed sequentially. For any e ∈ Ēt′ , we define ι′E (e) as the increase in d′cur when e is removed from G′map . Whenever ν(t) ∈ Vtarget at time t, the agent moves via an unused edge. If the movement is redundant, d′cur may increase by at most nr − 1; otherwise, ν(t + 1) is newly added to Vmap . If the newly added node ν(t + 1) belongs to Vtarget , then d′cur remains zero; otherwise, it may increase. In this case, we treat the event as if ν(t + 1) leaves Vtarget , so that the increase in d′cur is given by ι′V (ν(t + 1)). We define ι′V (v) = 0 for any node v that does not leave Vtarget during round r. Similarly, we define ι′E (e) = 0 for any edge e that does not belong to Ēt′ at any time t during round r. Since round r lasts exactly τ (nr , mr ) time steps, the initial value of the potential d′cur is at most nr − 1, and vcur holds P ∈ Vtarget P for ′at most mr time steps, we obtain τ (nr , mr ) ≤ (nr − 1) + ′ m r + e∈E ιE (e). In the same way as in Lemmas 4 and 6, we obtain v∈V ιV (v) + Pr + (n′ r − 1)zP ′ (e) = O(ϵ(n , m ) · m + n log2 n ). This sum is less than τ (n , m )/2 − n − ι (v) + ι r r r r r r r r v∈V V e∈E E mr , since we can choose a sufficiently large constant c for the hidden constant in τ (n, m). Thus, r ,mr ) zr ≥ τ (n2n . Corollary 4. The agent terminates in O((m − n + 1)n + n log2 n) time. Proof. By definition, the agent makes at most m − n + 1 redundant movements. Thus, by Lemma 8, the total time required for all rounds except the last is at most 2(m − n + 1)n. The last round also completes within τ (n, m) = O(ϵm + n log2 n) = O((m − n + 1)n + n log2 n) time by definition. Thus, Theorem 1 follows from Lemma 7 and Corollary 4. 10
𝑢
𝑣
𝑢
𝑣
Figure 1: K5 (u, v) (left) and K6 (u, v) (right)
3
Lower Bounds
In this section, we prove the lower bounds stated in Section 1.3. Specifically, we prove Theorem 3, 4, and 5. To prove Theorem 3, we introduce the graph Kn (u, v) as a gadget, obtained by removing the edge {u, v} from the complete graph on n nodes (see Figure 1 for examples). We call u and v the gates of Kn (u, v), and the remaining nodes traps. The key advantage of this gadget is that once the agent visits any trap, the adversary can confine the agent within the gadget for Ω(n2 ) time, as formalized in the following lemma. Lemma 9. For any deterministic algorithm A and any sufficiently large n, there exists an ∞interval-connected graph G with underlying graph Kn (u, v) = (V, E) such that a single agent running A in the KT1 model, starting from a node other than u or v, requires Ω(n2 ) time to reach either u or v. This claim holds even if the agent knows the entire structure of the underlying graph, including the port assignments λx (y) for all x, y ∈ V , a priori. Proof. Note that G can depend on algorithm A, which is deterministic. Therefore, it suffices to describe an adversarial strategy that adaptively determines, at each time t, which edges are present based on ν(t) (i.e., the current location of the agent), thereby preventing the agent from reaching a designated node u or v for Ω(n2 ) time while preserving ∞-interval connectivity. The adversary maintains a set Vblk ⊆ V of blocked nodes, a set Vdone ⊆ V of nodes visited by the agent since the last update of Vblk , and a set Edel of deleted edges. The set Edel represents the output of the adversarial strategy. That is, at each time step t, the adversary defines E(t) = E \Edel . Initially, Vblk = {u, v}, Vdone = {ν(0)}, and Edel = ∅. The adversary proceeds as follows: 1. Edel ← Edel ∪ {{vcur , w} ∈ E | w ∈ Vblk }. 2. Let the agent make one move according to A. 3. Vdone ← Vdone ∪ {vcur }. 4. If |Vdone | + |Vblk | < n − 1, return to Step 1. 5. Vblk ← Vblk ∪ {v}, where v is the unique node in V \ (Vblk ∪ Vdone ). 6. Vdone ← {vcur }. 7. If |Vblk | < n − 2, return to Step 1; otherwise, terminate. The agent moves only in Step 2, whereas Step 1 ensures that all edges between the current location and the blocked nodes, including u and v, belong to Edel , and hence are never present in 11
𝐾# = 𝐾" (𝑢# , 𝑣# )
𝐾 ! = 𝐾" (𝑢! , 𝑣! )
𝑣#
𝑣!
𝑢#
𝑢!
𝑃$%!"%& 𝑝#
𝑥
𝑦
𝑧
Figure 2: The underlying graph for the proof of Theorem 3, excluding null edges Step 2. Therefore, the agent never visits u or v before this strategy terminates. The agent must make P at least n − 2 − |Vblk | moves to increase |Vblk | by one. Thus, the total number of moves is at 2 least n−3 k=2 (n − 2 − k) = Ω(n ). This lower bound is independent of the algorithm A. It remains to show that the strategy preserves ∞-interval connectivity. Let w1 , w2 , . . . , wn−4 be the nodes added to Vblk in this order, and let x and y be the remaining two nodes in V \ Vblk . We define a spanning tree T∩ = (VT , ET ), where ET = {{u, w1 }} ∪ {{v, w1 }} ∪ {{wi , wi+1 } | i ∈ [1..n − 5]} ∪ {{wn−4 , x}} ∪ {{wn−4 , y}}. Throughout the above strategy, every edge of this tree is present. Hence, ∞-interval connectivity is preserved. Then, we prove Theorem 3, which states that ψk (n, m) = Ω(m) for any k ∈ {0, 1}. Proof of Theorem 3. We prove that, for any sufficiently large n and any m ∈ [n.. n2 ], there exists an underlying graph G = (V, E) with n nodes and m edges such that the adversary can prevent the agent from visiting all nodes while preserving c′ m-interval connectivity for some constant c′ . We n prove this by considering two cases: 2n ≤ m ≤ 2 and n ≤ m < 2n. p First, consider the case 2n ≤ m ≤ n2 . Let g = ⌊ m/8⌋. We define G0 = (V, E0 ) as the graph obtained by merging two copies of the gadget, K 1 = Kg (u1 , v1 ) and K 2 = Kg (u2 , v2 ), a path graph Pn−2g−3 = ({p1 , p2 , . . . , pn−2g−3 }, {{pi , pi+1 } | i ∈ [1..n − 2g − 4]}), and three nodes x, y, and z, connecting them with the following edges (see Figure 2): {u1 , x}, {x, y}, {y, z}, {z, u2 }, {v1 , v2 }, and {x, p1 }. (Note that 2g + 3 ≤ n/2 + 3 < n for sufficiently large n.) Clearly, |V | = n. However, g m + n < m, |E0 | = 2 − 1 + n − 2g − 4 + 6 < g 2 + n < 2 2 for sufficiently large n. Therefore, to match the desired number of edges in G, we add m − |E0 | null edges to G0 to obtain G, where a null edge is an edge that is never present when the agent visits its endpoints and is therefore never available to the agent. As in the proof of Lemma 9, it suffices to describe an adaptive adversarial strategy that determines, at each time t, which edges are present based on ν(t), thereby preventing the agent from visiting all nodes while preserving T -interval connectivity, where T = c′ m for a sufficiently small constant c′ . 12
The adversary maintains a variable next ∈ {1, 2} such that next = i indicates that no edge of K i has been deleted during the past T time steps. Thus, by Lemma 9, once the agent visits any trap node of K next , the adversary can confine the agent within K next for the next T = c′ m ≤ 2c′ (g + 1)2 time steps while preserving T -interval connectivity. (Note that c′ can be an arbitrarily small constant.) Initially, next = 1. The goal of the adversary is to prevent the agent from visiting y. We may choose any node other than y as the initial location ν(0). Whenever the agent visits a trap node in K next , the adversary confines it within K next for T time steps. During this period, it does not delete any (non-null) edge outside K next , in particular, any edge of K 3−next . Thus, it can safely switch the value of next to 3 − next after the confinement period ends. In addition, the adversary deletes the edge {x, y} (resp. {y, z}) at time t if and only if ν(t) = x (resp. ν(t) = z), so the agent can never visit y. This rule would violate T -interval connectivity if the agent visits both x and z within T time steps, thereby isolating y. However, this does not occur, because whenever the agent moves from x to z or from z to x, it must visit a trap node in K next , regardless of whether next = 1 or next = 2, and hence requires at least T time steps to reach the destination. (Note that {u1 , v1 }, {u2 , v2 } ∈ / E0 .) Thus, the agent can never visit y, while T = Ω(m)-interval connectivity is preserved, which completes the proof, in the case m ≥ 2n. Next, we consider the case n ≤ m < 2n, which is much simpler to handle. As an underlying graph, we consider a cycle Cn = ({v0 , v1 , . . . , vn−1 }, {{vi , vi+1 mod n } | i ∈ [0..n − 1]}), adding m − n null edges. We may choose any node other than v1 as ν(0). Then, the adversary can easily prevent the agent from visiting v1 : whenever the agent visits v0 (resp. v2 ), it removes the edge {v0 , v1 } (resp. {v1 , v2 }). This schedule preserves T -interval connectivity for T = n − 3 > m/2 − 3 = Ω(m), since the agent requires n − 2 steps to move from v0 to v2 (resp. from v2 to v0 ), so once {v0 , v1 } (resp. {v1 , v2 }) is deleted, {v1 , v2 } (resp. {v0 , v1 }) remains present for the next n − 3 steps. We can also use the gadget Kn (u, v) to prove Theorem 5, which states that in the KT1 model, every deterministic algorithm requires Ω(m) time to explore every ∞-interval-connected graph with n nodes and m edges. The proof is similar to that of Lemma 9, but more direct. Proof of Theorem 5. If m = O(n), the theorem is trivial, so we consider the case m = ω(n). Given any sufficiently large n and any m = ω(n), we construct an underlying graph G = (V, E) with √ n nodes and m edges. Let g = ⌊ m⌋ < n. We define G0 = (V, E0 ) as the graph obtained by connecting a path graph Pn−g = ({p1 , p2 , . . . , pn−g }, {{pi , pi+1 } | i ∈ [1..n − g − 1]}) and Kg (u, v) with an edge {p1 , u}. Clearly, |V | = n. However, g |E0 | = − 1 + n − g ≤ m/2 − 1 + n = m − ω(n). 2 Therefore, as in the proof of Theorem 3, we add m − |E0 | null edges to G0 to obtain G, which are never present whenever the agent visits their endpoints. Then, by Lemma 9, we can prevent the agent from visiting either gate u or v for Ω(g 2 ) = Ω(m) time while preserving ∞-interval connectivity, provided that the agent starts from a trap node, i.e., ν(0) ∈ / {u, v}. Lastly, we prove Theorem 4, which states that in the KT0 model, every deterministic algorithm requires Ω((m − n + 1)n) time to explore every ∞-interval-connected graph with n nodes and m edges. Proof of Theorem 4. Given any sufficiently large n and any m ∈ [n.. n2 ], we construct an underlying graph G = (V, E) with n nodes and m edges. Let ∆ = m − n + 1, ℓ = ⌊n/3⌋, and r = ⌊2n/3⌋. The node set is V = {v1 , v2 , . . . , vn }. Let VL = {v1 , v2 , . . . , vℓ } and VR = {vr , vr+1 , . . . , vn−1 }. Note that 13
𝑚 % = min(Δ, 𝑉& ⋅ |𝑉' |) trap edges
… 𝑣$
… 𝑉!
𝑣ℓ
…
𝑣!
… 𝑉"
𝑣"
Figure 3: The underlying graph for the proof of Theorem 4, excluding null edges the rightmost node vn does not belong to VR . The underlying graph G has three types of edges: path edges, trap edges, and null edges (Figure 3). The path edges form a path on the n nodes; that is, G contains the edge {vi , vi+1 } for all i ∈ [1..n − 1]. Let mT = min(∆, |VL | · |VR |). We choose any mT trap edges, each connecting a node in VL and a node in VR . If mT < ∆, we add ∆ − mT null edges to ensure |E| = m. As in the proof of Lemma 9, it suffices to describe an adaptive adversarial strategy that determines, at each time t, which edges are present based on ν(t), thereby preventing the agent from visiting all nodes while preserving ∞-interval connectivity. Moreover, whenever the agent located at a node v uses an unused port p ∈ [1..δ(v)] to move, the adversary can decide, in a delayed manner, which unused edge incident to v is associated with p, since we assume the KT0 model and we consider only deterministic algorithms. We describe a simple adversarial strategy. First, as in the proofs of the above lemmas, whenever the agent visits a node v, we delete all null edges incident to v. Next, we never remove any path edge at any time. Therefore, ∞-interval connectivity is preserved regardless of how we delete the trap edges. We choose v1 as the starting node, i.e., ν(0) = v1 , and prevent the agent from visiting vn for Ω(mT · n) = Ω((m − n + 1)n) time steps. Whenever the agent visits a node in VL , we delete all trap edges incident to that node. Therefore, once the agent visits a node in VL , it requires r − ℓ = Ω(n) time to visit any node in VR . Moreover, whenever the agent attempts to traverse an unused edge at a node v ∈ VR (i.e., it chooses an unused port at v), we let the agent traverse an unused trap edge as long as such an edge exists. As a result, for each vi ∈ VR , the agent requires Ω(ki · n) time to visit vi+1 after it Pfirst visits vi , where ki is the number of trap2 edges incident to vi . Therefore, the agent requires i∈[r..n−1] Ω(ki · n) = Ω(mT · n) = Ω(min(∆, n ) · n) = Ω((m − n + 1)n) time to visit vn .
4
Conclusion
In this paper, we studied deterministic single-agent exploration in T -interval-connected graphs under two visibility models, KT0 and KT1 . We focused on two natural questions: the minimum window size that guarantees exploration, and the exploration time achievable once the window size is sufficiently large. We first established upper bounds for both models. In particular, we presented deterministic exploration algorithms whose required window size is O(ϵ(n, m) · m + n log2 n). For the KT0 model, our algorithm explores the graph in O((m − n + 1)n + n log2 n) time, while for the KT1 model, the exploration time is at most the required window size itself. We then proved matching or nearly matching lower bounds. For both KT0 and KT1 , we showed that the minimum required window size is Ω(m). For the exploration time, we proved lower bounds of Ω((m − n + 1)n) in the KT0 model and Ω(m) in the KT1 model. These results yield a nearly complete picture of deterministic single-agent exploration under T interval connectivity. In particular, when m = n1+Θ(1) , our upper and lower bounds on the minimum 14
window size match asymptotically, giving a tight bound Θ(m). Moreover, when parameterized solely by n, our bounds are tight: ψk (n) = Θ(n2 ) for both k ∈ {0, 1}. For the exploration time, our results also imply tight bounds when parameterized only by n, namely Θ(n3 ) for KT0 and Θ(n2 ) for KT1 . Our work leaves several interesting directions for future research. Most notably, it would be interesting to understand how much randomization can help. If randomized algorithms are allowed, how small can the minimum required window size be made, and how much can the exploration time be improved? More broadly, closing the remaining polylogarithmic gap in the general case and clarifying the exact advantage of additional local visibility also remain interesting open problems.
15
A
Supplemental Lemmas
Lemma 10. For any real number x > 0 and n ≥ 3, we have ln n < xn1/(2x) . Proof. For n ≥ 3, let y = ln2xn > 0. Then ln n < xn1/(2x)
⇐⇒
2y < ey .
Define h(y) = ey − 2y. Then h′ (y) = ey − 2, so h attains its minimum on (0, ∞) at y = ln 2, where h(ln 2) = 2 − 2 ln 2 > 0. Hence ey > 2y for all y > 0, proving the claim.
16
References [AHL02]
Noga Alon, Shlomo Hoory, and Nathan Linial. The moore bound for irregular graphs. Graphs and Combinatorics, 18(1):53–57, 2002.
[AKL+ 79]
Romas Aleliunas, Richard M Karp, Richard J Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 218–223. IEEE, 1979.
[AMJ18]
John Augustine and William K Moses Jr. Dispersion of mobile robots: a study of memory-time trade-offs. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1–10, 2018.
[BDP23]
Sébastien Bouchard, Yoann Dieudonné, and Andrzej Pelc. Want to gather? no need to chatter! SIAM Journal on Computing, 52(2):358–411, 2023.
[CFQS12]
Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Timevarying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012.
[DDFS16]
Giuseppe Antonio Di Luna, Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Live exploration of dynamic rings. In 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS), pages 570–579. IEEE, 2016.
[DLFP+ 20] Giuseppe Antonio Di Luna, Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Gathering in dynamic rings. Theoretical Computer Science, 811:79–98, 2020. [DPP14]
Yoann Dieudonné, Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Transactions on Algorithms (TALG), 11(1):1–28, 2014.
[EHK21]
Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1–18, 2021.
[FMS13]
Paola Flocchini, Bernard Mans, and Nicola Santoro. On the exploration of time-varying networks. Theoretical Computer Science, 469:53–68, 2013.
[FS13]
Zoltán Füredi and Miklós Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erdős centennial, pages 169–264. Springer, 2013.
[GFMS21] Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Exploration of dynamic networks: tight bounds on the number of agents. Journal of Computer and System Sciences, 122:1–18, 2021. [GSO+ 21]
Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Exploration of dynamic tori by multiple agents. Theoretical Computer Science, 850:202–220, 2021.
[GSOM20] Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, and Toshimitsu Masuzawa. Dynamic ring exploration with (H, S) view. Algorithms, 13(6):141, 2020.
17
[IKW14]
David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade. Exploration of constantly connected dynamic graphs based on cactuses. In International Colloquium on Structural Information and Communication Complexity, pages 250–262. Springer, 2014.
[IW18]
David Ilcinkas and Ahmed M Wade. Exploration of the T -interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems, 62(5):1144–1160, 2018.
[KKM+ 25] Ajay D Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, and Gokarna Sharma. Dispersion is (almost) optimal under (a) synchrony. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, pages 367–381, 2025. [KLO10]
Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 513–522. ACM, 2010.
[Kou02]
Michal Kouckỳ. Universal traversal sequences with backtracking. Journal of Computer and System Sciences, 65(4):717–726, 2002.
[KS25]
Ajay D Kshemkalyani and Gokarna Sharma. Near-optimal dispersion on arbitrary anonymous graphs. Journal of Computer and System Sciences, page 103656, 2025.
[Mic16]
Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics, 12(4):239–280, 2016.
[MS16]
Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1–23, 2016.
[MT10]
Toshimitsu Masuzawa and Sébastien Tixeuil. Quiescence of self-stabilizing gossiping among mobile agents in graphs. Theoretical Computer Science, 411(14-15):1567–1582, 2010.
[PDDK96] Vyatcheslav B Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Physical Review Letters, 77(25):5079, 1996. [Pel12]
Andrzej Pelc. Deterministic rendezvous in networks: A comprehensive survey. Networks, 59(3):331–347, 2012.
[PP99]
P. Panaite and A. Pelc. Exploring unknown undirected graphs. Journal of Algorithms, 33(2):281–295, 1999.
[PP24]
Debasish Pattanayak and Andrzej Pelc. Deterministic treasure hunt and rendezvous in arbitrary connected graphs. Information Processing Letters, 185:106455, 2024.
[Rei08]
O. Reingold. Undirected connectivity in log-space. Journal of the ACM (JACM), 55(4):1–24, 2008.
[SBN+ 15]
Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. A single agent exploration in unknown undirected graphs with whiteboards. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 98(10):2117–2128, 2015. 18
[SKE+ 23]
Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial gathering of mobile agents in dynamic tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023), pages 2–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023.
[SKS+ 20]
Masahiro Shibata, Norikazu Kawata, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings. Theoretical Computer Science, 822:92–109, 2020.
[SOK25]
Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Self-stabilizing graph exploration by a single agent. In International Colloquium on Structural Information and Communication Complexity, pages 384–400. Springer, 2025.
[SSKM20]
Takahiro Shintaku, Yuichi Sudo, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Efficient dispersion of mobile agents without global knowledge. In Stabilization, Safety, and Security of Distributed Systems: 22nd International Symposium, SSS 2020, Austin, TX, USA, November 18–21, 2020, Proceedings 22, pages 280–294. Springer, 2020.
[SSN+ 24]
Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Near-linear time dispersion of mobile agents. In 38th International Symposium on Distributed Computing, 2024.
[TSZ14]
Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms (TALG), 10(3):1– 15, 2014.
[Xin07]
Qin Xin. Faster treasure hunt and better strongly universal exploration sequences. In International Symposium on Algorithms and Computation, pages 549–560. Springer, 2007.
[YWB03]
Vladimir Yanovski, Israel A Wagner, and Alfred M Bruckstein. A distributed ant algorithm for efficiently patrolling a network. Algorithmica, 37(3):165–186, 2003.
19