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

Rui Sun, Zhaohui Liu, Yiyuan Wang, Han Xiao, Jiangnan Li, Jiejiang ChenIJCAI 2025 · DOI

TL;DR

This paper introduces NuMDS, a novel local search algorithm for the Minimum Dominating Set (MDS) problem. NuMDS significantly outperforms existing state-of-the-art algorithms by employing a unique three-phase approach: a sophisticated reduction method, a two-phase vertex initialization strategy, and a dynamic multi-stage local search mechanism that adapts its search behavior based on the current progress.

What Problem Does This Paper Address?

The Minimum Dominating Set (MDS) problem is a fundamental challenge in graph theory with broad applications in areas like wireless communication, disease modeling, and computer vision. The goal is to find the smallest possible subset of vertices in a graph such that every vertex in the graph is either in the subset or adjacent to a vertex in the subset. This problem is NP-hard, meaning that finding an optimal solution is computationally intractable for large graphs. While approximation algorithms exist, they often have limited performance. Exact algorithms can solve small instances but struggle with larger ones. Therefore, efficient heuristic algorithms are crucial for practical applications. Existing heuristic approaches, while improving, still face challenges in terms of convergence speed and escaping local optima, especially on large-scale, real-world graphs.

Methods

NuMDS introduces three key innovations:

  • Dominate Propagation-Based Reduction Method (DPRM): This novel preprocessing step aims to fix the status (included or excluded) of a significant portion of vertices in an optimal solution. It leverages three types of vertex relationships (strong cover, strong ignore, and unique dominate) to effectively reduce the search space.
  • Two-Phase Initialization Method: Recognizing that dominating vertices in sparse graph regions requires more effort than in dense regions, this method first prioritizes vertices in sparse areas using k-shell decomposition and then employs a greedy approach to complete the initialization. This ensures the search starts from a more informed initial solution.
  • Multi-Stage Local Search Mechanism: Unlike previous algorithms that use a uniform search strategy, NuMDS dynamically adjusts its search behavior. In the early stages, it uses a greedy approach for faster convergence. As improvement becomes difficult, it switches sequentially to a randomized search for exploration and then an exploitation search to escape local optima. This is managed by a unimprove counter and a hybrid scoring function that considers both vertex score and its "age" (how long it hasn't been operated on).

Datasets

The paper evaluates NuMDS on a comprehensive set of benchmarks, including:

  • UDG: A widely used benchmark for MDS algorithms.
  • T1: Consists of 54 families of instances, with vertex weights set to 1.
  • DIMACS: A standard benchmark from a previous challenge.
  • BHOSLIB: Generated from the RB model.
  • SNAP: The Stanford Large Network Dataset Collection, focusing on large graphs (over 10^4 vertices).
  • DIMACS10: Another large-scale graph benchmark.
  • Network Repository: A collection of real-world graphs, with a focus on large instances (over 10^5 vertices).
  • NDR1 & NDR2: These are subsets of the Network Repository, with NDR2 including additional instances used in recent DmDS research.

In total, 428 instances were used for evaluation.

Key Insights and Ideas

  • The importance of graph structure in initialization: The paper highlights that simply using greedy approaches for initialization can overlook critical vertices in sparse graph regions, leading to suboptimal starting points. The k-shell decomposition-based priority phase in their initialization method directly addresses this.
  • Dynamic search strategies are crucial for complex problems: The multi-stage search mechanism demonstrates that adapting the search strategy (greedy, random, exploitation) based on the algorithm's progress is more effective than a one-size-fits-all approach for tackling challenging NP-hard problems like MDS.
  • Reduction methods can be significantly improved: The proposed DPRM method shows a substantial improvement in the "fix ratio" (percentage of vertices whose status is fixed) compared to existing reduction techniques, even if it incurs a slightly higher computational cost. This reduction is vital for making local search feasible on large graphs.
  • The synergy of components: The experimental results strongly suggest that the combination of DPRM, the two-phase initialization, and the multi-stage search mechanism is what makes NuMDS so effective, with each component contributing significantly to the overall performance.

Key Results

NuMDS demonstrates superior performance across all tested benchmarks.

  • Best Solutions: NuMDS finds the best minimum solution for all standard instances and significantly outperforms competitors on real-world instances. It achieves the best solution for 23 out of 31 instances on DIMACS10, and for a majority of instances on SNAP and NDR benchmarks.
  • Comparison to State-of-the-Art: NuMDS outperforms FastDS, DmDS, and DeepOpt-MWDS in finding minimal average solutions on a large number of instances.
  • Run Time: NuMDS is considerably faster than its competitors when achieving similar solution quality, as illustrated in Figure 3.
  • Comparison to Exact Algorithms: NuMDS significantly outperforms powerful exact algorithms like BIBLP and Gurobi on large-scale instances, highlighting the effectiveness of its heuristic approach.
  • Component Analysis: Ablation studies (comparing NuMDS to versions with components removed) show that DPRM and the multi-stage mechanism are indispensable for its strong performance. The two-phase initialization also proves more effective than standard greedy or perturbation methods.

Limitations and Future Work

  • Parameter Tuning: While the paper mentions using irace for parameter tuning and demonstrates that NuMDS is not overly sensitive to parameter choices, the optimal parameter values are still critical for achieving peak performance.
  • Computational Cost of DPRM: Although DPRM is effective, its time complexity is higher than some simpler reduction rules. The paper addresses this by applying the more complex Fix-Out-Set Reduction Rule 4 selectively on smaller remaining graphs.
  • Future Work: The paper doesn't explicitly detail future work directions, but the success of NuMDS suggests potential avenues for applying its core ideas (DPRM, adaptive search, and informed initialization) to other NP-hard graph problems. Further exploration into more efficient reduction techniques or adaptive strategies could also be beneficial.

Summary updated

BibTeX
@inproceedings{sun2025numds,
  author = {Rui Sun and Zhaohui Liu and Yiyuan Wang and Han Xiao and Jiangnan Li and Jiejiang Chen},
  title = {{NuMDS: An Efficient Local Search Algorithm for Minimum Dominating Set Problem}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/997},
}
Figure