Learn to solve dominating set problem with GNN and reinforcement learning

The Dominating Set Problem has a wide range of applications in many industrial areas and the problem has been proven to be NP-hard. The idea using neural networks to solve combinatorial optimization problems has been shown to be effective and time-saving in recent years. Inspired by these studies, to solve the Dominating Set Problem, we train a neural network by Double Deep Q-Networks (DDQN). To better capture the features and structures of the graph, we use a message passing network for the graph representation. We validate our model on random graphs of different sizes, and even on several different lattice graphs, which show our model is effective.