Maximal Independent Set via Mobile Agents

We consider the problem of finding a maximal independent set (MIS) in an unknown graph by mobile agents or mobile robots. Suppose n mobile agents are initially located at arbitrary nodes of an n-node anonymous graph G = (V, E) and the goal is that the agents autonomously relocate themselves to find a subset S ⊂ V of nodes such that S forms an MIS. The objective is to minimize both (i) the time required to find an MIS and (ii) the memory required at each agent. We consider the mobile agents with communicate-compute-move model in the synchronous setting, in which agents can communicate with other agents if they are located at the same node (called local communication).

We present deterministic algorithms for finding MIS on various graph classes (e.g., general graphs, trees, grids) in our robot model. Additionally, we consider different initial configurations of the agents over the nodes. Specifically, we present algorithms for three different initial configurations: rooted (all agents are positioned at the same node), dispersed (one agent at each node), and arbitrary (agents positioned at multiple nodes, except in the dispersed configuration). For general graphs, our algorithm finds MIS in O(nΔ) time and uses O(log n) bits of memory per agent in the rooted initial configuration, where Δ represents the maximum degree of the graph. The algorithms for the dispersed and arbitrary initial configurations require O(nΔlog n) time and O(log n) bits of memory, but necessitate prior knowledge of n and Δ. For trees, our algorithms find MIS in: (i) O(D2) time and O(log n) bits of memory per agent in the rooted configuration, where D is the diameter of the tree, (ii) O(D) time and O(Δ + log n) bits of memory per agent in the dispersed configuration, requiring the knowledge of Δ, and (iii) O(n) time and O(Δ + log n) bits of memory per agent in the arbitrary configuration, where knowledge of both n and Δ is required. Lastly, for rectangular grids with n = x × y nodes, our algorithm finds MIS in O(max (x, y)) time and O(log n) bits memory per agent, requiring the knowledge of x, y. The algorithm is simultaneously time and memory optimal.

To the best of our knowledge, this is the first time where the maximal independent set problem is explored through the lens of mobile agents in the local communication model.