Online Treasure Hunt in Vertex-Permuted Dynamic Rings Kamran Ayoubi1[0009−0008−7768−8639] , Bernard Mans2[0000−0001−7897−2043] , and Lata Narayanan1[0000−0002−3875−0371]
arXiv:2609.11013v1 [cs.DC] 10 Sep 2026
1
Department of Computer Science and Software Engineering, Concordia University, Montreal, Canada [email protected], [email protected] 2 School of Computing, Macquarie University, Sydney, Australia [email protected]
Abstract. We study the problem of treasure hunt by a group of k ≥ 1 agents in vertex-permuted dynamic rings (VP). In this model, the n vertices remain on a ring but are permuted at each time step. We first show that treasure hunt is impossible for any k ≤ n − 3 agents, if there are no restrictions on the sequence of permutations used in the dynamic ring. We then study the VP(δ) setting, in which for every pair i, j of vertices, the edge (i, j) is guaranteed to appear within δ steps. We show that the class VP(δ) is feasible only for δ ≥ n−1 . For the 2 one-agent case, we show a tight bound of Θ(δn) on the worst-case search time as well as competitive ratio of any online algorithm for treasure hunt, provided δ ≥ 2n. We then give an optimal algorithm for k agents, thereby showing that k agents can obtain a speedup of k on the worstcase search time. Finally, in the R-VP setting, in which in every step, the vertices are arranged as a ring according to a random permutation, we show that treasure hunt takes expected Θ(n) steps against an oblivious adversary and Θ(n log n) steps against an adaptive adversary. Keywords: Online treasure hunt · vertex-permuted rings · temporal graphs.
1
Introduction
Modern networks are dynamic rather than static, with links between entities changing over time. These networks are ubiquitous and occur in critical settings, such as wireless and mobile networks, transportation networks, sensor networks, and systems where nodes or links can fail or be turned off. Moreover, changes can be arbitrary, making it challenging to design algorithms for such networks. In this paper we study the problem of treasure hunt or search by a group of agents in a dynamic ring network. There is a special vertex T (the treasure), and k ≥ 1 mobile agents located at potentially different vertices of the n-node ring start looking for the treasure at the same time. Agents are identical, anonymous, memoryless, and operate synchronously and online: at each time step t they
2
K. Ayoubi et al.
observe their neighbors in the current graph Gt , and then decide whether to move to a neighboring vertex or to stay, without any knowledge of future graphs, or memory of past actions. Their collective goal is to minimize the time that the first agent reaches the treasure. We focus on vertex-permuted rings (VP), a dynamic ring in which, in every time step, the vertex set is permuted and then arranged in a ring topology [1, 5]. A vertex-permuted graph is a temporal graph in which the structure of the graph remains fixed at each time step throughout the graph’s lifetime, though the vertices may assume different positions in the graph. For example, cyclists who ride in pelotons, swap their positions after specific time intervals as it is more tiring to be in front of the formation. In the natural world, it has been observed that birds flying in formation or fish swimming in formation swap positions while maintaining the same structure of the formation. In the context of sensor networks that have clusters configured in a star topology, different nodes periodically assume the role of clusterhead, in order to balance energy consumption across cluster members. All the above are examples of vertex-permuted graphs. We show that treasure hunt is impossible in a vertex-permuted ring if there is no restriction on the dynamicity. In view of this impossibility, we consider restrictions on the dynamicity. We consider the class VP(δ): for every ordered pair (u, v) with u ̸= v, and every starting time t, the vertices u and v appear as neighbors in some step s ∈ {t, t + 1, . . . , t + δ − 1}. Finally, we consider a random version of VP. In R-VP, in every step, a random permutation of the vertices is arranged as a ring.
1.1
Overview of results
We first show that for any k with 1 ≤ k ≤ n − 3 and for every randomized or deterministic online algorithm, there are inputs on which no agent can ever reach the treasure. For VP(δ), using an interesting connection to the Walecki decomposition of a clique into Hamiltonian cycles [2, 21], we first note that the class is non-empty if and only if δ ≥ ⌈(n − 1)/2⌉. Next we show a tight bound of Θ(δn) on the search time and on the competitive ratio for a single deterministic agent in VP(δ) for δ ≥ 2n, provided agents have the ability to flag a node when they visit it, and subsequently, agents at neighboring nodes can see the flag. In contrast, if agents do not have the ability to flag nodes, we show that no deterministic singleagent algorithm can solve treasure hunt in VP(δ). We then give a randomized algorithm that can find the treasure in expected O(δ 2 ) time. For k agents, we show a lower bound of (⌈(n − 2)/k⌉ − 2) δ, provided δ ≥ (k + 1)(n − k − 2) on the time any agent can reach the treasure; we give an algorithm that matches this bound asymptotically. For upper bounds, we assume that agents are anonymous and memoryless, have the ability to flag, and can see flags at distance one, but do not have chirality and do not know any node labels. Our matching lower bounds hold
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
3
even if we assume agents have memory, chirality, full knowledge of node labels and visibility of the entire graph. To our knowledge, the idea of allowing agents to plant flags at visited nodes that can be seen subsequently at distance one is novel. We note that flags constitute a compact (one-bit) but powerful form of persistent memory that obviates the need for agents to know or remember identities of nodes they have visited, and to find out about nodes that other agents have visited either by sending/receiving messages, or via an increased visibility range. In R-VP, using an equivalence with random walks in cliques, we show that the expected time for an agent to reach the treasure is Θ(n) for an oblivious adversary and it iΘ(n log n) for an adaptive adversary who knows the input sequence of random graphs. 1.2
Organization
Section 2 discusses related work, and Section 3 defines the model and the problem. Section 4 proves impossibility in unrestricted vertex-permuted rings. Section 5 studies the single-agent case in V P (δ) and R-VP. Finally, Section 6 studies the multiple-agent case in V P (δ).
2
Related work
Temporal graphs (also called time-varying or dynamic or evolving graphs) model networks whose edges change over time, see, e.g., the TVG survey of Casteigts et al. [10] and the distributed-computing model of Kuhn, Lynch, and Oshman, who introduced T -interval connectivity [10, 20]. Dynamic rings in particular have been studied for example, for the problem of gathering and dispersion [1, 14] and exploration [24, 13, 19, 22]. Vertex permutation dynamism is a temporal model in which every snapshot is isomorphic to a fixed base graph, obtained by permuting vertex identities between steps. Vertex permuted rings were introduced in [1], which studied the problem of dispersion in such graphs. In [5], the authors study restless exploration in vertex-permuted temporal graphs of arbitrary topology and show a precise characterization of the base graphs for which restless exploration is always possible. The concept of exploration by restless agents (agents who must move to a neighboring node in every step) was introduced in [7]. Search or treasure hunt has been studied in many settings, including continuous domains (e.g., the cow-path problem, first studied in [6]) and discrete graphs [4, 9]. More recently, multi-agent search has been studied, under different models of communication between the agents, different speeds of agents, various fault models, and so on. Search in a graph [4, 9, 26] is similar to graph exploration; in the former, agents are looking for a specific node or object in the graph, while the goal of exploration is to visit every node in the graph. The exploration of temporal graphs, introduced by Michail and Spirakis [25], and studied in [17] addresses
4
K. Ayoubi et al.
the problem of designing temporal walks that visit all vertices of a dynamic graph. Most work on exploration in temporal graphs is offline, where the entire sequence of graphs is known before designing the trajectory of agents. There is relatively little work on online exploration in dynamic graphs. In [13] and [24], online exploration of 1-interval connected dynamic rings was studied. However, this is a very different model of dynamicity than ours. Tokens or pebbles are a common way to strengthen the extremely limited capacity of the agents for exploration tasks, by allowing a small amount of persistent state in the environment [16]. Generally speaking, agents can place pebbles at a node, and are only visible to agents when they are actually at the node. Pebbles were used in the context of treasure hunt in [18, 15, 12]. The flags that we use in our paper are similar to pebbles, but differ in that we assume the flag that can be planted by an agent when visiting a node is visible to agents at neighboring nodes in all subsequent steps. They also differ from the model of mobile agents with lights [11] in which it is the robots that are equipped with lights that enable some communication with other robots, whereas flags are left behind by robots at nodes. When the dynamics are random rather than adversarial, agent trajectories are often analyzed using random-walk tools (hitting times, cover times) on temporal graphs. A representative example is Avin, Koucký, and Lotker, who relate the evolution rate of the graph to cover-time behavior [3].
3
Model
Dynamic graph model. For our purposes, a dynamic graph or a temporal graph is a sequence of graphs G0 = (V, E0 ), G1 = (V, E1 ), G2 = (V, E2 ), . . . , GL = (V, EL ), where each Gi = (V, Ei ) is a static undirected graph, and all Gi have the same vertex set V , but possibly different edge sets. The number L is called the lifetime of the temporal graph. Each graph Gi corresponds to the state of the temporal graph at time step i, with an edge e ∈ Ei representing a connection between two vertices that is available at time i. The sequence of graphs models the evolution of a network over time [17]. In this paper, we study vertex-permuted rings (VP) with n nodes in which each snapshot Gt is a cycle on V , obtained by an arbitrary permutation of the nodes arranged as a ring. Nodes are anonymous, that is, they may have labels, but they are unknown to the agents. In each time step t, in the graph Gt , every node v is connected to its two neighbors in the ring via distinctly labelled ports; the labelling of the ports is arbitrary and may not provide a globally consistent orientation. For δ ∈ N, the class VP(δ) consists of all dynamic graphs in VP in which, for every pair {u, v} with u ̸= v and every starting time t = iδ + 1 for i ∈ N there exists s ∈ {t, t + 1, . . . , t + δ − 1} such that u and v are adjacent in Gs . Equivalently, every vertex sees every other vertex as a neighbor at least once in every window of length δ. A dynamic graph in VP(δ) does not need to be a periodic graph with period δ. So a graph in VP(δ) does not guarantee adjacencies
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
5
with all other vertices in a sliding window of length δ. However, it is easy to see that for every graph in VP(δ), adjacencies are guaranteed with all other vertices in a sliding window of length 2δ. Thus, in the rest of the paper, we do not talk about sliding windows, and instead when speaking of VP(δ), consider a graph where starting at time 1, time is divided into windows of δ steps, and in each window, each vertex is guaranteed to be adjacent to every other vertex in at least one step during the window. Agents and actions. There are k ≥ 1 agents. Agents are identical and anonmyous: they do not have identities and execute the same algorithm. Agents are memoryless in the sense that they do not remember actions or information from the past in the current step. One of the nodes of the graph contains a treasure; we assume this treasure can only be seen when an agent is located at the same node as the treasure. To find the treasure, agents have to visit the nodes of the graph. In the k ≥ 2 case, agents work in synchronous discrete time steps, using the well-known LookCompute-Move model [13]. We consider two models of visibility and what an agent can do when it visits a node. In the first model, when an agent visits a node, it is able to mark it as visited by planting a flag there (we say the agent flags the node), which is visible to any agent at a neighboring node. A node that has not been visited by any agent remains unflagged. Note that agents have no visibility about nodes at a distance more than one in any step. In the second model, an agent cannot plant a flag, and cannot distinguish between nodes that were previously visited from nodes that have never been visited, even when those nodes are adjacent. Agents are silent - they do not communicate with agents at other nodes by sending messages. Planting flags to mark nodes as visited can be seen as a form of indirect communication between agents. There is no other communication between agents. Each agent has a consistent private orientation of the ring, which designates each port as cw or ccw. As in [14], access to the ports is by mutual exclusion: if multiple agents request the same port, exactly only of them succeeds. Requests to the two ports are arbitrated independently. Our lower bounds are valid for stronger models of agents; the specific ways in which agents can be strengthened are mentioned in the theorem statements. The treasure hunt problem. An instance of the treasure hunt problem is a dynamic graph G0 , G1 , . . . , GL , a set of k ≥ 1 agents located at the same vertex in G0 , and a treasure located at a fixed vertex T unknown to the agents. Each agent chooses its action at time t based only on what it sees in its neighborhood at time t and without any knowledge of Gt+1 to GL . Given an instance of the treasure hunt problem, the goal is to minimize τ1k , the first time any agent of k agents reaches T . We are also interested in analyzing the competitive ratio of our online algorithms. The competitive ratio of an online algorithm ALG is the worst-case ratio (over all possible input sequences G1 , . . . , GL ) of the cost of ALG to the cost of an optimal offline algorithm that knows the entire input sequence in advance.
6
K. Ayoubi et al.
Fig. 1. Illustration of the adversarial procedure TrapIn-(3) on a vertex-permuted ring. The dark vertex is the agent’s current position; the other two shown vertices are its neighbors in the current snapshot.
Although we describe our lower bound arguments in the classic request-answer game framework, where the adversary chooses the next graph Gt based on the actions of the agent so far, it is known that the lower bound also holds against an oblivious adversary for deterministic algorithms, and against an adaptive offline adversary for randomized algorithms [8].
4
Treasure hunt in unrestricted VP
In this section, we show that treasure hunt is impossible for any number of agents in VP when there are no restrictions on the permutations in every step. An adversarial scheduler can confine the agent to at most three nodes by using the following TrapIn-(3) procedure. Suppose the agent is at a node u whose neighbors are v and w in Gt . The graph Gt+1 chosen by the adversary depends on the agent’s action in step t. If the agent stays in u, then Gt+1 = Gt . If the agent moves to v, then in Gt+1 the adversary swaps the positions of v and u, so that v is now in the middle. Similarly, if it moves to w, the adversary swaps the positions of u and w so that w is in the middle. In this way, the agent can never visit any nodes except for u, v, and w. Figure 1 gives a concrete example of TrapIn-(3) with {u, v, w} = {0, 1, 2}. Theorem 1. For any randomized or deterministic algorithm with k agents starting at the same node, where 1 ≤ k ≤ n − 3, treasure hunt is impossible, even if agents have memory, chirality, full visibility of the graph, and know the node labels. Proof. For one agent, the TrapIn-(3) procedure foils any deterministic or randomized agent from reaching the treasure. The TrapIn-(3) procedure can be generalized to any k ≤ n − 3 agents; we call the procedure TrapIn-(k + 2) (see Figure 2). Given an online algorithm for treasure hunt, the adversary keeps presenting the same permutation until a time t when the k agents are spread k + 2
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
7
Fig. 2. Illustration of the adversarial procedure TrapIn-(k + 2) for k agents in a vertexpermuted ring. Stars denote agents. The adversary keeps all agents inside a contiguous block A of k+2 vertices; whenever an agent reaches a boundary vertex of A, it swaps that boundary with a free vertex of A in the next snapshot, restoring confinement. In Gt , at = 0 and bt = 6
apart. Let at be the farthest node from 0 going clockwise that contains an agent and let bt be the farthest such node going counterclockwise, and let A be the set of k + 2 nodes between at and bt . There is at least one node in the ring that is not in A; the adversary places the treasure in such a node. Also, there must be two nodes ct , dt ∈ A that are not occupied by any agents. In time t + 1, the adversary exchanges the positions of ct and dt with at and bt respectively. The agents are now in the “interior” nodes of A and cannot reach the treasure in step t + 1. In every subsequent step, as long as the agents stay within the interior nodes of A, the adversary does not change the permutation. If an agent moves to a “boundary” node, the adversary swaps the position of the agent-containing boundary node with an interior node that does not have an agent in the next step. Thus the agents are trapped in the set A of nodes and can never reach the treasure; knowing and remembering labels of nodes, chirality, and having complete visibility does not help. It is straightforward to see that a similar procedure can be employed even if k agents do not start at the same node, provided that n is large enough compared to k, by trapping subsets of agents in separate sets of nodes; we omit the details.
5
Treasure hunt by a single agent in restricted models of VP
In light of the impossibility of treasure hunt in unrestricted VP, we consider restricted versions of VP in this section, namely VP(δ) and R-VP.
8
K. Ayoubi et al.
5.1
The VP(δ) model
We first identify the minimum value of δ for which the class VP(δ) is non-empty. For valid values of δ, we give a single-agent algorithm for the model when agents can flag vertices when visiting them, and then prove a matching lower bound. For the model with no flags, we show that on the one hand, no deterministic agent can perform treasure hunt, and on the other hand, there exists a randomized algorithm that completes treasure hunt in expected O(δ 2 ) time. Feasibility threshold for VP(δ) on a ring We start by considering for which values of δ the class VP(δ) is non-empty. m l . Proposition 1. VP(δ) is non-empty if and only if δ ≥ n−1 2 Proof. Fix a vertex u. In any δ-window, u has exactly 2δ (ordered) neighbor “slots.” To see all n − 1 other vertices at least once as a neighbor in the window, we need 2δ ≥ n − 1 i.e., the stated lower bound. For odd n, a Walecki decomposition [2, 21] of an n-vertex clique gives (n − 1)/2 edge-disjoint Hamilton cycles whose union covers all edges in the clique. Each of these Hamilton cycles is a vertex-permuted ring. The sequence of all cycles in the decomposition constitutes a sequence of rings in which every node sees every other node as a neighbor. Repeating this sequence ensures VP(δ) with δ = (n − 1)/2. For even n, a standard modification (Hamilton cycles plus antipodal pairs folded into a cycle) yields δ = n/2. Hence the bound is tight.
Fig. 3. Example of a Walecki-style decomposition for n = 9 shown as four consecutive vertex-permuted rings (since (9 − 1)/2 = 4). Tracking the highlighted vertex 1 across the four rings, it becomes adjacent to all other vertices within a window of 4 steps.
Example (n = 9). Figure 3 illustrates the construction for δ = n−1 2 when n is odd, using the standard “rotation” view of Walecki’s decomposition. Here, vertex 8 is kept fixed as a center vertex, and the remaining vertices are arranged on a cycle. Each subsequent Hamiltonian cycle is obtained by rotating the outer vertices by one position (counterclockwise in the figure) while keeping the center vertex fixed; this produces the (n−1)/2 = 4 edge-disjoint Hamilton cycles whose union is K9 .
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
9
In these four consecutive rings, the highlighted vertex 1 has neighbors {8, 0} in step 1, {6, 7} in step 2, {5, 4} in step 3, and {2, 3} in step 4. Thus, within δ = 4 steps, vertex 1 is adjacent to every other vertex. By symmetry, the same holds for every vertex, and by repeating this sequence, we obtain a dynamic ring in VP(4). Upper bound for one agent Consider Algorithm Move-to-Unflagged for a single agent: Until the treasure is found, in every step, if either of the neighbors is unflagged, then move to it (pick an arbitrary one if both neighbors are unflagged), otherwise wait. Theorem 2. Algorithm Move-to-Unflagged solves the treasure hunt problem in at most δ(n − 1) steps. Proof. First, observe that the agent never has to wait longer than δ steps to see an unflagged vertex as a neighbor, and every time it moves, it flags a new node. It follows that it completes the search within δ(n − 1) steps. Lower bound for one agent We show that for any online deterministic algorithm, the adversary can construct an input such that the algorithm takes Θ(δn) steps, provided δ ≥ 2n, thus showing that the simple Move-to-Unflagged algorithm above is optimal for this range of δ. The adversary waits until 3 vertices have been visited and flagged. Without loss of generality, let these be vertices {0, 1, 2}. We call these the interior vertices, and assume that they have been visited at time step 0. All other vertices {3, . . . , n − 1} are the exterior vertices, which are as yet unflagged. Time is divided into periods of length δ = 2n: the r-th period is rδ, rδ + 1, . . . , (r + 1)δ − 1. For convenience, we speak of three phases inside a period. The first two phases use at most ⌈n/2⌉ time steps, and the three phases making up a period together use at most 2n time steps. The following lemma presents the properties of the input in a period. Lemma 1. In every period of length 2n, the adversary can present a sequence of vertex-permuted rings in which (i) every pair of vertices is adjacent at least once, and (ii) the agent can visit and flag at most one new vertex, even if it has memory, full visibility and knowledge of node labels. Proof. Let m = n − 3 be the number of exterior vertices. In every step but one in the period, the adversary uses the TrapIn-(3) procedure to keep the agent in the middle node of the three interior vertices. The other two interior vertices are called the two boundary interiors. The adversary chooses exactly one time step in the period to offer an unflagged vertex v as a neighbor of the agent; if the agent moves to v, the adversary puts v (and the agent) between two visited interiors in the next time step, and does not offer a second unflagged vertex as a neighbor in the same period. The challenge for the adversary is to do this while
10
K. Ayoubi et al.
making sure that all vertex pairs are adjacent at least once during the period, thus guaranteeing that the graph is in VP(δ). Phase 1 (⌊n/2⌋ − 1 time steps). Treat the three interior vertices as a single mega vertex Vm and form a ring on n − 2 vertices (Vm plus the m exterior vertices), and use a Walecki construction to create vertex-permuted rings of n − 2 vertices for the next ⌈(n − 3)/2⌉ = ⌊n/2⌋ − 1 time steps. Notice that every exterior vertex will be adjacent to every other exterior vertex at least once. In the same time, in each time step Vm is adjacent to two new exterior vertices. We now describe the adaptive part of the adversary’s strategy. In each such ring of size n − 2, we expand the vertex Vm , and respond to the agent’s actions in the vertices that constituted Vm by the TrapIn-(3) procedure. Observe that adjacencies between Vm and the exterior vertices are split across the three interior vertices so that no interior vertex meets more than ⌈(n − 3)/2⌉ distinct exteriors by the end of phase 1. Thus by the end of phase 1 we have: (a) all exterior–exterior pairs of vertices have been adjacent; and (b) at least (n − 3) distinct interior–exterior pairs have been adjacent, with no interior vertex being adjacent to more than half of the exterior vertices. Phase 2 (⌊n/2⌋ − 1 steps). In this phase, the adversary continues to use the TrapIn-(3) procedure (Figure 1) to keep the agent in the middle of the three interior vertices. However, in each time step, we ensure that each boundary interior vertex is adjacent to a new exterior vertex that it did not see in Phase 1. This is possible since no interior vertex has been adjacent to more than (n − 3)/2 exterior vertices in Phase 1. The other adjacencies between exterior vertices are arbitrarily chosen. After ⌈n − 3/2⌉ = ⌊n/2⌋ − 1 time steps, (at least) another n − 3 interior–exterior pairs have been adjacent. Phase 3 (at most n − 3 time steps). There are 3(n − 3) pairs of interior-exterior vertices in all. After Phase 2, all but (n − 3) of these pairs have already been adjacent during the current period. In Phase 3, in each step, to build the permutation, we first move the agent to the middle of the three interior vertices. Call this middle vertex v, and let u and w be the boundary interior vertices. If one of u and w still has not been adjacent to some exterior vertex, then we provide that adjacency (or those adjacencies) now and build the rest of the permutation in an arbitrary way. If both u and w have already been adjacent to all exterior vertices, all missing exterior-interior adjacencies are with the node v, where the agent is located. So in the new permutation, we swap the positions of u and v, making v a boundary interior, then make v adjacent to one of those (possibly unflagged) exterior vertices x, swapping the positions of u and x. This provides the only chance for the agent to visit an unflagged vertex in this period. If the agent does not move to x, we repeat the procedure described here, creating a new adjacency with v and a new exterior vertex. If the agent does move to x, we now put x in between u and w (that is, x is now an interior vertex), and put v in the ring at a position one away from u, and in each subsequent step, (a) create two of the remaining adjacencies between v and exterior vertices; (b) use TrapIn-(3) to keep the agent in the middle vertex among u, w, x; (c) arbitrarily create the rest of the permutation. When this process completes, all vertices
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
11
have been adjacent to all other vertices, and at most one vertex has been flagged in the period. The total number of steps in all three phases, that is, the length of the period is 4⌊n/2⌋ − 4 < 2n. Theorem 3. For any deterministic online algorithm, there is an input in V P (δ) for δ ≥ 2n such that treasure hunt takes at least δ(n − 3) steps, that is, τ11 ≥ δ(n − 3), even for agents with chirality, memory, full visibility and knowledge of node labels. Proof. We start with 3 visited/flagged vertices {0, 1, 2}. By Lemma 1, each period covers all pairs and adds at most one new flagged vertex. Note that the set of 3 interior vertices can change between phases; interior vertices are always flagged, and some subset of the exterior vertices of size at most i are flagged after the ith period. Placing the treasure at the last unflagged vertex to be reached ensures that (n − 3) periods are needed. Each period has length δ. Therefore the total time needed is δ(n − 3). As a consequence of Theorems 2 and 3, we have: Corollary 1. Algorithm Move-to-Unflagged , in which agents do not have chirality, memory, or knowledge of node labels, and can only see flags at neighboring nodes, is asymptotically optimal in terms of both worst-case search time for VP(δ) with δ ≥ 2n, even considering agents with chirality, memory, full visibility, and knowledge of node labels. Theorem 4. The competitive ratio of any deterministic online agent with chirality, memory, and full visibility, but without knowledge of node labels, is Ω(δn). Proof. To see that the competitive ratio of any deterministic online agent is Ω(δn), we claim that on the input described in the proof of Lemma 1, it is possible for an optimal offline algorithm to reach the treasure in a single step. Recall that in the construction of the bad input for the online agent, we assume that the first three vertices visited by the agent were 0, 1, and 2. If the treasure was at n − 1, then the optimal offline algorithm could reach it in one step, while the adversary can ensure that vertex n − 1 is the very last node visited by the online agent. Agents that cannot flag visited vertices In the VP(δ) model we have considered so far, agents can distinguish between vertices that have already been visited and those that have not been visited, by using flags. We now consider the setting without flags. In this setting, an agent can still observe its current neighbors and choose whether to move or stay, but it cannot tell whether a neighboring vertex has been visited before. We first show that without flags, no deterministic single-agent algorithm can solve treasure hunt. In contrast, we give a randomized algorithm that can solve the problem in expected O(δ 2 ) time, by choosing to wait with a positive probability in every step.
12
K. Ayoubi et al.
Theorem 5. For δ ≥ n, no deterministic single-agent algorithm can solve treasure hunt in V P (δ) without flags, even for agents with memory, chirality, and full visibility, but no knowledge of node labels. Proof. Consider an arbitrary deterministic algorithm for a single agent without flags. We allow the agent to have memory, but the vertices are anonymous, as far as the agents are concerned. In this case, any deterministic algorithm can be specified as a sequence (i, di ) with di ∈ {−1, 0, 1}, where −1, 0, 1 respectively stand for move counterclockwise, stay, and move clockwise. The adversary knows this sequence; we give a strategy for the adversary for a window of length δ ≥ n. The adversary keeps the agent confined to two vertices u and v. The treasure is placed at an arbitrary vertex outside {u, v}. We treat the pair of vertices u, v as a mega-vertex V adversary uses m ; the time steps. This a Walecki construction on a graph of n − 1 vertices in n−2 2 ensures that all vertices except u and v are adjacent to each other in some step, and also, adjacent to Vm in some step. Now we describe what happens inside Vm during these steps. Suppose after step i − 1, the agent is at u. Then if di = 0, in the graph Gi , the adversary keeps the relative positions of u and v the same as in the previous step; if di = 1, the adversary makes v the clockwise neighbor of u; and if di = −1, the adversary makes v the counterclockwise neighbor of u. An identical strategy is used if the agent is in v after step i − 1, exchanging the roles of u and v. In this way, the adversary ensures that if the agent moves in step i, it can only move from u to v or from v to u. At the same time, the permutation built by the Walecki construction ensures that in every step, at least ⌊ n−2 2 ⌋ of the remaining n − 2 vertices have been adjacent to u (but not to v) and the remaining have been adjacent to v (but not to u). In the next ⌈ n−2 2 ⌉ steps, the adversary creates these missing adjacencies for u and v, while using an identical strategy as in the first ⌈ n−2 2 ⌉ steps to keep the agent in the vertices u and v. The adjacencies between the n − 2 vertices other than u and v can be arbitrarily set. ≤ n steps, every pair of vertices has appeared Therefore, in at most 2 n−2 2 as an edge at least once. Repeating this construction in every window gives a dynamic graph in VP(δ) for every δ ≥ n. However, throughout the whole execution the agent visits only the two vertices u and v. The agent’s memory may affect the sequence of actions di , but it does not allow the agent to distinguish u and v from previously unseen anonymous vertices. Since the treasure is placed outside {u, v}, the agent never finds the treasure. Hence, no deterministic online algorithm can solve treasure hunt in VP(δ) without flags, even if the agent has memory. In Theorem 5, the adversary uses its advance knowledge of the agent’s deterministic choices in every step to keep the agent trapped between two vertices and still create a graph in VP(δ). However, for a randomized algorithm, since the adversary does not know the agent’s random choices in advance, it is possible to succeed in finding the treasure. Consider the following simple randomized algorithm. At each time step, the agent stays at its current vertex with probability
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
13
Ps . Otherwise, it moves to one of its two neighbors, choosing the clockwise and counterclockwise neighbor with equal probabilities Pℓ = Pr = 12 (1 − Ps ). By choosing the right value of Ps , we obtain the following result: Theorem 6. There is a randomized algorithm for treasure hunt by one agent in V P (δ) with δ ∈ Ω(n), which achieves E[τ11 ] = O(δ 2 ). Proof. Consider a particular window of δ steps. Let u be the location of the agent at the first time step of the window, and let T be the location of the treasure. We first find the probability that the agent reaches the treasure within the window of δ time steps. Since the input is in VP(δ), the edge (u, T ) must appear in this window. Let t∗ be the step chosen by the adversary to present the edge (u, T ). The agent reaches T at time t∗ if it (a) remains at u for the first t∗ − 1 steps and (b) moves at step t∗ toward T . Let pwin (Ps ) denote the probability that the agent reaches T in a time window of δ steps. Then ∗
pwin (Ps ) ≥ (Ps )t −1
(1 − Ps ) (1 − Ps ) ≥ (Ps )δ−1 > 0. 2 2
This bound is robust against an adaptive offline adversary: the adversary chooses t∗ , but cannot make the probability above vanish when 0 < Ps < 1. The lower bound on the probability is maximized when Ps = (δ − 1)/δ. δ−1 Substitute into the lower bound on pwin (Ps ) and use 1 − 1δ → e−1 , we obtain 1 1 1 δ−1 1 p∗win ≥ ≈ . 1− · 2 δ δ 2e δ Consequently, the expected number of windows to reach the treasure is at most 1/p∗win , and the expected number of steps satisfies E[τ11 ] ≤
δ ≤ 2e δ 2 . p∗win
Theorem 6 shows that treasure hunt can be solved in expected O(n2 ) time in a dynamic graph in VP(δ) (provided δ = Θ(n)) by a randomized algorithm even when the agent does not have the ability to flag nodes while visiting. Observe that our randomized strategy relies on a positive probability of waiting. If Ps = 0, then the lower bound on pwin given above is zero. In fact, we can show that our TrapIn-(3) strategy can be adapted to foil a restless randomized agent, that is, an agent that always moves in every step; we omit the details. Remark 1 (Unknown n and δ). In this remark, we relax the memoryless assumption and allow the agent to maintain a counter of the number of steps since the start of its execution. The randomized algorithm above does not require knowledge of n. The assumption that the agent knows δ can also be removed by using the standard doubling technique; see, for example, [23]. Let Di = 2i+1 , for i = 0, 1, 2, . . .. In phase i, the agent uses Ps = 1 −
1 Di
and
Pℓ = Pr =
1 , 2Di
14
K. Ayoubi et al.
and follows this strategy for ⌈16eDi2 ⌉ steps. If the treasure has not been found, the agent proceeds to phase i + 1, thereby doubling its current estimate of δ. Let i∗ be the first phase for which Di∗ ≥ δ. Since every window of Di∗ steps contains a window of δ steps, an input in VP(δ) is also an input in VP(Di∗ ). Hence, by the proof of Theorem 6, if this phase were continued indefinitely, its expected search time would be at most 2eDi2∗ . It follows from Markov’s inequality that the probability of not finding the treasure during the phase is at most 1/8. The same conclusion holds for every subsequent phase. The total number of steps spent before phase i∗ is O(Di2∗ ). Moreover, the lengths of the subsequent phases increase by a factor of four, whereas the probability of reaching each subsequent phase decreases by a factor of at least eight. Therefore, their expected total length is also O(Di2∗ ) = O(δ 2 ). Indeed, for every m ≥ 1, the probability thatthe agent fails in all of the first m phases starting m . Letting m tend to infinity, the probability that from phase i∗ is at most 81 the agent never finds the treasure is therefore zero. Consequently, the treasure is found with probability one and in expected O(δ 2 ) steps, even when the agent initially knows neither n nor δ. 5.2
Treasure hunt in R-VP
Next, we consider treasure hunt in R-VP, a random-order arrival model, where the permutation of vertices is chosen uniformly at random at each time step. We show that the agent can complete the search significantly faster in this setting. We consider the worst-case search times under both an oblivious adversary and an adaptive adversary. The oblivious adversary must choose the location of the treasure without knowledge of the input sequence of random graphs, while the adaptive adversary has knowledge of the input sequence. We show that a simple search algorithm in which the agent simply moves to its clockwise neighbor is stochastically equivalent to a random walk on the complete graph Kn . Note that the agent does not need to flag vertices. Let τ (G, T ) be the search time of the algorithm where G is a dynamic graph in R-VP and T ∈ V (G) and T is chosen by the oblivious adversary, that is, before the search algorithm starts executing. Let T (G) be a treasure location chosen by an adaptive adversary that has knowledge of G. Note that since G is a random graph, T is a random variable. Theorem 7. For every T ∈ V (G), and G in R-VP, E[τ (G, T )] = Θ(n). For every G in R-VP, the adversary can choose T (G) such that E[τ (G, T (G))] = Θ(n log n). Proof. Fix a time step t and let the agent be at vertex i at time t. For any j ̸= i, the probability that j is the clockwise neighbor of i in a permutation chosen 1 uniformly at random is n−1 and therefore the probability that the agent moves
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
15
1 to j is n−1 . Since this holds for any j ̸= i, the search procedure we described is identical to a simple random walk on a clique. It follows that for any treasure location picked by an oblivious adversary, the expected time to reach it is at most the hitting time in a clique, and is therefore Θ(n). On the other hand, an adaptive adversary that knows the sequence of random graphs in advance can ensure that the treasure is located at the last vertex visited by the agent. Hence the expected time to reach the treasure in this case is the cover time in a clique, which is Θ(n log n).
6
Search by k ≥ 2 agents
In this section, we study treasure hunt with k ≥ 2 agents in V P (δ). We first give an online algorithm with search time O(nδ/k), showing that k agents obtain a linear speedup up to constant factors. We then prove a matching lower bound for the stated range of δ. 6.1
Upper bound for k agents in V P (δ)
We now present an online algorithm Generalized-Move-to-Unflagged for k agents that finds the treasure in O(nδ/k) time steps. The k agents may initially be located at arbitrary vertices. Agents move only to unflagged neighbors. Using the fact that access to ports is by mutual exclusion [13], we can ensure that exactly one of the agents situated at a vertex move to each of its unflagged neighbors. The pseudocode is given in Algorithm 1 .
Algorithm 1 Generalized-Move-to-Unflagged 1: Look: 2: Observe the two neighboring vertices and whether each of them is flagged. 3: Let P be the set of incident ports leading to unflagged neighbours. 4: Compute: 5: If P = ∅, do not request any port. 6: Otherwise, order the ports of P according to the agent’s private local orientation. 7: Request the first port in this order. 8: If the request fails and P contains a second port, request the second port. 9: Move: 10: If either of the port requests succeeded, move through the acquired port and flag the vertex reached. 11: Otherwise, stay at the current vertex.
Theorem 8. For δ ≥ ⌈ n−1 2 ⌉, Generalized-Move-to-Unflagged is an online algorithm for treasure hunt with k agents in VP(δ) that achieves worst-case search time τ1k ≤ δ⌈ 2n k ⌉.
16
K. Ayoubi et al.
Proof. We show that Generalized-Move-to-Unflagged achieves this bound. We divide time into windows of length δ. Let Wi be the ith window of δ steps. Let ni be the number of unflagged vertices at the start of window Wi . Observe that in Generalized-Move-to-Unflagged , an agent moves only to an unflagged node, and at most 2 agents move to the same unflagged node in the same time step Indeed, every unflagged node has degree two in the current ring, and at most one agent can acquire each of the two ports leading to it. Therefore, the number of new nodes flagged in a window is at least half the number of agents that moved in that window. We claim that at least min{ni , ⌈k/2⌉} nodes will be flagged during window Wi . First consider the case when ni ≥ ⌈k/2⌉. If every agent moves at least once during Wi , then at least ⌈k/2⌉ nodes were flagged, and the claim is proved. Otherwise, there exists an agent A that remains at the same node u during the whole window Wi . Since all nodes, and in particular, all unflagged nodes, become neighbors of u during Wi , the only reason A did not move is that another agent at u acquired the corresponding port and moved to an unflagged node. In other words, all ni unflagged nodes were visited during Wi , and the claim holds. Now consider the case when ni < ⌈k/2⌉. Then, it cannot be that all k agents moved during window Wi , and there must be some agent A that did not move. As argued above, this implies that all ni = min{ni , ⌈k/2⌉} unflagged nodes were visited by agents during Wi . To conclude the proof, we observe that the number of windows of length δ needed for all nodes to be visited is at most ⌈n/⌈k/2⌉⌉ ≤ ⌈2n/k⌉ and therefore treasure hunt is completed in δ⌈2n/k⌉ steps. 6.2
Lower bound for k agents in V P (δ)
The lower bound argument in Lemma 1 and Theorem 3 can be generalized to k agents, provided k + 2 ≤ n2 . We first run the online algorithm as long as it takes for the k agents to be spread out over a block of k + 2 nodes for the first time. We ignore these initial steps. Denote by I (the interior nodes) the block of nodes of length k + 2 containing the agents. Call the remaining nodes E (the exterior nodes). The treasure will be placed in a suitable node in E, so the agents have to spread out in a distance k block at some point, otherwise they cannot find the treasure. Lemma 2. In every period of length (k + 1)(n − k − 2), with 1 ≤ k ≤ n2 − 2, the adversary can present a sequence of vertex-permuted rings in which (i) every pair of vertices is adjacent at least once, and (ii) the k agents can collectively visit and flag at most k unflagged vertices, even if they have memory, chirality, full visibility and knowledge of node labels. Proof. As in the one-agent case, we build a period with three phases. Fix m = n − k − 2, the size of the set E. For simplicity, we assume that δ is exactly (k + 1)m. Phase 1 (⌈m/2⌉ steps): Treat the whole interior block I as a mega-vertex Vm and consider the complete graph on E ∪ {Vm }, which has m + 1 vertices.
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
17
Using a Walecki Hamiltonian decomposition, we can list ⌈m/2⌉ Hamilton cycles whose union covers all edges of this clique. We realize each cycle as a ring on V by expanding Vm into a contiguous block containing the vertices of I (in some order), while keeping the cyclic order on E as prescribed by the cycle. Hence, in these ⌈m/2⌉ steps, every E-E pair is adjacent at least once. In parallel, during the same ⌈m/2⌉ steps we permute the order of vertices inside I according to a Walecki schedule on K|I| , which is feasible because m ≥ k + 2 implies ⌈m/2⌉ ≥ ⌈(|I| − 1)/2⌉. Thus all I-I pairs are also covered by the end of Phase 1. Finally, in each step, the mega-vertex Vm has two exterior neighbors, so the expansion creates two I-E adjacencies incident to the two boundary interiors. Therefore Phase 1 creates 2⌈m/2⌉ ≥ m distinct I-E pairs. Moreover, each boundary interior is incident to at most ⌈m/2⌉ distinct exterior neighbors by the end of Phase 1. Throughout Phase 1, the adversary uses the TrapIn-(k + 2) procedure to ensure that both boundary interiors are unoccupied by agent; hence agents cannot enter E in Phase 1. Phase 2 (⌊m/2⌋ steps): We continue to keep the agents away from the boundary interiors using the TrapIn-(k + 2) procedure. In each step, we choose the two exterior vertices adjacent to the two boundary interiors so that each boundary interior meets an exterior vertex it did not meet in Phase 1. This is possible because each boundary interior met at most ⌈m/2⌉ exteriors in Phase 1, so it still has at least m − ⌈m/2⌉ = ⌊m/2⌋ unseen exteriors. After ⌊m/2⌋ additional steps, we have executed a total of ⌈m/2⌉ + ⌊m/2⌋ = m steps in Phases 1–2. Because of the TrapIn-(k + 2) procedure, the identity of the two boundary interiors may change over time; hence we cannot assert that two fixed interior vertices have met all exterior vertices by time m. We can ensure that by time m, we have realized exactly 2m distinct I-E pairs, and of the (k + 2)m possible I-E pairs, exactly km pairs remain to be realized. Phase 3 (at most km steps). Let I = {u1 , u2 , . . . , uk+2 }. We say a node in I has finished once it has already been adjacent to all other nodes in this period. If there exist two nodes ui , uj ∈ I that do not contain agents and are not finished, that is, they are still missing adjacencies with exterior nodes, we make them the boundary interior nodes, and place suitable exterior nodes next to them to take care of two missing adjacencies in the step. The remaining interior nodes are placed in between ui and uj in a block of k + 2 nodes in arbitrary order, and the remaining exterior nodes make up another contiguous block between the two chosen exterior nodes in arbitrary order. If instead there exists one node ui ∈ I that does not contain agents and is still not finished, we make ui a boundary interior node, we pick another node uj ∈ I without agents as the other boundary node. Such a node must exist, since there are k agents and k + 2 nodes in I. Furthermore uj must have finished. We place a suitable exterior node next to ui to take care of a missing adjacency. The remaining interior nodes and exterior nodes are placed arbitrarily as in the previous case.
18
K. Ayoubi et al.
Otherwise, the only nodes that do not contain agents have already finished. Take such a node, call it ui that is already finished and does not have agents. We make ui a boundary node. For the other boundary, pick a node uj from I that is still missing adjacencies. The node uj contains some agents. We will now realize all missing adjacencies for uj so that uj is finished, while ensuring that at most one exterior node is flagged. Place a suitable exterior node x next to uj (that is, x has not yet been adjacent to uj in this period), and place the remaining nodes interior nodes between ui and uj as in the other cases, and the remaining exterior nodes in a contiguous block. between x and ui . – If no agent moves from uj to x, the set I is intact, and we repeat this procedure in the next step (once again placing an exterior node next to uj , and finding an interior node with no agents for the other boundary interior node). – If some agent does move to x from uj , we will temporarily change I and follow a different special procedure. Note that if x was unflagged, it will now be flagged, and we have increased the number of flagged vertices. However, this is the only time agents can visit an unflagged exterior vertex, while we follow the special procedure to finish uj . We remove uj from I, and bring x into I temporarily. Until uj misses adjacencies with other nodes in E, we create the next few permutations by realizing the missing adjacencies for uj , meanwhile using the TrapIn-(k + 2) procedure to keep all the agents in I. Once uj is finished, we put x back in E, and uj back in I, and revert to the original procedure, described at the beginning of Phase 3. Note that the special procedure of finishing a node from I can be done only after at least two nodes from I are already finished. This implies that during the entire period, the special procedure is done at most k times, and at most k previously unflagged vertices can be visited during the period. By the end of Phase 3, all pairs of adjacencies have been realized. All three phases together take ⌈m/2⌉ + ⌊m/2⌋ + km steps. Therefore, every unordered pair {u, v} ⊆ V appears as an edge in at least one step within the period with δ = (k + 1)m = (k + 1)(n − k − 2) steps, and at most k new vertices are flagged, as claimed. Having chirality, knowledge of node labels, visibility of node labels, and memory does not help as agents collectively are not adjacent to more than k unflagged vertices during a period. Theorem 9. For 1 ≤ k ≤ n2 − 2 and δ ≥ (k + 1)(n − k − 2), and for every k online n−2 algorithm A with k agents, there exists an input in VP(δ) such that τ1 ≥ ( k −2) δ, even for agents with chirality, memory, full visibility and knowledge of node labels. Proof. By Lemma 2, in every period of length δ the agents can collectively visit at most k previously unvisited vertices. After r full periods, at most rk new vertices can have been visited. Recall that k + 2 vertices are visited before the first period starts. Therefore after r⋆ = ⌈(n − k − 2)/k⌉ − 1 = ⌈(n − 2)/k⌉ − 2 periods, there exists at least one exterior vertex that has not been visited yet.
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
19
Place the treasure at such a vertex. This treasure cannot be reached before the end of period r⋆ , hence τ1k ≥ r⋆ δ = (⌈(n − 2)/k⌉ − 2) δ. This proves the theorem. Corollary 2. Generalized-Move-to-Unflagged is asymptotically optimal in terms of worst-case search time for VP(δ) with δ ≥ (k + 1)(n − k − 2).
7
Conclusion and open problems
We studied treasure hunt in vertex-permuted dynamic rings. We showed that, in unrestricted V P , the treasure may be hidden forever from any set of k ≤ n − 3 deterministic or randomized agents. For V P (δ) with δ ≥ ⌈(n − 1)/2⌉, we gave tight bounds for the search time and competitive ratio for a single deterministic agent with flag, and showed that k agents can obtain a linear speedup. We also studied the random model R-VP. Several questions remain open. First, our lower bound for one deterministic agent with flags is proved for δ ≥ 2n. It would be interesting to know whether the same bound holds for the full feasible range δ ≥ ⌈(n − 1)/2⌉. Second, the competitive ratio of randomized algorithms against an adaptive online adversary is yet to be studied. Finally, one may ask which results extend beyond rings to vertex-permuted graphs with other topologies.
20
K. Ayoubi et al.
References 1. Agarwalla, A., Augustine, J., Moses Jr, W.K., Madhav, S.K., Sridhar, A.K.: Deterministic dispersion of mobile robots in dynamic rings. In: Proceedings of the 19th International Conference on Distributed Computing and Networking. pp. 1–4 (2018) 2. Alspach, B.: The wonderful walecki construction. Bull. Inst. Combin. Appl 52(52), 7–20 (2008) 3. Avin, C., Koucký, M., Lotker, Z.: How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In: Automata, Languages and Programming (ICALP 2008), Part I. vol. 5125, pp. 121–132 (2008) 4. Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152(2), 155–172 (1999) 5. Ayoubi, K., Narayanan, L.: Restless exploration and token dissemination in vertexpermuted temporal graphs. In: Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025) (2025) 6. Beck, A.: On the linear search problem. Israel Journal of Mathematics 2, 221–228 (1964) 7. Bellitto, T., Conchon-Kerjan, C., Escoffier, B.: Restless exploration of periodic temporal graphs. In: 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). pp. 13:1 – 13:15 (2023) 8. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (2005) 9. Bouchard, S., Dieudonné, Y., Labourel, A., Pelc, A.: Almost-optimal deterministic treasure hunt in unweighted graphs. ACM Transactions on Algorithms 19(3), 1–32 (2023) 10. Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27(5), 387–408 (2012) 11. Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Autonomous mobile robots with lights. Theoretical Computer Science 609, 171–184 (2016) 12. Das, S.K., Dhar, A.K., Gorain, B., Mahawar, M.: Collision-free exploration by mobile agents using pebbles. Proceedings of the 26th International Conference on Distributed Computing and Networking (2025) 13. Di Luna, G., Dobrev, S., Flocchini, P., Santoro, N.: Distributed exploration of dynamic rings. Distributed Computing 33(1), 41–67 (2020) 14. Di Luna, G.A., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. Theoretical Computer Science 811, 79–98 (2020) 15. Disser, Y., Hackfeld, J., Klimm, M.: Tight bounds for undirected graph exploration with pebbles and multiple agents. J. ACM 66(6) (2019) 16. Dobrev, S., Flocchini, P., Královič, R., Santoro, N.: Exploring an unknown dangerous graph using tokens. Theoretical Computer Science 472, 28–45 (2013) 17. Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. Journal of Computer and System Sciences 119, 1–18 (2021) 18. Gorain, B., Mondal, K., Nayak, H., Pandit, S.: Pebble guided optimal treasure hunt in anonymous graphs. Theor. Comput. Sci. 922, 61–80 (2022) 19. Ilcinkas, D., Wade, A.W.: Exploration of the T-interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems (2018) 20. Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010). pp. 513–522. ACM (2010)
Online Treasure Hunt in Vertex-Permuted Dynamic Rings
21
21. Lucas, E.: Récréations Mathématiques (2), chap. 6, pp. 161–164. Gauthier-Villars (1896) 22. Luna, G.A.D., Dobrev, S., Flocchini, P., Santoro, N.: Live exploration of dynamic rings. In: 36th IEEE International Conference on Distributed Computing Systems (ICDCS 2016). pp. 570–579. IEEE Computer Society (2016) 23. Luo, H., Schapire, R.E.: Towards minimax online learning with unknown time horizon. In: Proceedings of the 31st International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 32, pp. 226–234 (2014) 24. Mandal, S., Molla, A.R., Moses, W.A.: Efficient live exploration of a dynamic ring with mobile robots. Theoretical Computer Science 980, 114201 (2023) 25. Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics 12(4), 239–280 (2016) 26. Pattanayak, D., Pelc, A.: Deterministic treasure hunt and rendezvous in arbitrary connected graphs. Information Processing Letters 185, 106455 (2024)