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

Sun, Rui; Liu, Zhaohui; Wang, Yiyuan; Xiao, Han; Li, Jiangnan; Chen, Jiejiang

doi:10.24963/ijcai.2025/997

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

Rui Sun, Zhaohui Liu, Yiyuan Wang, Han Xiao, Jiangnan Li, Jiejiang Chen

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8966-8976.

https://doi.org/10.24963/ijcai.2025/997

Keywords

Search: S: Combinatorial search and optimisation

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.

Rui Sun, Zhaohui Liu, Yiyuan Wang, Han Xiao, Jiangnan Li, and Jiejiang Chen. 2025. NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8966–8976. https://doi.org/10.24963/ijcai.2025/997

@inproceedings{ijcai2025p997,
  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 = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {8966--8976},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/997},
  url       = {https://doi.org/10.24963/ijcai.2025/997},
}

TY  - CPAPER
TI  - NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem
AU  - Sun, Rui
AU  - Liu, Zhaohui
AU  - Wang, Yiyuan
AU  - Xiao, Han
AU  - Li, Jiangnan
AU  - Chen, Jiejiang
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 8966
EP  - 8976
DO  - 10.24963/ijcai.2025/997
UR  - https://doi.org/10.24963/ijcai.2025/997
ER  -