Collaborative exploration
\(k\) agents start together at the root of an unknown graph and must visit all its nodes; how much faster than one agent can a team be?
Problem statement and measuresexpand
A team of \(k\) distinguishable agents starts at a node \(s\) (the root) of an unknown connected graph with \(n\) nodes; \(D\) is the largest distance from \(s\). In synchronous rounds every agent traverses at most one edge. When an agent reaches a node it sees the incident edges. The team must visit every node (some papers also require all agents to return to \(s\); the bounds coincide asymptotically).
Time is the number of rounds (in the asynchronous model: the total number of moves). The offline optimum is \(\Theta(n/k + D)\), so an algorithm that explores every tree in \(\mathrm{CR}(k)\cdot(n/k+D)\) rounds is called \(\mathrm{CR}(k)\)-competitive; a single depth-first search is \(O(k)\)-competitive. Memory is bits per agent; most of this literature lets it be unbounded.
Unless a variant says otherwise, nodes are labelled (an agent recognises a node it has seen), which is the standard assumption of collective tree exploration; on trees it does not matter for lower bounds Disser et al. 2020. With anonymous nodes and \(k = n\), the problem is solved by rooted dispersion.
Measures: Time, rounds until every node is visited (asynchronous: total moves); Memory, bits per agent.
Trees, complete communication
standard settingverifiedCollective tree exploration as posed by Fraigniaud, Gąsieniec, Kowalski and Pelc: the competitive ratio is now between \(\Omega(\log k/\log\log k)\) and \(O(\log^2 k)\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Node identifiers: labelled nodes
- Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.
- Randomness: deterministic
- The next state and move of an agent are a function of its current state and what it observes.
- Communication: global communication
- At every round every agent can read the memory of every other agent, wherever it is.
- Node memory: no whiteboards
- Nodes have no storage: no information can be left at a node except by an agent staying there.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Team size: any \(k\)
- Any number \(k\ge 2\) of agents.
- Topology: tree
- \(G\) is connected and acyclic: \(|E|=n-1\).
What is known
- deterministic
- holds with global communication and unbounded memory
- for \(k \le n\log^\kappa n\); first shown by Dynia et al. 2007 for \(k<\sqrt n\)
- the hard instances are trees
Results, in order of publication
Works already with write-read communication at nodes; \(O(k/\log k)\)-competitive. The analysis is tight on a tree of Higashikawa et al. 2014.
Breadth-first depth-next; optimal when \(D=o(\sqrt n)\).
First ratio below \(k/\log k\): \(O(k/\exp(\sqrt{\ln 2\ln k}))\).
First polynomial improvement: \(O(\sqrt k)\)-competitive by using \(\sqrt k\) of the agents. Current best among peer-reviewed results.
\(O(\log^2 k)\)-competitive. A September 2026 preprint, not yet peer-reviewed.
Open questions
Determine the competitive ratio of synchronous collective tree exploration: between \(\Omega(\log k/\log\log k)\) and \(O(\log^2 k)\).
Do randomized algorithms help? A randomized lower bound of \(\Omega(\sqrt{\log k}/\log\log k)\) is attributed to Ortolf and Schindelhauer (SPAA 2012), not checked here. Cosson and Massoulié conjecture they do not Cosson & Massoulié 2025.
Notes
Fraigniaud et al. conjectured that a constant ratio is possible; Dynia et al. 2007 refuted it. Greedy algorithms cannot beat \(\Omega(k/\log k)\) Higashikawa et al. 2014, which is why progress needed new ideas: tree-mining games Cosson 2024 and potential functions Cosson & Massoulié 2024.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.