Exploration of dynamic graphs by teams

Further reading

Papers on this problem that are not yet placed in a setting.

• Adamson & Spirakis 2026 Brief Announcement: Exploration of Always S-Connected Temporal Graphs. Exploration by teams when the whole sequence of snapshots is given in advance (offline), each agent crossing at most one present edge per round. In an always \(S\)-connected temporal graph every snapshot joins every node by a path to some node of a fixed set \(S\); \(|S|\) agents, one starting on each node of \(S\), explore every such graph whose lifetime is polynomial in \(n\), \(|S|\) and the average degree of the underlying graph (Theorem 1, Corollary 1). Through a division of the underlying graph into parts with few boundary nodes, a single agent explores an always connected temporal graph whose underlying graph has treewidth \(\mathrm{tw}\) within \(O(n^{4/3}\,\mathrm{tw}^{9/2}\log^{5/2} n)\) rounds (Theorem 2). When every edge is present in exactly one snapshot, deciding whether one agent can explore is NP-hard (Theorem 5), and the minimum number of agents that explore a path is computed in \(O(n)\) time, that for a cycle in polynomial time (Theorems 6 and 7). Full version (arXiv v2) read; Carnevale 2026 cites \(\mathrm{tw}^{11/2}\) for the brief announcement, which was not read.
• Bournat et al. 2017 Computability of perpetual exploration in highly dynamic rings. Perpetual exploration of connected-over-time rings by anonymous FSYNC robots with persistent memory and local weak multiplicity detection: \(k \ge 3\) robots for \(n > k\) (Theorem III.1); two robots fail for \(n > 3\) and one for \(n > 2\) (Theorems IV.1, V.1), and suffice for \(n = 3\) and \(n = 2\) (Theorems IV.2, V.2). Read.
• Bournat et al. 2019 Self-stabilizing robots in highly dynamic environments. Self-stabilizing perpetual exploration of connected-over-time rings by FSYNC robots with distinct identifiers: three robots for rings of at least four nodes (Theorem 4.1); two robots are impossible for \(n \ge 4\) (Theorem 3.1). Read.
• Feletti et al. 2026d Safe Exploration of Arbitrary Dynamic Dangerous Networks. Extends the temporally connected setting of Gotoh et al. 2021 to graphs with any number of black holes, unknown to the agents, which must visit every safe node while at least one agent survives. Semi-synchronous oblivious anonymous agents starting on arbitrary safe nodes explore perpetually with \(2\eta' + \sum_{x \in B}\deg(x) + 1\) agents, where \(B\) is the set of black holes and \(\eta'\) the number of transient edges between safe nodes, using whiteboards of \(O(\Delta)\) bits (Theorem 11); without black holes this is the \(2\eta + 1\) of Gotoh et al. 2021. Agents with identifiers that know the number of safe nodes also terminate (Theorem 16). Preprint; read.
• Saxena et al. 2026b Dynamic Graph Exploration: Semi-Synchrony and Dynamic Port Labeling. Exploration of 1-interval connected graphs of arbitrary topology, with port numbers reassigned in every round, under a semi-synchronous scheduler: in each round an adversary deactivates up to \(\alpha\) agents (their \(p\)), and every agent is activated infinitely often. Agents have distinct identifiers, start on arbitrary nodes and know neither \(n\) nor \(k\); nodes have no storage. With \(k \le (n-2)(\alpha+1)\) agents exploration is impossible, even with full visibility, global communication, node identifiers and storage, unbounded memory and knowledge of every parameter (Theorem 2.1, \(n \ge 3\), \(\alpha \ge 1\)). With \((n-2)(\alpha+1)+1\) agents it stays impossible for agents that see their neighbouring nodes but communicate only face to face (Theorem 2.2, \(n \ge 9\)), and for agents that see only their own node but communicate globally (Theorem 2.3). Agents that see their neighbouring nodes and communicate globally explore whenever \(k \ge (n-2)(\alpha+1)+1\), that is \(\alpha \le \lfloor (k-1)/(n-2) \rfloor - 1\), without knowing \(n\), \(k\) or \(\alpha\); every agent eventually knows that exploration is complete, the total number of moves is \(O(k)\) times the largest diameter of a snapshot, and each agent uses \(O(\max\{\log n, \log\alpha\})\) bits (Theorem 3.1, \(n \ge 4\)). The number of agents is therefore tight for every \(\alpha \ge 1\); whether global communication is necessary is left open. For \(\alpha = 0\) the threshold \(n-1\) is the bound for synchronous agents of Saxena & Mondal 2025, as reported by Saxena et al. 2026b. The timing axis has no semi-synchronous value, so the result is not placed in a setting. Read in the arXiv version (v1); theorem numbers refer to it.
• Sudo et al. 2026c Online Graph Exploration under T-Interval Connectivity. A single deterministic agent on \(T\)-interval-connected graphs of arbitrary topology whose nodes carry identifiers: the window must be \(\Omega(m)\) (Theorem 3), and with a window of \(O(\zeta m + n\log^2 n)\), where \(\zeta = \ln n/(1+\ln(m/n))\), the agent explores and stops within \(O((m-n+1)\,n + n\log^2 n)\) moves, optimal when \(m-n+1 = \Omega(\log^2 n)\) (Theorems 1 and 4). Placed in the setting \(T\)-interval-connected graphs, labelled nodes of single-agent exploration. Preprint; read.
• Ayoubi et al. 2026 Online Treasure Hunt in Vertex-Permuted Dynamic Rings. In vertex-permuted rings, where every snapshot is a cycle through all \(n\) nodes in an order the adversary chooses at each step, up to \(n-3\) agents starting at one node cannot even find a treasure, so they cannot explore, even with memory, chirality, a view of the whole snapshot and knowledge of the node labels (Theorem 1). If every two nodes are adjacent within every \(\xi\) steps and agents flag the nodes they visit, \(k\) agents visit all nodes within \(\xi\lceil 2n/k\rceil\) steps (proof of Theorem 8). Preprint; read.
• Gotoh et al. 2020 Dynamic Ring Exploration with (H,S) View. A single agent on a 1-interval connected ring with partial knowledge of the future: it sees which edges within \(H\) hops will be present in each of the next \(S\) rounds. It can explore exactly when \(H + S \ge n\) and \(S \ge \lceil n/2\rceil\) (Theorem 2), in \(O(n^2)\) rounds, \(O(n^2/H + nH)\) when \(S\) is large enough, and \(O(n^2/H + n\log H)\) when \(S \ge n-1\) (Theorems 1, 3), against \(\Omega(n^2/H)\) for every \(S\) (Theorem 4). Read in full.