Mobility Matters
Home›Mobile agents on graphs›Computing with agents›Minimal dominating set by agents

Minimal dominating set by agents

\(n\) agents in an anonymous graph must mark a minimal dominating set.

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 neighboursno black neighbour: 3 turns black4 settles at e; parent is black, so grey5 settles at d and visits its neighboursFinal: black a, c, d dominate, minimally
Minimal dominating set by a depth-first walk that colours as it settles Chand et al. 2023: 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. Every node is black or next to a black node, and no black node can be dropped.

\(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 mark a minimal dominating set of nodes: 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 placing first-aid kits in some rooms of a building so that every room either has a kit or is next to a room with one, and no kit can be removed without leaving some room uncovered. 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. A set of nodes is a dominating set if every node is in it or is a neighbour of a node in it; it is a minimal dominating set if removing any one node breaks this property (it need not be the smallest possible). \(n\) agents (small mobile computers) with distinct identifiers (IDs) move in synchronous rounds (in each round an agent may talk to the agents on its node, then move along at most one edge) and must mark such a set: at the end every agent knows whether its node is in the set. We count rounds and bits of memory per agent. As for all problems in this family, one general method is to place one agent on each node and then imitate a message-passing algorithm by visiting 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 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. At each empty node it reaches, the walking agent with the smallest ID stays for good, becoming a settled agent, and remembers the port leading back.
  2. The new settled agent decides its colour: if its parent (the node from which the walk reached it) holds a black agent it becomes grey; otherwise it visits all its neighbours and becomes grey if one of them is black, and black if none is.
  3. The others continue; a settled agent on a node tells them the node was visited before.
  4. When all agents have settled, the black nodes are the dominating set.
Why it works and what it costs. Every agent ends black or grey, and grey means "next to a black one", so the black nodes dominate the graph. They are also minimal: a black node has no black neighbour (all its neighbours are grey or settled after it and saw it), so removing it would leave it uncovered. In fact the black nodes form a maximal independent set, and every maximal independent set is a minimal dominating set. The walk crosses each edge a constant number of times and the checks cost \(2\deg(v)\) rounds per node \(v\), \(4m\) in total, so the algorithm takes \(O(m)\) rounds with \(O(\log n)\) bits Chand et al. 2023. The current best takes \(O(n)\) rounds, from a rooted or arbitrary start, with \(O(\log n)\) bits Chand & Molla 2026, building on a faster dispersion algorithm Kshemkalyani et al. 2025.

Why it matters. It is the template that later dominating-set and MIS algorithms for agents refine: settle agents greedily during exploration and let each settled agent decide from its neighbourhood.

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 path's length. The far end \(u\) must be dominated: \(u\) or its only neighbour must be marked, and a marked node holds an agent. Both are at distance at least \(D-1\) from \(s\).

Why it holds. Agents move along at most one edge per round, so the algorithm needs at least \(D-1\) rounds on this path. This is our own short argument; the catalogue records no lower bound, so whether the \(O(n)\) rounds of Chand & Molla 2026 are optimal is open. On a path \(D = n-1\), so on paths the \(O(n)\) algorithm is optimal up to a constant factor.

Why it matters. It shows that linear time is the right target on long, thin graphs, and that a better lower bound would need graphs with small diameter.

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 standard
A minimal dominating set in \(O(n)\) rounds with \(O(\log n)\) bits, from a rooted or arbitrary start.
unknown \(O(n)\) vs —
unknown \(O(\log n)\) vs —

What the community started looking at

Dominating sets by agents were posed with time and memory as measures Chand et al. 2023; building on optimal dispersion, linear time without any knowledge followed Chand & Molla 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 (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 minimal dominating sets the rooted algorithm of Chand et al. 2023 already needs no knowledge, and Chand & Molla 2026 removes it from the arbitrary start as well.

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.