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}=(\mathcal{V},\mathcal{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…