Representation of Dominating Set Variants Using Dataless Neural Networks

A Dominating Set in a simple graph \(G=(V,E)\) is a set \(D\subseteq V\) such that for each vertex \(v\in V\) , either \(v\in D\) or one of its neighbors is in D. The objective of the Dominating Set problem is to find a Dominating Set of minimum cardinality in a given graph \(G=(V,E)\) . It is a well studied problem in the literature and known to be NP-hard. In this paper, we explore the Dominating Set problem and one of its variants known as the Vertex-Edge Dominating Set problem through the lens of dataless neural networks. We develop differentiable functions for both of these problem instances within the framework of dataless neural networks. Notably, a recent breakthrough demonstrated that a single differentiable function within a dataless neural network can effectively address the Maximum Independent Set problem. Drawing inspiration from this achievement, we craft dataless neural network solutions for the Dominating Set and Vertex-Edge Dominating Set problems. Furthermore, we also establish the correctness of our derivations in a rigorous fashion.