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

Minimum spanning tree by agents

\(n\) agents in an anonymous weighted graph must build a minimum spanning tree.

Problem statement and measurescollapse
1423222333555666Start: dispersed; every node its own fragmentPhase 1, block 1: 5, 6 visit neighboursPhase 1, block 2: 2, 3, 6 visit neighboursPhase 1, block 3: 3, 5 visit neighboursEach adds its lightest edge: fragments mergePhase 2, block 1: 5, 6 visit neighboursPhase 2, block 2: 2, 3, 6 visit neighboursPhase 2, block 3: 3, 5 visit neighboursPhase 2: edges of weight 3, 4 leave fragments5 reports weight 3 to leader 3, 6 weight 4 to 2Final: both pick weight 3; one fragment, the MST
MST by growing fragments along their lightest outgoing edges (Borůvka, Gallager-Humblet-Spira) Chand et al. 2025: agents dispersed on a weighted cycle meet their neighbours with the ID-bit schedule (in each block of \(2\Delta = 4\) rounds, agents whose current ID bit is 1 visit each neighbour and come back, one edge per round). Each one-node fragment adds its lightest edge (weights 1 and 2), giving two fragments (colours) with leaders 3 and 2 (circled). In phase 2 the agents meet again with the same walks (shown round by round) and find the edges that leave their fragment (red); 5 and 6 walk to their leaders to report the lightest outgoing edge, both fragments pick weight 3 and merge into the minimum spanning tree (thick).

\(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 minimum spanning tree of the edge-weighted graph, each agent knowing which incident edges belong to it: 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 must choose which corridors to keep open so that every room can still reach every other, using the cheapest possible total length. 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. Every edge has a weight (its cost), which the agents on its two ends can see; \(\Delta\) is the maximum degree (the largest number of edges at one node). Nodes have no names, but the edges at a node are numbered \(1, 2, \dots\); these numbers are ports. A spanning tree is a set of \(n-1\) edges that connects all nodes without forming a cycle, and a minimum spanning tree (MST) is one with the smallest total weight. In the basic version the agents start one per node (a dispersed start), have distinct identifiers (IDs), 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 must know which of the edges at its node belong to the MST. We count rounds and bits of memory per agent. As for all problems in this family, the agents can imitate a message-passing algorithm by visiting their neighbours, the method explained under leader election by agents.

1AlgorithmGrow fragments along their lightest outgoing edges Dispersed start → Chand et al. 2025

This is the classic Borůvka / Gallager-Humblet-Spira idea, carried out by agents. Assume all edge weights differ (agents can break ties using their IDs and ports).

  1. At the start every node is its own fragment: a set of nodes joined by edges already chosen for the tree, so a small tree.
  2. In each phase, every agent meets its neighbours by the ID-bit schedule (in block \(i\) of \(2\Delta\) rounds, agents whose \(i\)-th ID bit is \(1\) visit their neighbours one by one while the others wait; see leader election by agents) and learns which of the edges at its node leave its fragment and how heavy they are.
  3. The agents of each fragment pass the lightest such edge up their tree to the fragment's leader (one agent of the fragment that decides for it), which picks the lightest outgoing edge of the whole fragment: the edge of smallest weight with one end in the fragment and the other outside.
  4. Every fragment adds its lightest outgoing edge; fragments joined by these edges merge into one, with one leader.
  5. Repeat until one fragment remains: it is the MST, and its leader is also an elected leader for all agents.
Why it works and what it costs. Step 4 is safe because of the cut property: the lightest edge leaving any group of nodes always belongs to the MST. Every fragment merges with at least one other in each phase, so the number of fragments at least halves, and \(O(\log n)\) phases suffice. In total this gives \(O(n\log n + \Delta\log^2 n)\) rounds with \(O(\log n)\) bits per agent, assuming the agents know \(L\), the largest ID Chand et al. 2025. The first agent algorithm handled the fragments one at a time and needed \(O(m + n\log n)\) rounds and \(O(n\log n)\) bits Kshemkalyani et al. 2024.

Why it matters. Halving the number of fragments in every phase is the standard way to build spanning trees in parallel, and the resulting tree gives agents a root and a structure for broadcasting, used afterwards for BFS and counting problems.

2Lower boundOn a ring, the heaviest edge is far away Dispersed start →

Information moves at most one edge per round, because it travels only inside agents and each agent moves along at most one edge per round. So after \(t\) rounds, what the agent on node \(y\) knows depends only on the part of the graph within distance \(t\) of \(y\).

Take a ring of \(n\) nodes with distinct weights. The MST of a ring is the ring minus its heaviest edge. Look at an edge \(e = \{u, v\}\) and an edge \(f\) on the opposite side of the ring, at distance about \(n/2\) from \(u\) and \(v\). Give every edge other than \(e\) and \(f\) a weight below the weight of \(e\). If \(f\) is lighter than \(e\), then \(e\) is the heaviest edge and is not in the MST; if \(f\) is heavier, \(e\) is in the MST.

Why it holds. Within fewer than about \(n/2 - 1\) rounds the agents on \(u\) and \(v\) cannot tell these two rings apart, so they answer the same way and one answer is wrong. Hence any algorithm needs \(\Omega(n)\) rounds on a ring, and \(\Omega(D)\) rounds in general, where \(D\) is the diameter (largest distance between two nodes). This is our own short argument; the catalogue records no lower bound. On a ring \(\Delta = 2\), so the best algorithm, \(O(n\log n + \Delta\log^2 n)\), is within a \(\log n\) factor of it there.

Why it matters. It shows that an MST is a global object: an edge's membership can depend on an edge at the other end of the graph.

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 standard
From a dispersed start, an MST takes \(O(n\log n+\Delta\log^2 n)\) rounds with \(O(\log n)\) bits.
unknown \(O(n\log n+\Delta\log^2 n)\) vs —
unknown \(O(\log n)\) vs —

What the community started looking at

Spanning trees were the first application of agent-based leader election Kshemkalyani et al. 2024; the question since has been rounds, then memory, without knowledge 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 minimum spanning trees, Kshemkalyani et al. need no parameter Kshemkalyani et al. 2024, and Chand, Kumar and Molla reduce memory to \(O(\log n)\) bits knowing 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.