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

These optimization problems offer a means to model highly intricate discrete decision problems across diverse domains where pairwise interactions play a crucial role, such as social network analysis [1], wireless communications [2], operations research [3], scheduling [4], and transportation [5]. A considerable portion of these problems belongs to the broader class of NP-hard problems, where it is challenging to find exact solutions, as doing so often necessitates a near-complete enumeration of the entire search space. Consequently, computation of exact solutions is practically infeasible, and approximation or heuristic algorithms are generally favored for practical applications. Although these algorithms exhibit significantly faster runtime and possess sub-exponential theoretical complexities, they often yield suboptimal solutions. Therefore, a key area of research revolves around the development of approximation or heuristic algorithms that can provide solutions that are as close to optimal as possible. The minimum dominating set (MDS) problem is an important network-based optimization problem that involves finding the smallest dominating set of a given graph. A dominating set of a graph is a subset of the vertices in the graph such that every vertex is either in the dominating set or adjacent to a vertex in the dominating set. The MDS problem aims to find the dominating set of minimum cardinality. Dominating sets have a wide range of applications in various fields, including social networks [6-8], cybersecurity [9], biological networks [10], bioinformatics [11], multi-document summarization [12], and wireless sensor networks [13]