This paper introduces two innovative self-adaptive metaheuristic algorithms: Self-Adaptive Walrus Optimization Algorithm (SAWO) and Self-Adaptive Grasshopper Optimization Algorithm (SAGO), designed specifically to solve the Minimum Dominating Set Problem (MDSP) efficiently. The SAWO is inspired by natural process modeling walrus social foraging, while SAGO emulates grasshopper swarming, both of them using dynamic self-adaptation mechanisms to balance the exploration ( \(E_{x}\) ) and exploitation ( \(E_{p}\) ). The goal is to find a minimum Domination Set \(D \subseteq V\) in a graph \(G = \left( {V, E} \right),\) such that every vertex \(v \in V\) is either in D or adjacent to at least one vertex in \(D\) . Both algorithms integrate parameters of \(\left( {\alpha , \beta , \gamma } \right)\) to adapt exploration and exploitation across iterations t dynamically, this makes the search process faster. These algorithms integrated in graph theory strengthen the topology T(G). The incorporation of this algorithm in the graph theory by finding the optimal value to solve the minimum dominant set problem. The proposed algorithm enhances the graph's topology while reducing the solution space. Thus, the computational efficiency and convergence stability are highly improved. Benchmarking results show how effective they are: for \(50\) -node graphs with \(55\) edges, SAWO and SAGO achieved minimum dominating sets of size \(19\) compared to IG's \(21\) ; for \(40\) -node graphs with \(32\) edges, both algorithms reduced the solution size to \(17\) compared to IG's \(19\) ; and for \( 30\) -node graphs with \(19\) edges, SAWO matched IG with a solution size of \(14\) , while SAGO generated \(16\) . These results verify that, for a range of graph sizes and densities, SAWO and SAGO consistently produce competitive or better solutions. The results show SAWO and SAGO as robust methods for solving NP-hard problems, with possible weighted and dynamic graph extensions for future work.
