A Reinforcement Learning-Based Approach for the Minimum Dominating Set Problem

Abstract

Computer science and operational research use combinatorial optimization to generate optimal results among limited problem sets. This optimization method serves as the backbone for numerous practical difficulties to find solutions from finite options within scheduling and resource allocation and network design fields. The basic challenge in this domain deals with the Minimum Dominating Set (MDS) issue to identify the minimum collection of graph nodes that either contain themselves or connect to a member of the subset. Exact algorithms fail to address large MDS problem instances since it belongs to the NP-hard class of computational problems.

The MDS problem finds application across multiple domains that include wireless sensor networks as well as social influence modeling and biological networks and security monitoring systems. The research community has presented multiple solution approaches due to MDS problem's computational difficulty. Modern approaches using artificial intelligence and machine learning algorithms obtain their problem-solving abilities from training data to solve large or dynamic graph environments with adaptive methods that perform strongly.

A solution method for MDS problem will be developed through reinforcement learning which integrates deep neural networks and graph embedding approaches. An AI model needs to demonstrate its ability to efficiently produce high-quality optimal solutions on top of achieving wide-reaching scalability.