# Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks

arXiv: https://arxiv.org/abs/2306.03434 · HTML: https://mlsanity.com/paper/2306.03434/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 64 references that are in the map.
- First posted on arXiv 6 Jun 2023.

## Builds on (most cited first, 11 of 11)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [Temporal Graph Kernels for Classifying Dissemination Processes](https://mlsanity.com/paper/1911.05496/) (2019)
- [Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs](https://mlsanity.com/paper/2003.04819/) (2020)
- [An Order-based Algorithm for Minimum Dominating Set with Application in Graph Mining](https://mlsanity.com/paper/1705.00318/) (2017)

## Built on by (most cited first, 1 of 1)

- [Heuristic Algorithm-based Action Masking Reinforcement Learning (HAAM-RL) with Ensemble Inference Method](https://mlsanity.com/paper/2403.14110/) (2024)

## Abstract (arXiv)

A dominating set of a graph G=(V, E) is a subset of vertices SsubseteqV such that every vertex v∈ V setminus S outside the dominating set is adjacent to a vertex u∈ S within the set. The minimum dominating set problem seeks to find a dominating set of minimum cardinality and is a well-established NP-hard combinatorial optimization problem. We propose a novel learning-based heuristic approach to compute solutions for the minimum dominating set problem using graph convolutional networks. We conduct an extensive experimental evaluation of the proposed method on a combination of randomly generated graphs and real-world graph datasets. Our results indicate that the proposed learning-based approach can outperform a classical greedy approximation algorithm. Furthermore, we demonstrate the generalization capability of the graph convolutional network across datasets and its ability to scale to graphs of higher order than those on which it was trained. Finally, we utilize the proposed learning-based heuristic in an iterative greedy algorithm, achieving state-of-the-art performance in the computation of dominating sets.