A Systematic Experimental Comparison of Exact, Greedy, Local Search, Metaheuristic, and Distributed Algorithms for the Minimum Dominating Set Problem

The Minimum Dominating Set (MDS) problem is an NP-hard optimization problem that aims to find the smallest dominating set of nodes encompassing all nodes of a graph. Because it is equivalent to the cluster covering problem, approximate solutions better than the multiplier (1−ε)lnn cannot be obtained in polynomial time unless P = NP. This work presents a comprehensive comparison of ten representative methods selected from six algorithm families (exact ILP, greedy and degree-based heuristics, configuration-controlled local search, genetic algorithm, ant colony optimization, binary particle swarm optimization, simulated annealing, enhanced binary whale optimizer, and synchronous distributed greedy algorithm) in a single, reproducible experimental framework. Experiments were performed on a total of 110 benchmark graphs consisting of five real-world networks and nine random graph models; stochastic methods were evaluated with 30 independent runs, and ILP optima were used as a quality reference. Statistical analyses show significant performance differences between the algorithms (Friedman χ²(9) = 69.6, p = 1.8×10⁻¹¹). Configuration-checking local search was the most successful approximate method, reaching the optimum solution in most instances, followed closely by ant colony optimization and genetic algorithm. While exact ILP produced fast solutions up to approximately 200 nodes, it ran into time constraints in larger and denser graphs; at these scales, metaheuristic methods were the most feasible option. Furthermore, it was shown that the genetic algorithm could be sped up by 1.7–2.5× with parallelization, while the distributed algorithm could operate with low communication costs in large-scale networks with an approximately 14% loss in solution quality.. The results reveal in detail the trade-offs in solution quality, runtime, and memory usage between different algorithms.