A hybrid local search algorithm for minimum dominating set problems. (September 2022)

• Record Type: Journal Article
• Authors: Abed, Saad Adnan; Rais, Helmi Md; Watada, Junzo; Sabar, Nasser R.
• Is Part Of: Engineering applications of artificial intelligence. Volume 114(2022)
• Publication Date: 2022-09
• Subjects: Minimum dominating set -- Minimum positive influence dominating set -- Local search -- Meta-heuristic -- Greedy methods; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2022.105053
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: Minimum dominating set (MDS) is a well-known NP-hard fundamental graph theory problem having many applications such as mining social networks and bioinformatics. MDS seeks for the minimum subset of vertices in which every vertex not in the selected subset is adjacent to at least one vertex of this subset. In this study, we consider MDS and a complex variant of MDS known as the minimum positive influence dominating set (MPIDS). In MPIDS, the aim is to identify a subset of vertices where each vertex of a graph must be dominated by at least half of its neighbors. To solve these problems, we propose a two-stage hybrid local search algorithm. In the first stage, we propose an adaptive information content-based local search algorithm as an exploratory procedure. This algorithm focuses on generating promising solutions in different areas of the solution space using the problem search history. Moreover, we introduce information content strategy-based neighborhood structure and tolerance-based features to evolve high-quality and diverse solutions. For the second stage, we propose a gain-based deterministic local search algorithm as an exploitation procedure. It navigates feasible neighborhood areas to improve the solution quality. We conducted extensive analysis to evaluate the impact of the proposed components. The proposed algorithm produced very good results and generalized well overall instances of both MDS and MPIDS. Compared to the literature, the proposed algorithm outperformed other algorithms in most of the tested instances. Highlights: A hybrid local search algorithm to address large scale MDS and MPIDS instances. An adaptive exploration procedure to locate promising solutions. An effective intensification procedure to improve solution quality. An information content based neighborhood structure to generate new solutions.