  Spanning tree problems with specialized constraints can be difficult to solve
in real-world scenarios, often requiring intricate algorithmic design and
exponential time. Recently, there has been growing interest in end-to-end deep
neural networks for solving routing problems. However, such methods typically
produce sequences of vertices, which makes it difficult to apply them to
general combinatorial optimization problems where the solution set consists of
edges, as in various spanning tree problems. In this paper, we propose
NeuroPrim, a novel framework for solving various spanning tree problems by
defining a Markov Decision Process (MDP) for general combinatorial optimization
problems on graphs. Our approach reduces the action and state space using
Prim's algorithm and trains the resulting model using REINFORCE. We apply our
framework to three difficult problems on Euclidean space: the
Degree-constrained Minimum Spanning Tree (DCMST) problem, the Minimum Routing
Cost Spanning Tree (MRCST) problem, and the Steiner Tree Problem in graphs
(STP). Experimental results on literature instances demonstrate that our model
outperforms strong heuristics and achieves small optimality gaps of up to 250
vertices. Additionally, we find that our model has strong generalization
ability, with no significant degradation observed on problem instances as large
as 1000. Our results suggest that our framework can be effective for solving a
wide range of combinatorial optimization problems beyond spanning tree
problems.
