From exploration to dispersion, and beyond

Fraigniaud, Gąsieniec, Kowalski and Pelc posed collective tree exploration: \(k\) agents start at the root of an unknown tree and must visit every node as fast as possible Fraigniaud et al. 2006. The offline optimum is \(\Theta(n/k + D)\), by spreading the agents along an Euler tour of the tree Disser et al. 2020. Their algorithm is \(O(k/\log k)\)-competitive, which Disser, Mousset, Noever, Škorić and Steger call "only slightly better than the trivial upper bound of \(O(k)\)" of a single depth-first traversal Disser et al. 2020 Fraigniaud et al. 2006; without any information sharing, a factor \(k\) is unavoidable Fraigniaud et al. 2006. Cosson, Massoulié and Viennot frame the problem as "a fundamental problem behind the exploration of an unknown physical environment with a team of agents" and add: "Despite almost two decades of research, we still do not completely understand how much exploration time can decrease with the number of agents" Cosson et al. 2023.

The lower bound side was opened by Dynia, Łopuszański and Schindelhauer, who showed \(\Omega(\log k/\log\log k)\) for \(k < \sqrt n\) (as reported by Disser et al. 2020); Disser et al. extended it to \(k \le n\log^\kappa n\) for every constant \(\kappa\) Disser et al. 2020. The upper bound moved from \(O(k/\log k)\) to below \(k/\log k\) Cosson 2024, to \(O(\sqrt k)\) Cosson & Massoulié 2024, and in a 2026 preprint to \(O(\log^2 k)\) Cosson & Massoulié 2026. These results assume labelled nodes and, except in the whiteboard variants, free communication, so the agents share a map of what has been explored.

A second line asks what a team can do with very little memory, and here agents act as markers for each other. Rollik's traps show that no finite team of finite automata explores all graphs Rollik 1980 (as recounted by Disser et al. 2019). Disser, Hackfeld and Klimm observe that a team of \(p+1\) agents can simulate one agent with \(p\) pebbles, one agent walking while the others stand still, and that before their work no algorithm explored undirected graphs with sublogarithmic memory using several agents or pebbles Disser et al. 2019. Their result closes the question:

"Since an additional agent is at least as powerful as a pebble, this implies that \(O(\log\log n)\) agents with constant memory can explore any \(n\)-vertex graph." Disser et al. 2019

They also show that \(\Omega(\log\log n)\) agents are needed even when each has \(O((\log n)^{1-\varepsilon})\) bits Disser et al. 2019. An agent that stays still is a marker; dispersion is built on the same idea.

Augustine and Moses Jr. introduced dispersion in 2018: \(k\) agents on an \(n\)-node graph must reach a configuration with at most one agent per node. Their motivation is self-driving electric cars that look for free charging stations instead of queueing, and they place the problem between scattering, exploration and load balancing from the first page Augustine & Moses Jr. 2018:

"Since any solution to a problem of dispersion acts as a solution to \(n\) robot exploration under the same conditions, any possibility results achieved for dispersion apply to \(n\) robot exploration." Augustine & Moses Jr. 2018

Lower bounds move the other way, so the \(\Omega(D^2)\) bound for \(n\) agents on trees Disser et al. 2020 is a dispersion lower bound. The catalogue records that this bound is existential in \(D\) (the hard trees have height about \(\sqrt{\log n}\)), so whether rooted dispersion on taller trees needs \(\Omega(D^2)\) rounds is open.

The assumptions are much weaker than in collaborative exploration. Sudo, Shibata, Nakamura, Kim and Masuzawa single out "the unique computation model": no node identifiers, no memory at the nodes, agents with identifiers that talk only when they share a node Sudo et al. 2024. The algorithms recover the marker idea: in the depth-first dispersion of Kshemkalyani and Ali, "A robot that docks at a node helps other robots to determine whether they have visited this node before" Kshemkalyani & Ali 2019. Every later improvement up to time-optimal \(O(k)\) rounds with \(O(\log(k+\Delta))\) bits, synchronous Kshemkalyani et al. 2025 and asynchronous Pattanayak et al. 2025, is a faster way of using settled agents as markers on anonymous nodes.

Because dispersion with \(k = n\) explores, the dispersion results are also the best known results for \(n\) agents exploring an anonymous graph with only local communication: \(O(n)\) rounds and \(O(\log n)\) bits per agent from a rooted start Kshemkalyani et al. 2025, an inference the catalogue makes and the paper does not state. With labelled nodes and global communication, \(n\) agents explore a tree in \(D^2\) rounds Disser et al. 2020; whether anonymity and local communication force \(\Omega(n)\) rounds on shallow trees is open, and Augustine and Moses Jr. already asked for \(o(n)\)-round dispersion on trees Augustine & Moses Jr. 2018.

Dispersion also gave exploration-type questions new resources to measure. Gorain, Mandal and Mondal took up the question of Bouchard, Dieudonné and Pelc whether gathering needs communication Bouchard et al. 2023 and asked it for dispersion: their silent agents convey information only by the timing of moves and by counts of co-located agents Gorain et al. 2022. Molla and Moses Jr. replaced identifiers by coin flips Molla & Moses Jr. 2019. Each such variant is, for \(k = n\), a statement about collaborative exploration under the same assumptions.

Kshemkalyani, Kumar, Molla and Sharma describe the agent-based model by its two differences from message passing: the nodes have no identifiers, computation or storage, and devices can exchange information only when co-located, so a message to a neighbour requires a move Kshemkalyani et al. 2024. With \(n\) agents on \(n\) nodes the model corresponds to message passing with one device per node, and their simulation theorem converts any message-passing algorithm that runs in \(R\) rounds into an \(O(\Delta R\log n)\)-round agent algorithm from a dispersed start (plus \(O(n\log^2 n)\) rounds otherwise), provided \(n\) and \(\Delta\) are known Kshemkalyani et al. 2024. Their stated goal is to remove that knowledge, and they note that limited storage "makes it impossible for the relocatable devices to first traverse the graph to learn the topology and then run graph computation as a second step" Kshemkalyani et al. 2024.

Dispersion is the first step in most of what followed. Chand, Molla and Sivasubramaniam built dominating sets on it: "Our algorithms rely on the ideas used for dispersion", taking "advantage of the fact that most dispersion protocols involve the exploration of \(G\)" Chand et al. 2023. For triangle counting, Chand, Das and Molla state that a dispersed configuration "is a requirement" Chand et al. 2026. Kaur, Gorain and Mondal reach maximal independent sets through distance-2 dispersion, which with \(n\) agents is the same problem, and elect a leader on the way Kaur et al. 2026. Chand and Molla build on time-optimal dispersion Kshemkalyani et al. 2025 to obtain, in \(O(n)\) rounds, termination after dispersion, a spanning tree, a leader and a minimal dominating set Chand & Molla 2026.

The progress is quick. Leader election without knowledge went from \(O(m)\) rounds with \(O(n\log n)\) bits Kshemkalyani et al. 2024 to \(O(n\log^2 n)\) rounds with \(O(\log n)\) bits Kshemkalyani et al. 2025 and to \(O(n)\) rounds Chand & Molla 2026. Maximal independent sets Pattanayak et al. 2024 Kaur et al. 2026, minimum spanning trees and BFS trees Chand et al. 2025, and triangle and butterfly counts Chand et al. 2026 Chand et al. 2025 followed the same route.

1. Height versus size. Is \(\Omega(D^2)\) the right bound for \(n\) agents on a tree of every height? Exploration theory proves it for one height Disser et al. 2020; dispersion uses it for all.
2. Settled agents versus pebbles. A pebble is a mute marker; a settled agent stores and exchanges \(O(\log n)\) bits. How much of the \(\Theta(\log\log n)\) pebble bound Disser et al. 2019 changes when markers can talk?
3. Anonymity versus labels. The collaborative-exploration bounds assume labelled nodes and global communication; dispersion assumes neither. Where does anonymity start to cost time?
4. Lower bounds for agent-based problems. No time lower bound specific to leader election, independent sets, dominating sets or spanning trees by agents is recorded in the catalogue; the only bounds come from dispersion itself. Whether the \(O(n)\) rounds of Chand & Molla 2026 are optimal for leader election, in particular from a dispersed start where no dispersion is needed, is open.

The open questions above are recorded with their variants: the rooted-tree and tree variants of dispersion, and the anonymous graphs with \(k = n\) agents variant of collaborative exploration.