Solving the Minimum Dominating set Problem using an Apiary Organizational–based Optimization Algorithm

Résumé

     The Minimum Dominating Set (MDS) problem is a fundamental challenge in graph theory due to its computational difficulty and broad relevance to coverage and optimization tasks. The problem seeks the smallest subset of vertices capable of dominating all other vertices in a graph, a requirement that becomes increasingly complex as graph size and structure grow. Because the MDS problem is NP-hard, exact methods are often impractical for large or irregular graphs, which motivates the use of heuristic strategies. In this study, an adaptation of the Apiary Organizational-based Optimization Algorithm (AOOA) is employed to generate approximate solutions for selected instances of the MDS problem. The algorithm, inspired by collective behavior in bee colonies, provides a flexible search mechanism that balances exploration and exploitation. Experimental results obtained from applying the algorithm to benchmark graph instances illustrate its ability to produce competitive dominating sets within reasonable computational time. The findings highlight the value of using nature-inspired heuristics to complement theoretical analysis and provide practical insight into domination behavior across different graph structures. The results were compared with two metaheuristic algorithms: the Bees algorithm and the Genetic algorithm. The improvement ratios showed that the AOOA algorithm outperformed both, with a  improvement in minimum domination compared to  for the Bees algorithm. Regarding average time, the improvement was  for GA and  for the Bees algorithm. This demonstrates the superiority of the AOOA over the other two.