Abstract

Finding an optimal subset of nodes to dismantle a complex network is a fundamental NP-hard problem. Existing algorithms typically yield only a single solution, limiting their practical use. To address this, we introduce Generative Flow Dismantling (GFD), a novel framework based on Generative Flow Networks (GFlowNets), which reformulates the dismantling task as a learnable, sequential sampling process. Trained on small synthetic networks, GFD generalizes to diverse real-world scenarios, efficiently producing a diverse set of high-quality dismantling strategies. Our data-driven analysis of these solutions reveals a key insight: the quality of a final dismantling set is more strongly correlated with the mean degree of the nodes in the initial decycling set than with its size alone. Leveraging this, we develop two enhanced variants, GFD-edges and GFD-nodes, that further improve solution quality and dismantling speed. By exploring the full landscape of diverse, high-quality solutions, our work establishes a new paradigm for network dismantling, offering a flexible and powerful framework with broad implications for understanding and enhancing network resilience.

DOI: https://doi.org/10.1016/j.chaos.2025.117526