Learning to solve the minimum dominating set problem via graph neural networks and hybrid decoding

Abstract

This paper proposes a learning-assisted framework for the Minimum Dominating Set problem that integrates Graph Neural Network-based node scoring with a heuristic optimization method. The proposed framework combines supervised GraphSAGE-based node scoring with optimization-oriented decoding and refinement procedures by using a supervised GraphSAGE model trained on sampled subgraphs. The predicted node scores are used to construct feasible dominating sets. By integrating learned node scoring with deterministic combinatorial optimization, the proposed approach improves robustness, scalability, and solution quality across different graph structures. We evaluate the proposed approach on a diverse collection of synthetic graph families and real-world benchmark datasets.