Exact algorithm for network dismantling problem
Communications in Theoretical Physics · 01.09.2026 · 78 (9) · 095602
DOI: 10.1088/1572-9494/ae63ae ↗Kurz gefasst
Fachartikel in der Zeitschrift Communications in Theoretical Physics, online erschienen am 26.06.2026. Verfasst von Yi-Ding Men und 3 weiteren Autor:innen. Die Arbeit nennt 41 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
The network dismantling problem (NDP), which seeks to fragment a network into subcritical components by removing a minimal set of vertices, is a fundamental challenge in complex network science with broad applications in infrastructure protection and epidemic control. Physically, the NDP maps to the problem of finding the ground state of a disordered spin system, a task known to be NP-hard. Consequently, exact solutions have remained computationally intractable for all but the smallest graphs, leaving a critical gap in evaluating the true optimality of widely used heuristic algorithms. In this work, we bridge this gap by presenting an exact dismantling algorithm based on a branch-and-bound framework. By efficiently pruning the solution space based on connected component formation, our method determines the exact ground states for regular random graphs up to 70 nodes and Erdős–Rényi graphs up to 80 nodes. These rigorous results serve as a definitive benchmark, revealing the precise optimality gap of popular approximation methods such as Collective Influence and CoreHD. Furthermore, we leverage our exact approach to optimize heuristic strategies, demonstrating a 1%–4% improvement in dismantling efficiency on larger networks.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Men, Y., Xu, W., Shen, Z., & Zhang, P. (2026). Exact algorithm for network dismantling problem. Communications in Theoretical Physics, 78(9), 095602. https://doi.org/10.1088/1572-9494/ae63ae
Vancouver
Men Y, Xu W, Shen Z, Zhang P. Exact algorithm for network dismantling problem. Communications in Theoretical Physics. 2026;78(9):095602. doi:10.1088/1572-9494/ae63ae
BibTeX
@article{Men2026,
author = {Men, Yi-Ding and Xu, Wen-Biao and Shen, Zi-Song and Zhang, Pan},
title = {Exact algorithm for network dismantling problem},
journal = {Communications in Theoretical Physics},
year = {2026},
volume = {78},
number = {9},
pages = {095602},
doi = {10.1088/1572-9494/ae63ae}
}
EUVIMED