Mobility Matters
Home›Mobile agents on graphs›Computing with agents›BFS tree by agents

BFS tree by agents

\(n\) agents in an anonymous graph must build a breadth-first spanning tree, without being told the root.

Problem statement and measurescollapse
d=0d=0d=1d=0d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2d=0d=1d=1d=2d=2122334455Start: dispersed; root 1 has depth 0Phase 0: depth-0 agent 1 visitsPhase 1: depth-1 agents 4, 2 visitPhase 2: depth-2 agents 5, 3 visitFinal: no new depth; BFS tree from root 1
BFS tree, grown layer by layer Chand et al. 2025: the agents are dispersed and the root (agent 1, chosen by leader election, not shown) has depth 0. In phase \(d\) (of \(2\Delta = 6\) rounds) every agent of depth \(d\) visits each neighbour and comes back, one edge per round, while all others wait at home; a waiting agent without a depth that is visited takes depth \(d+1\) and the visitor's home as its parent (thick edges). The tree is complete when a phase gives no new depth.

\(n\) agents with distinct identifiers (IDs) are placed on the nodes of an anonymous port-labelled graph with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). The start is rooted (all agents on one node), dispersed (one agent on each node) or arbitrary. Agents compute only by moving and by talking with agents on the same node. The agents must build a BFS tree from a root they choose, each agent knowing its parent and children: every agent (or node) learns its part of the output. Time is in synchronous rounds; memory in bits per agent.

Measures: Time, rounds; Memory, bits per agent.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine \(n\) agents (small mobile computers), one in each room of a building, who want a plan for emergencies: one room is the exit, and every other agent should know which room next to its own is one step closer to the exit along a shortest route. The building is a graph: rooms are its nodes and corridors are its edges; there are \(n\) nodes and \(m\) edges, and from here on we say only node and edge. Two nodes joined by an edge are neighbours. The degree of a node is the number of edges at it, \(\Delta\) is the maximum degree, and the diameter \(D\) is the largest distance between two nodes. Nodes have no names, but the edges at a node are numbered \(1, 2, \dots\); these numbers are ports. A BFS tree (breadth-first search tree) with root \(s\) (the exit of the picture) gives every other node \(v\) a parent: a neighbour of \(v\) that is one step closer to \(s\), so following parents gives a shortest path to \(s\). In the basic version the agents start one per node (a dispersed start; an agent's starting node is its home), have distinct identifiers (IDs), know nothing about the graph, and must choose the root themselves; they move in synchronous rounds (talk to the agents on the same node, then move along at most one edge), and at the end every agent knows its parent and its children. We count rounds and bits of memory per agent. As for all problems in this family, agents can imitate message-passing algorithms by visiting neighbours, the method explained under leader election by agents.

1AlgorithmGrow the tree layer by layer from a known root Dispersed start, root unknown → Chand et al. 2025

Suppose the agent on the root \(s\) is already known and the agents know \(\Delta\). Time is cut into phases of \(2\Delta\) rounds. Each agent will record a depth, a number that is unknown at the start.

  1. In phase 0 the root agent takes depth 0.
  2. In phase \(d\), every agent of depth \(d\) visits its neighbours one by one (out along one edge, back along it); all other agents stay at home.
  3. An agent that has no depth yet and receives such a visit takes depth \(d+1\) and records the visitor's home as its parent (if several visitors arrive, it picks the smallest ID). The visitor records its new child.
  4. Repeat with phase \(d+1\) until no agent gets a new depth.
Why it works and what it costs. An agent gets depth \(d\) exactly when its distance to \(s\) is \(d\), so the parents form a BFS tree. During phase \(d\) only depth-\(d\) agents move, so the agents they visit are at home. Each phase lasts \(2\Delta\) rounds and there are at most \(D\) phases with new nodes, so the tree is built in \(O(D\Delta)\) rounds; Chand et al. 2025 cite this bound for a known root. Without a known root they first build an MST to get a root and the values \(m\) and \(\Delta\), which gives \(O(\min(D\Delta, m\log n) + n\log n + \Delta\log^2 n)\) rounds with \(O(\log n)\) bits.

Why it matters. It is the agent version of the textbook BFS, and it shows why knowing \(\Delta\) matters: it fixes how long a phase must last.

2Lower boundA BFS tree contains an elected leader Dispersed start, root unknown →

When a BFS tree has been built, the agent on the root knows it has no parent, and every other agent knows it has one. So "I am the root" is exactly a leader election: one agent knows it is the leader and all others know they are not.

Why it holds. Hence building a BFS tree without a known root is at least as hard as leader election, and any lower bound for leader election also holds for BFS. This is why the best known algorithm spends \(O(n\log n + \Delta\log^2 n)\) rounds electing a leader (via an MST) before the BFS itself Chand et al. 2025. The catalogue records no lower bound for either problem, so the time this preliminary step really needs is open.

Why it matters. It explains why leader election is the first building block in this family: trees, MIS and counting all need an agent that starts things off.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Memory
Dispersed start, root unknown standard
A BFS tree in \(O(\min(D\Delta, m\log n)+n\log n+\Delta\log^2 n)\) rounds with \(O(\log n)\) bits.
unknown \(O(\min(D\Delta,m\log n)+n\log n+\Delta\log^2 n)\) vs —
unknown \(O(\log n)\) vs —

What the community started looking at

BFS trees are the next building block after leader election; the question is rounds then memory without knowledge of the root or of graph parameters Chand et al. 2025.

Perspectives

  • From exploration to dispersion, and beyond How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.

All settings

The assumption tree (1 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Identifiers › Communication › Timing › Knowledge › Initial configuration › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge

0no knowledge of graph parameters1\(n\) and \(\Delta\) are known

Whether agents know global parameters is inherited from message passing, where nodes typically know \(n\) or an upper bound on it, and possibly \(\Delta\) and \(D\); Kshemkalyani, Kumar, Molla and Sharma set the agent-based model against this and asked for algorithms that rely on no such knowledge, "neither exact nor an upper bound" Kshemkalyani et al. 2024. Knowing \(n\) and \(\Delta\) tells an agent how long to wait: in the arbitrary-start minimal dominating set algorithm of Chand, Molla and Sivasubramaniam every robot waits \(\kappa n\Delta\) rounds before leader election begins Chand et al. 2023, and the introductory maximal independent set algorithm assumes both \(n\) and \(\Delta\) Pattanayak et al. 2024 (as reported by Kaur et al. 2026 and Kshemkalyani et al. 2024). Kshemkalyani et al. state the trade-off: solutions without knowledge "are more resilient to network changes and device faults", but "algorithm design becomes challenging since devices may not know how long to run a procedure to guarantee a solution" Kshemkalyani et al. 2024. Later papers remove the assumption by first dispersing with termination detection and electing a leader, after which a spanning tree lets the agents compute \(\Delta\) and the largest identifier themselves Chand et al. 2026; knowing only that largest identifier \(L\) is a weaker assumption, recorded on results rather than as a level of this axis Chand et al. 2025. For BFS trees the catalogued algorithm uses no graph parameter, only \(L\) Chand et al. 2025.

Formal definitions
0no knowledge
Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\)
Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

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