Learning-Based Heuristic for Combinatorial Optimization of the Minimum
  Dominating Set Problem using Graph Convolutional Networks
Abihith Kothapalli Mudassir Shabbir Xenofon Koutsoukos
A dominating set of a graph $\mathcal{G=(V, E)}$ is a subset of vertices
$S\subseteq\mathcal{V}$ such that every vertex $v\in \mathcal{V} \setminus S$
outside the dominating set is adjacent to a vertex $u\in 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.