NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem
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.
Cite
Text
Sun et al. "NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/997Markdown
[Sun et al. "NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/sun2025ijcai-numds/) doi:10.24963/IJCAI.2025/997BibTeX
@inproceedings{sun2025ijcai-numds,
title = {{NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem}},
author = {Sun, Rui and Liu, Zhaohui and Wang, Yiyuan and Xiao, Han and Li, Jiangnan and Chen, Jiejiang},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {8966-8976},
doi = {10.24963/IJCAI.2025/997},
url = {https://mlanthology.org/ijcai/2025/sun2025ijcai-numds/}
}