Learn to solve dominating set problem with GNN and reinforcement learning

Mujia Chen, Sihao Liu and Weihua He

Applied Mathematics and Computation, 2024, vol. 474, issue C

Abstract: 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.

Keywords: Combinatorial optimization; Dominating set problem; Graph neural network; Reinforcement learning (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324001899
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:474:y:2024:i:c:s0096300324001899

DOI: 10.1016/j.amc.2024.128717

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().