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.
Rooted start, no knowledge
verifiedFrom a rooted start without knowledge of \(n\) or \(\Delta\), an MIS takes \(O(n\Delta)\) rounds with \(O(\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: rooted start
- All \(k\) agents start at the same node (\(\ell=1\)). Also called co-located (black hole search: all agents at the home base) or a rooted graph Molla & Moses Jr. 2019.
- Topology: any topology
- \(G\) is any connected graph in the class allowed by the other axes.
What is known
Results, in order of publication
Introductory and current best (Theorem 3.1, Algorithm MIS-GraphRooted): a depth-first traversal that settles one agent on each new node, while the unsettled agents visit the neighbours of that node to learn whether one of them is already in the set; at most \(4m\) rounds of traversal and \(2\delta\) rounds of visits at a node of degree \(\delta\). No knowledge of graph parameters. On trees, \(O(D^2)\) rounds with \(O(\log n)\) bits (Theorem 4.2).
Open questions
None recorded for this variant.
Notes
The rooted start is all \(n\) agents on one node (initial axis of the model). From the same start, Kshemkalyani et al. 2024 need \(O(n\Delta)\) rounds and \(O(n\log n)\) bits (Theorem 20), which this result dominates. Checked against the full text of Pattanayak et al. 2024.
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.