RGF: Recursive Generative Framework for the Edge-Cut Separable Problems

The Maximal Independent Set (MIS), Dominating Set (DS), and Vertex Cover (VC) problems are fundamental combinatorial optimization problems with wide-ranging applications. We identify a key property of these problems: by finding a cut in the graph and determining the states of vertices associated with the cut, the graph can be decomposed into multiple subgraphs whose solutions are independent of each other. Therefore, we classify MIS, DS, and VC as Edge-Cut Separable Problems (ECSPs). This property enables a natural divide-and-conquer strategy, which significantly reduces the computational complexity and allows neural networks to scale to large-scale graphs that were previously intractable. Based on this property, we propose a recursive framework that leverages this property to approximately solve ECSPs, namely \ours. Our framework consists of two major components: a partitioner that identifies a cut in the graph, and a predictor that solves the cut-determination sub-problem (CDSP) to determine the states of vertices associated with the cut. By recursively applying these components, RGF generates a complete solution for the original ECSP instance. Additionally, through partial prediction, the memory consumption is significantly reduced, enabling RGF to handle real-world large graphs. Experimental results validate the advantages of RGF: the performance of our method is up to 2.13\% better than the state-of-the-art machine learning (ML)-based approach, and our approach can handle real-world large graphs with up to 11M vertices.