Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the NP-hard problem of finding minimum zero-forcing sets in undirected graphs by introducing a reinforcement learning framework called SD-ZFS, which adapts the S2V-DQN architecture for this specific challenge. The authors train and evaluate multiple models across various graph datasets, revealing that the SD-ZFS framework outperforms both optimal solutions and greedy heuristics in terms of efficiency and scalability. Key findings indicate that the structure of the network significantly influences the performance of the models, providing new insights into machine learning applications for graph-based problems.
Reinforcement learning can effectively tackle the NP-hard minimum zero-forcing set problem, outperforming traditional methods in diverse graph structures.
This paper explores the problem of finding the minimum zero-forcing set on undirected graphs and proposes an adapted machine-learning framework to solve the problem. The minimum zero-forcing set problem is a graph coloring problem where the color of an initial set of nodes propagates throughout a network. The set of nodes is zero-forcing if it forces all uncolored nodes to change color under the constraint of the color-change rule. There are several applications to this problem across different domains such as network science, network control, and designing logical circuits. Finding the minimum zero-forcing set is shown to be NP-hard. We propose a reinforcement learning framework, SD-ZFS, that adapts the S2V-DQN architecture to the ZFS problem. We train several models on this adapted framework and analyze the performance across graph datasets that have varying structures. We evaluate how the models trained on the framework generalize, scale, and transfer to different network types. The results demonstrate the effectiveness of the framework when compared against the optimal solution and greedy heuristic. We provide further insight into how the ZFS problem can be solved through machine-learning and the influence of network structure on the problem.