Online Treasure Hunt in Vertex-Permuted Dynamic Rings

Online Treasure Hunt in Vertex-Permuted Dynamic Rings is a study by Kamran Ayoubi, Bernard Mans, and Lata Narayanan investigating how mobile agents search for a target in a dynamic ring where vertices are permuted at each step. The research establishes that treasure hunt is impossible for $k \leq n-3$ agents in unrestricted vertex-permuted rings, but becomes feasible under the restricted class VP($\delta$), where every pair of vertices becomes neighbors within $\delta$ steps, requiring $\delta \geq \lceil(n-1)/2\rceil$.

Key findings include: Single Agent Performance: For $\delta \geq 2n$, a single agent using flags to mark visited nodes achieves a tight worst-case search time and competitive ratio of $\Theta(\delta n)$ via the "Move-to-Unflagged" algorithm. Without flags, deterministic search is impossible, though a randomized strategy achieves expected $O(\delta^2)$ time. Multi-Agent Speedup: $k$ agents can achieve a linear speedup, reducing the worst-case search time to $O(n\delta/k)$, provided $\delta$ is sufficiently large relative to $n$ and $k$. * Random Permutations: In the random vertex-permuted model (R-VP), the expected search time is $\Theta(n)$ against an oblivious adversary and $\Theta(n \log n)$ against an adaptive adversary, behaving similarly to random walks on a clique.

The paper studies online treasure hunt in a highly dynamic network model: a ring of \(n\) vertices whose vertex order is permuted at every time step. A team of \(k \ge 1\) agents must locate a hidden treasure without prior knowledge of the future sequence of permutations, so the agents’ relative positions to one another, to the network topology, and to the treasure can change adversarially over time. The model captures settings where the underlying graph remains a ring, but node identities or positions are continuously reconfigured.

Its main contribution is a sharp feasibility analysis under different levels of adversarial reconfiguration. In the unrestricted vertex-permuted dynamic ring model, the paper proves that treasure hunt is impossible for any team of \(k \le n-3\) agents: no online strategy can guarantee discovery when the permutation sequence is arbitrary. The paper then moves to the restricted \(VP(\delta)\) setting, where the permutations are constrained by a parameter \(\delta\), typically bounding how far a vertex can move or how localized the reconfiguration may be. In this regime, it characterizes when the treasure hunt becomes solvable and analyzes the resulting tradeoffs among the number of agents, the ring size, and the allowed permutation range.

The work matters because it identifies a clear boundary between solvable and unsolvable search problems in reconfigurable dynamic networks. It shows that arbitrary topological shuffling can defeat all but near-complete agent coverage, while bounded vertex mobility restores enough structure for coordinated search to succeed. More broadly, the results inform the design of robust distributed search, monitoring, and exploration protocols in environments such as mobile ad hoc networks, reconfigurable sensor rings, or other systems where connectivity changes rapidly but may be partially predictable or physically constrained.