这篇论文告诉你如何用强化学习搞定一个NP难的图论问题，效果比传统贪心算法好，适合研究图神经网络和组合优化的人。
该论文提出SD-ZFS框架，将S2V-DQN架构适配到最小零强制集(ZFS)问题。ZFS是NP难的图着色问题，在图神经网络、网络控制和逻辑电路设计中有应用。在多个不同结构的图数据集上训练模型，评估其泛化、扩展和迁移能力。与最优解和贪心启发式相比，SD-ZFS框架展示了有效性。
Deep Reinforcement Learning for Minimum Zero-Forcing Sets
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.