Mobility Matters
Home›Mobile agents on graphs›Computing with agents›Maximal independent set by agents

Maximal independent set by agents

\(n\) agents in an anonymous graph must mark a maximal independent set of nodes.

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 settle on the nodes of a maximal independent set, every other agent knowing it is not in the set: 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.

no assumptions›+ static graph, + undirected, + distinct IDs (eponymous), + local communication, + synchronous

No knowledge

verified
Time: unknownMemory: unknown

Without knowledge: \(O(\max\{n\log^2 n, m\})\) rounds with \(O(\log n)\) bits.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Identifiersdistinct identifiers (eponymous): agents have pairwise distinct identifiers+Communicationlocal (co-located agents communicate)+Timingsynchronous rounds

Not assumed

Knowledgeno knowledge of graph parametersInitial configurationarbitrary (agents on any \(\ell \le k\) nodes)Topologyarbitrary connected graph
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

Time · rounds
unknown
—
lower boundnone known
introductory
\(O(n\Delta)\)
current best
\(O(\max\{n\log^2 n,m\})\)
Memory · bits per agent
unknown
—
lower boundnone known
introductory
\(O(n\log n)\)
current best
\(O(\log n)\)

Results, in order of publication

Kshemkalyani et al. 2024 introductory
Time \(O(n\Delta)\)Memory \(O(n\log n)\)
Kaur et al. 2026 current best
Time \(O(\max\{n\log^2 n,m\})\)Memory \(O(\log n)\)

Open questions

None recorded for this variant.

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

Knowing \(n\) and \(\Delta\)

Branches from here

Knowing \(n\) and \(\Delta\)

+knows \(n\), \(\Delta\)
With \(n\) and \(\Delta\) known: \(O(n\Delta)\) rounds from a rooted start, and \(O(n\log^2 n+D\Delta\log n)\) from any start, with \(O(\log n)\) bits.

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