Home›Mobile agents on graphs›Exploration›Collaborative exploration

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.

no assumptions›+ static graph, + undirected›+ labelled nodes›+ global communication›+ synchronous›any \(k\), + free team›+ tree

Trees, complete communication

standard settingverified

Time: near-optimalMemory: unknown

Collective 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)

+Graph dynamicsstatic graph+Edge directionundirected+Node identifierslabelled nodes (an agent can recognise a node it has visited)+Communicationglobal (any agent can read any other agent's state)+Timingsynchronous rounds+Connectivity of the teamthe agents may spread out+Topologytree

Not assumed

RandomnessdeterministicNode memoryno whiteboardsTeam sizeany number \(k\) of agents

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.
Connectivity of the team: free team: Agents may be anywhere in the graph.
Topology: tree: \(G\) is connected and acyclic: \(|E|=n-1\).

What is known

Time · rounds until every node is visited (asynchronous: total moves)

near-optimal

\(O(\log^2 k)\) versus \(\Omega(\log k/\log\log k)\) competitive: about a \(\log k\log\log k\) factor (upper bound from a preprint; the peer-reviewed gap is \(O(\sqrt k)\) versus the same lower bound).

lower bound

\(\Omega\big(\tfrac{\log k}{\log\log k}\,(\tfrac nk + D)\big)\) Disser et al. 2020

bottleneckonline tree revelation

holds when

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

Before that, a ratio of at least \(2-1/k\) on trees of \(n = xk^2+1\) nodes, so for \(k<\sqrt n\) (Theorem 3.2 of Fraigniaud et al. 2006a, proved with an adversary that answers each choice of an unexplored edge); Dereniowski et al. 2015a state it for deterministic and randomized algorithms. Dynia et al. 2007 prove their bound for deterministic algorithms on trees of \(O(tk)\) nodes with \(t > k\) (Theorem 1).

introductory

\(O(D + n/\log k)\)

Fraigniaud et al. 2006a

current best

\(\tfrac{2n}{k}+O(D\log^2 k)\)

Cosson & Massoulié 2026 preprint

Memory · bits per agent

unknown

Memory is not bounded in these papers.

lower boundnone known

introductory—

current best—

Results, in order of publication

Fraigniaud et al. 2006a introductory

Time \(O(D + n/\log k)\)

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.

Cosson et al. 2023 also

Time \(\tfrac{2n}{k}+D^2(\min\{\log\Delta,\log k\}+2)\)

Breadth-first depth-next; optimal when \(D=o(\sqrt n)\).

Cosson 2024b also

Time \(\tfrac{2n}{k}+O(k^{\log_2 k-1}D)\)

First ratio below \(k/\log k\): \(O(k/\exp(\sqrt{\ln 2\ln k}))\).

Cosson & Massoulié 2024 also

Time \(\tfrac{2n}{k}+O(kD)\)

First polynomial improvement: \(O(\sqrt k)\)-competitive by using \(\sqrt k\) of the agents. Current best among peer-reviewed results.

Cosson & Massoulié 2026 preprint current best

Time \(\tfrac{2n}{k}+O(D\log^2 k)\)

\(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. listed an algorithm with constant ratio as their first open problem Fraigniaud et al. 2006a, and according to Disser et al. 2020 suggested in their initial version that one exists; Dynia et al. 2007 showed that no deterministic algorithm achieves it. Greedy algorithms cannot beat \(\Omega(k/\log k)\) Higashikawa et al. 2014, which is why progress needed new ideas: tree-mining games Cosson 2024b 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

Trees, no communication

Time \(O(k)\cdot\text{optimal}\)

Trees, asynchronous, complete communication

Time \(2n+O(kD\log^2 k)\)

Arbitrary graphs, complete communication

Time \(\tfrac{2n}{k}+D^2(\min\{\log\Delta,\log k\}+2)\)

Lower bounds from stronger settings hold here

Trees with \(k = n\) agents

Time \(D^2/3\)

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.