TermiNet: A reinforcement learning framework for k-Path partitioning problem

The k-path partition (kPP) problem has been widely used in routing and scheduling, which aims to partition all vertices of a graph into a minimum number of vertex-disjoint paths, each constrained by a capacity limit. Although it has broad applications, the kPP problem is NP-hard, and traditional algorithms often lack efficiency and generalization. In this paper, we propose TermiNet, the first deep reinforcement learning framework for kPP. It constructs paths in an auto-regressive manner, capturing the temporal dependencies in the path construction process. A learnable termination strategy is also integrated, enabling the model to determine when to terminate each path, effectively reducing the number of paths. Experimental results show that TermiNet achieves competitive performance in large-scale graphs, underscoring the scalability and adaptability of reinforcement learning-based graph partitioning methods.