[Paper] Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents
Source: arXiv - 2511.19880v1
Overview
A new paper by Chand and Molla shows how a swarm of simple, memory‑limited mobile agents can compute a minimal dominating set (mDS) on any connected graph in linear time—that is, in (O(n)) synchronous rounds for an (n)-node network. The result pushes the state‑of‑the‑art for distributed graph algorithms that run on autonomous agents, while also delivering a spanning‑tree construction and leader election “for free.”
Key Contributions
- Linear‑time mDS algorithm for anonymous graphs using only (O(\log n)) bits of memory per agent.
- Works from both rooted and arbitrary initial placements of agents, requiring no global knowledge (e.g., graph size, diameter).
- Simultaneously builds a spanning tree and elects a unique leader in the same (O(n)) rounds.
- Extends the optimal dispersion algorithm (previously used for robot placement) to solve a classic domination problem.
- Provides a clean, synchronous mobile‑agent model that can be directly mapped to software agents, drones, or IoT devices.
Methodology
- Model – Agents are identical, have finite local memory, and move synchronously along edges. The graph is anonymous: nodes have no IDs, and agents cannot rely on global parameters.
- Dispersion Backbone – The authors start from a recent optimal dispersion routine that spreads agents so that each node ends up with at most one agent. This routine already guarantees an (O(n)) schedule and uses only (O(\log n)) bits.
- Dominating‑Set Extraction – While dispersing, agents record a lightweight “parent” pointer that implicitly defines a spanning tree rooted at the first agent that settles.
- Local Decision Rules – Once the tree is formed, each agent decides locally whether to join the dominating set: an agent becomes part of the mDS if none of its children are already in the set and if it has at least one neighbor not yet dominated. This rule mirrors the classic greedy construction of a minimal dominating set but is executed in parallel across the tree.
- Leader Election & Tree Completion – The root of the tree naturally becomes the leader. Because the tree spans all nodes, the leader can be used to coordinate any follow‑up tasks (e.g., data aggregation).
All steps are designed to require only constant‑time local computation per round, keeping the overall schedule linear.
Results & Findings
| Metric | Achieved | Prior Best |
|---|---|---|
| Time (rounds) | (O(n)) | (O(n \log n)) or higher in earlier mobile‑agent mDS algorithms |
| Memory per agent | (O(\log n)) bits | Same order, but earlier solutions needed extra global knowledge |
| Assumptions | No prior knowledge of (n), graph diameter, or node IDs | Some prior works required at least one of these |
| Additional outputs | Spanning tree + unique leader | Usually separate algorithms needed |
The theoretical analysis confirms that the algorithm never exceeds linear rounds, even in worst‑case topologies such as long paths or dense meshes. Moreover, the dominating set produced is minimal (no proper subset dominates the graph) though not necessarily minimum (smallest possible size), which matches the classic trade‑off for distributed settings.
Practical Implications
- Robotics & Drone Swarms – A fleet of low‑cost drones can autonomously organize themselves to monitor an area (the dominating set) while maintaining a communication backbone (the spanning tree).
- IoT Network Management – Tiny edge devices can elect a coordinator and decide which nodes should stay awake to act as relays, saving energy without a central controller.
- Fault‑Tolerant Service Placement – In cloud or edge clusters, the algorithm can quickly decide a minimal set of servers to host a critical service while ensuring every client is adjacent to at least one host.
- Self‑Healing Networks – When nodes join or leave, the same dispersion‑based routine can be rerun locally, guaranteeing that the dominating set and tree adapt in linear time.
- Simplified Protocol Stacks – Because the algorithm needs only (O(\log n)) bits per agent, it can be implemented on microcontrollers with very limited RAM, making it attractive for constrained environments.
Limitations & Future Work
- Minimal vs. Minimum – The algorithm guarantees a minimal dominating set, which may be larger than the optimal (minimum) one. Future work could explore approximation guarantees while preserving linear time.
- Synchronous Assumption – Real‑world deployments often experience asynchrony, message loss, or variable travel times. Extending the technique to asynchronous or partially synchronous models is an open challenge.
- Dynamic Graphs – The current analysis assumes a static topology. Handling edge/node churn without restarting the whole dispersion process would broaden applicability.
- Empirical Evaluation – The paper focuses on theoretical bounds; experimental validation on real robot swarms or network testbeds would help quantify overheads (e.g., communication cost, energy consumption).
Overall, the work demonstrates that even with severely limited local resources, mobile agents can solve classic graph problems efficiently—a promising direction for the next generation of autonomous, distributed systems.
Authors
- Prabhat Kumar Chand
- Anisur Rahaman Molla
Paper Information
- arXiv ID: 2511.19880v1
- Categories: cs.DC, cs.DS, cs.MA, cs.RO
- Published: November 25, 2025
- PDF: Download PDF