Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents

The use of autonomous agents to solve graph problems has recently attracted significant attention. Such agents, representing entities like self-driving cars, drones, robots, or distributed processes, combine two defining capabilities: they can perform local computations under strict memory constraints, and they can traverse networks, moving between nodes while retaining only limited information. A crucial observation in this model is that local computation cost is essentially negligible compared to movement, as in real-world scenarios where the cost of physical traversal (for example, a self-driven car traversing across mutiple cities) far outweighs local processing. Consequently, research in this area has focused on minimising movement while still enabling efficient solutions to classical graph problems. Several fundamental graph problems, such as computing minimal dominating sets and independent sets, leader election, spanning tree construction, and community detection, have been extensively studied both in the classical distributed model and, more recently, in the mobile-agent model. For instance, dominating set construction has been investigated in the mobile-agent setting [2] and refined in subsequent works [3, 4, 5], while the closely related maximal independent set (MIS) problem has also been explored [6]. The same framework has produced algorithms for spanning structures, including BFS trees [7, 8], MSTs [3, 5], and general spanning trees [9]. These developments have further led to increasingly efficient approaches for leader election.