EUVIMEDEUVIMED entdecken
Crossref

Exact algorithm for network dismantling problem

Yi-Ding Men, Wen-Biao Xu, Zi-Song Shen, Pan Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →