NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem
Rui Sun, Zhaohui Liu, Yiyuan Wang, Han Xiao, Jiangnan Li, Jiejiang Chen
Abstract
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.
BibTeX
@inproceedings{ijcai2025_numdsanefficient,
title = {NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem},
author = {Rui Sun and Zhaohui Liu and Yiyuan Wang and Han Xiao and Jiangnan Li and Jiejiang Chen},
booktitle = {IJCAI 2025},
year = {2025}
}