NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem

The minimum dominating set (MDS) problem is a crucial NP-hard combinatorial optimization problem with wide applications in real-world scenarios. In this paper, we propose an efficient local search algorithm namely NuMDS to solve the MDS, which comprises three key ideas. First, we introduce a dominate propagation-based reduction method that fixes a portion of vertices in a given graph. Second, we develop a novel two-phase initialization method based on the decomposition method. Third, we propose a multi-stage local search procedure, which adopts three different search manners according to the current stage of the search. We conduct extensive experiments to demonstrate the outstanding effectiveness of NuMDS, and the results clearly indicate that NuMDS outperforms previous state-of-the-art algorithms on almost all instances.

Authors

• Rui Sun Deep Space Exploration Laboratory, University of Science and Technology of China
• Zhaohui Liu Beijing Tongren Hospital
• Yiyuan Wang Northeast Normal University
• Han Xiao Xiamen University
• Jiangnan Li Harbin Institute of Technology, Shenzhen; Guangdong Provincial Key Laboratory of Novel Security Intelligence Technologies
• Jiejiang Chen

Keywords

• Search: S: Combinatorial search and optimisation