基于强化学习的最小全支配集问题求解框架

A Reinforcement Learning Framework for Minimize Total Dominating Set Problem

摘要: 最小全支配集(MinimumTotal Dominating Set, MTDS)问题旨在在图中寻找一个最小顶点集合，使得每个顶点至少与集合中的一个顶点相邻，该问题在网络监测与故障检测等领域具有广泛应用。针对现有启发式方法在复杂图结构下性能受限的问题，本文提出了一种基于深度强化学习的端到端求解方法。该方法采用自回归方式逐步生成候选解，并利用消息传递神经网络刻画图结构中的局部依赖关系，以指导节点选择决策。此外，本文设计了一种新的奖励函数，对解的构造过程进行约束，从而保证结果的可行性与有效性。实验结果表明，该方法在不同规模和结构的图上的解质量均优于多种经典启发式算法。

Abstract: Finding a Minimum Total Dominating Set (MTDS)—a minimal vertex set where every graph node has a neighbor in the set—is a critical task in network monitoring and fault detection. However, existing heuristic approaches often suffer from limited scalability on complex graph structures. To overcome this, this paper presents an end-to-end deep reinforcement learning solver. The proposed model operates in an autoregressive manner, utilizing a Message Passing Neural Network (MPNN) to encode local topological dependencies and guide decision-making. Additionally, we design a constraint-aware reward function to regulate the solution construction process, ensuring both feasibility and effectiveness. Experimental results confirm that our method achieves superior solution quality compared to standard baselines across a wide range of graph sizes and configurations.