Minimum spanning tree by agents
\(n\) agents in an anonymous weighted graph must build a minimum spanning tree.
Problem statement and measuresexpand
\(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.
Arbitrary start
verifiedFrom an arbitrary start without knowledge, an MST takes \(O(m+n\log n)\) rounds with \(O(n\log n)\) bits, or \(O(m+n\log^2 n)\) rounds with \(O(\Delta\log n)\) bits.
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.
- Identifiers: distinct IDs (eponymous)
- Distinct identifiers (eponymous agents): the label function \(\mathrm{id}:\{1,\dots,k\}\to\{1,\dots,L\}\) is injective; usually \(L=k^{O(1)}\), so a label takes \(O(\log k)\) bits.
- Communication: local communication
- Agents at the same node at the same time can read each other's entire memory (face-to-face communication). Agents crossing on an edge do not meet.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Knowledge: no knowledge
- Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
- Initial configuration: any start
- Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
Results, in order of publication
Theorem 3: elect a leader in \(O(m)\) rounds (Theorem 2), which also disperses the agents, then merge components along minimum outgoing edges; no knowledge of graph parameters.
Theorem 4.4: elect a leader in \(O(n\log^2 n)\) rounds with \(O(\log n)\) bits (Theorem 1.1), then run the MST technique of Kshemkalyani et al. 2024; no knowledge of graph parameters. Best in memory; it pays a \(\log n\) factor on the \(n\log n\) term of the time.
Open questions
An MST from an arbitrary start in \(O(m + n\log n)\) rounds, or fewer, with \(O(\log n)\) bits per agent and no knowledge of graph parameters.
Notes
Knowing \(n\) and \(\Delta\), Kshemkalyani et al. 2026 obtain \(O(m+n\log^2 n+D\Delta\log n)\) rounds with \(O(\Delta\log n)\) bits (Theorem 2), which the algorithm of Kshemkalyani et al. 2025c matches or beats without knowledge. Checked against the full text of Kshemkalyani et al. 2024 (Theorem 3) and Kshemkalyani et al. 2025c (Theorem 4.4).
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
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.