A Distributed Algorithm for Constructing an Independent Dominating Set

Abstract

Given a simple finite undirected graph, finding a minimum Independent Dominating Set is a fundamental graph algorithmic problem. In this paper, we propose a distributed algorithm for constructing an independent dominating set (IDS) in the CONGEST model of distributed computing. Our algorithm requires only 2-hop partial information at each node for computations, and hence each node takes various decisions without having any global knowledge of the graph. The algorithm consists of mainly three steps. First, we construct a dominating set using a node estimation and voting mechanism. Then each dominating node finds out a vertex cover of its 2-hop graph by an incremental greedy algorithm along with a few optimizations and tie breaking. We prove that the union of the vertex covers computed by each dominating node is a vertex cover of the original graph. Finally, we construct an independent set by complementing the vertex cover. Considering this independent set as an IDS (of the induced graph by the closed neighborhood of the independent set), its closed neighborhood is deleted from the original graph to construct the reduced graph. We repeat the above three-step process until the reduced graph is null. To the best of our knowledge, this is the first distributed algorithm for constructing an IDS. We experimented on eight real-world networks and synthetic networks from well-known Erdos-Renyi graph generators. We observe that in most of the cases our algorithm takes only a few (approx 5) iterations and returns an IDS whose size is fractionally higher than the size of IDS computed by a sequential greedy algorithm. © 2022, Springer Nature Switzerland AG.