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 measurescollapse
1122334455Start: all 5 agents at node a1 settles at a, visits its neighboursno black neighbour: 1 turns black2 settles at b; parent is black, so grey3 settles at c and visits its neighbours3 saw a black neighbour: greya is occupied: the group turns back4 settles at e and visits its neighboursno black neighbour: 4 turns black5 settles at d and visits its neighboursFinal: black nodes a, d, e form an MIS
MIS by a depth-first walk that colours as it settles Chand et al. 2023 (other algorithms, e.g. from an arbitrary start, in Pattanayak et al. 2024): all agents start at node \(a\); the group moves one edge per round in depth-first order (the walk's tree is drawn in grey), and at each empty node the agent with the smallest ID settles. A settled agent whose parent is black turns grey at once; otherwise it visits each neighbour and comes back, and turns black only if none is black. The black nodes form a maximal independent set.

\(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.

A first look

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

Imagine a building with \(n\) rooms that carry no names, and \(n\) agents (small mobile computers) who must choose some rooms to stand in so that no two chosen rooms are next to each other, yet every room is either chosen or next to a chosen room. 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 \(\deg(v)\) of a node \(v\) is the number of edges at it, and \(\Delta\) is the maximum degree. Nodes have no names, but the edges at a node are numbered \(1, 2, \dots\); these numbers are ports. Each agent has a distinct identifier (ID). A set of nodes in which no two nodes are neighbours is independent; it is a maximal independent set (MIS) if no further node can be added to it without losing this. The agents move in synchronous rounds (in each round every agent may talk to the agents on its node, then move along at most one edge), and at the end every agent must know whether it stands on a chosen node. We count rounds and bits of memory per agent. As for all problems in this family, a general method is to make the agents dispersed (one agent on each node) and then let them imitate a classical message-passing algorithm by visiting their neighbours (explained under leader election by agents).

1AlgorithmDepth-first walk that colours as it settles No knowledge → Chand et al. 2023

All \(n\) agents start together on one node (a rooted start) and know nothing about the graph.

  1. The group moves through the graph in a depth-first walk: it leaves its current node by a port not tried yet when there is one, and otherwise goes back to the node from which it reached the current node. Whenever it reaches an empty node, the agent with the smallest ID among those still walking stays there for good: it becomes a settled agent, and it remembers the port by which the group came in, so the group can later walk back.
  2. Before the group moves on, the new settled agent checks its neighbours. If its parent (the node from which the walk reached it) holds a black agent, it colours itself grey. Otherwise it visits every neighbour and comes back: if some neighbour is black it becomes grey, else black.
  3. The rest of the group continues the depth-first walk; finding a settled agent on a node tells it that the node was visited before, so it turns back.
  4. When every agent has settled, the black agents form the answer.
Why it works and what it costs. A black agent never has a black neighbour, so the black nodes are independent; every grey agent has a black neighbour, so no node can be added: the set is maximal. The depth-first walk crosses each edge a constant number of times, and the neighbour checks cost \(2\deg(v)\) rounds at each node \(v\), which sums to \(4m\); so the total is \(O(m)\) rounds with \(O(\log n)\) bits per agent Chand et al. 2023. The current best without knowledge, from any start, is \(O(\max\{n\log^2 n, m\})\) rounds with \(O(\log n)\) bits Kaur et al. 2026.

Why it matters. It shows that settling agents one at a time along a depth-first walk gives a greedy algorithm for free, the same pattern as dispersion.

2Lower boundSome agent must walk almost the whole diameter No knowledge →

Let all agents start on the end \(s\) of a path with \(D+1\) nodes, so the diameter \(D\) (largest distance between two nodes) is the length of the path. Maximality says that the far end \(u\) or its only neighbour must be chosen, and a chosen node needs an agent standing on it. Both nodes are at distance at least \(D-1\) from \(s\).

Why it holds. An agent moves along at most one edge per round, so no agent reaches distance \(D-1\) before round \(D-1\): from a rooted start every algorithm needs at least \(D-1\) rounds. This simple argument is our own, not from the papers; no better lower bound is recorded in the catalogue, so the gap to the known \(O(\max\{n\log^2 n, m\})\) rounds is wide open.

Why it matters. Distance is the most basic obstacle for moving agents, and the gap between this bound and the known algorithms shows how little is known about the optimal time.

3AlgorithmGreedy by identifiers, simulated after dispersion Knowing \(n\) and \(\Delta\) → Kshemkalyani et al. 2024

Here the agents know \(n\) and \(\Delta\), which lets them use the disperse-and-simulate method.

  1. Disperse, so that every node holds one agent.
  2. Repeat simulated message-passing rounds, each made of \(O(\log n)\) blocks of \(2\Delta\) rounds in which neighbouring agents meet by the ID-bit schedule: in block \(i\) an agent whose \(i\)-th ID bit is \(1\) visits its neighbours one by one and an agent whose bit is \(0\) waits on its node (see leader election by agents).
  3. An agent joins the set as soon as every neighbour with a larger ID has decided and none of them joined; it stays out as soon as some neighbour with a larger ID joined.
  4. Each agent tells its neighbours its decision at the next meetings.
Why it works and what it costs. The agent with the largest ID decides at once, and an agent waits only for neighbours with larger IDs, so a chain of waiting agents has decreasing IDs and at most \(n\) members: at most \(n\) simulated rounds. Each costs \(O(\Delta\log n)\) real rounds, so the total is \(O(n\Delta\log n)\) plus the time to disperse, the same order as the introductory \(O(n\Delta\log n)\) bound of Pattanayak et al. 2024 (whose algorithm may differ). With \(n\) and \(\Delta\) known the current best is \(O(n\log^2 n + D\Delta\log n)\) rounds with \(O(\log n)\) bits Kshemkalyani et al. 2026.

Why it matters. It shows the cost of the generic method: a slow message-passing algorithm becomes a slow agent algorithm, which is why later work designs algorithms for agents directly.

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
No knowledge
Without knowledge: \(O(\max\{n\log^2 n, m\})\) rounds with \(O(\log n)\) bits.
unknown \(O(\max\{n\log^2 n,m\})\) vs —
unknown \(O(\log n)\) vs —
Knowing \(n\) and \(\Delta\) standard
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.
unknown \(O(n\log^2 n+D\Delta\log n)\) vs —
unknown \(O(\log n)\) vs —

What the community started looking at

MIS by agents was posed with time first, memory second: rooted and arbitrary starts, trees and grids Pattanayak et al. 2024; later work removed the knowledge of \(n\) and \(\Delta\) Kaur et al. 2026.

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 (2 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 maximal independent sets the introductory algorithm assumes \(n\) and \(\Delta\) Pattanayak et al. 2024; Kshemkalyani et al. 2024 and Kaur et al. 2026 remove the assumption.

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.