1. Introduction
Networks—encompassing social, biological, technological, and information systems—serve as foundational tools for modeling and analyzing complex infrastructures and their functionalities. A critical challenge in this domain is the network dismantling problem (NDP) [1], which investigates how to effectively partition a network into smaller, subcritical subgraphs by deleting a minimal set of vertices and their adjacent edges. This problem lies at the intersection of network science, computer science, and statistical physics, offering profound insights into the structural robustness and controllability of complex systems [2]. Beyond its theoretical significance, network dismantling has far-reaching practical applications in diverse fields, including safeguarding critical infrastructure [3, 4], optimizing communication networks [5, 6], controlling epidemic spreading [7–9], and strategic influence maximization in social or commercial contexts [10, 11].
The NDP admits a natural formulation within the framework of statistical mechanics, mapping to the search for the ground state of a disordered system—a process intimately tied to the site percolation transition [4, 5]. Given a network G = (V, E), the objective is to identify a minimal subset ${V}^{{\prime} }\subset V$ whose removal fragments the network into disconnected components no larger than a threshold C. In the language of statistical physics, the system’s behavior at thermal equilibrium is governed by the Boltzmann distribution. For a configuration S = {s1,…, sN} ∈ {+1, −1}N—where Si = +1 denotes a retained vertex and Si = −1 denotes a removed vertex—the probability P(S) is determined by the system’s energy E(S) and the inverse temperature β: 1 ) is introduced solely to establish the statistical-mechanical correspondence of the NDP: the minimum dismantling set (MDS) coincides with the ground-state configuration in the zero-temperature limit β → ∞, where P(S) concentrates on the global minimum of E(S). The present work targets this ground state directly through a deterministic branch-and-bound search, without sampling at any finite temperature. The inverse temperature β therefore plays a conceptual rather than operational role and does not enter any step of Algorithm 1 . In the context of the C-dismantling problem [1], the energy function (or Hamiltonian) E(S) enforces the connectivity constraint while penalizing the removal of nodes. It can be defined as:
$\begin{eqnarray}P({\boldsymbol{S}})=\frac{1}{Z}{{\rm{e}}}^{-\beta E({\boldsymbol{S}})}\ .\end{eqnarray}$
Here, Z = ∑ Se−βE(S) is the partition function that normalizes the distribution over all possible states. We emphasize that the Boltzmann distribution in equation ( $\begin{eqnarray}E({\boldsymbol{S}})=\left\{\begin{array}{ll}\infty ,\quad & \,\rm{if}\,\,\,\rm{LCC}\,(G,{\boldsymbol{S}})\gt C\\ | {{\boldsymbol{S}}}_{-}| -| {{\boldsymbol{S}}}_{+}| ,\quad & \,\rm{if}\,\,\,\rm{LCC}\,(G,{\boldsymbol{S}})\leqslant C\end{array}\right.,\end{eqnarray}$
where LCC(G, S) denotes the size of the largest connected component in the residual network, and ∣S+∣ and ∣S−∣ represent the number of retained and removed vertices, respectively. The constant C defines the target fragmentation threshold [12]. Under this formulation, the optimal solution—known as the MDS—corresponds to the ground state configuration that minimizes the removal cost while satisfying the topological constraint: $\begin{eqnarray}\,\rm{MDS}\,=\left\{S\subset V| | S| =\mathop{\min }\limits_{{S}^{{\prime} }}\left\{| {S}^{{\prime} }| :| \,\rm{LCC}\,(G\setminus {S}^{{\prime} })| \leqslant C\right\}\right\},\end{eqnarray}$
where S is a dismantling set.Since finding the exact MDS is an NP-hard problem, previous research has predominantly focused on heuristic algorithms. Early approaches relied on centrality measures, such as the highest-degree (HD) adaptive attack [3, 4]. More sophisticated methods have leveraged the Bethe approximation and message-passing techniques, including Min-Sum [1] and belief propagation decimation (BPD) [13]. Spectral methods offer another avenue; for instance, Collective Influence (CI) [14] utilizes the principal eigenvector of the non-backtracking matrix approximated via l-length walks, while CoreHD [15] recursively targets high-degree nodes within the network’s 2-core. Theoretical connections between these spectral operators and belief propagation (BP) have been further elucidated in [16], and recent work has explored factor graph representations to enhance these algorithms [17]. Additionally, machine learning paradigms have emerged, such as Graph Dismantling with Machine Learning (GDM) [18] and deep reinforcement learning approaches like FINDER [19].
While these heuristic algorithms demonstrate scalability and strong performance on large networks, they inherently lack optimality guarantees. Despite the abundance of approximate methods, the precise deviation of their solutions from the true mathematical optimum remains largely uncharacterized due to the computational intractability of finding exact solutions. However, exact benchmarks are indispensable for several reasons. First, they provide the ground truth necessary to rigorously assess the ‘optimality gap’ of heuristic and approximation algorithms. Second, they reveal the absolute limits of network robustness, offering fundamental insights into structural vulnerabilities. Third, for mission-critical applications such as national security and infrastructure protection, deterministic and reliable solutions are often required over probabilistic approximations. To the best of our knowledge, the systematic investigation of exact solutions for the NDP has been limited.
In this work, we address this gap by developing an exact algorithm based on the branch-and-bound technique [20]. Although the worst-case complexity remains exponential, our approach efficiently prunes the search space, allowing us to: (1) guarantee optimal solutions for networks of tractable size (typically 50–80 vertices), and (2) provide a rigorous baseline for comparing heuristics. Furthermore, we demonstrate that our exact solver can be integrated into a hybrid framework to refine heuristic solutions on larger networks. Although computational constraints prevent full execution on massive graphs, our algorithm consistently yields superior intermediate solutions within practical time limits compared to pure heuristics.
The remainder of this paper is organized as follows. In section 2 , we conduct a critical review of existing heuristic approaches, examining their methodological foundations. section 3 introduces the theoretical framework of our exact branch-and-bound algorithm. In section 4 , we present experimental results in three phases: validating the exact solver on small random networks, scaling an approximate variant to larger networks (up to 100 vertices) where it outperforms state-of-the-art heuristics, and applying a hybrid strategy to large-scale networks (up to 2000 vertices) to achieve performance gains of 1%–4%. Finally, section 5 synthesizes our findings and outlines directions for future research.
2. Previous heuristic algorithms
One major category of algorithms builds upon BP, a message-passing framework rooted in the Bethe approximation (or the replica-symmetric cavity method). Prominent examples include Min-Sum [1] and BPD [13]. Min-Sum exploits the correspondence between the network’s 2-core and the existence of cycles, targeting vertices specifically to break loops. Similarly, BPD is based on the observation that a network can be properly oriented—with all edges assigned a direction and at most one outgoing edge per vertex—if and only if the network comprises trees, c-trees, or a hybrid structure of both. While both algorithms yield high-quality solutions by directly implementing BP decimation, they are computationally intensive due to the iterative nature of message passing.
To address computational scalability, spectral methods based on the non-backtracking matrix B [23, 24] have been introduced. The non-backtracking matrix serves as a linear operator that linearizes the BP equations and has found wide applications in community detection and neural networks [16, 25, 26]. The CI algorithm [14] utilizes this operator to define a node’s importance. The CI strength at level ℓ, denoted as CIℓ(i), is given by:
$\begin{eqnarray}{\,\rm{CI}\,}_{\ell }(i)=({d}_{i}-1)\displaystyle \sum _{j\in {\partial }_{i}^{\ell }}({d}_{j}-1),\end{eqnarray}$
where di is the degree of vertex i, and ${\partial }_{i}^{\ell }$ is the set of vertices at a distance ℓ from i. By removing nodes with the highest CIℓ, the algorithm aims to rapidly decrease the leading eigenvalue of B, thereby shattering the giant component.A further simplification is provided by the CoreHD algorithm [15], which iteratively removes the HD nodes located specifically within the 2-core of the network. The 2-core is the maximal subgraph where every vertex has a degree of at least 2. The rationale behind CoreHD is that the leading eigenvalue of the non-backtracking matrix is asymptotically controlled by the 2-core structure [16]. Consequently, targeting high-degree nodes within the 2-core is often more effective than global degree-based attacks, as high-CI nodes may sometimes reside outside the dense core.
Recently, machine learning approaches have also been explored. FINDER [19] employs graph neural networks and deep reinforcement learning to autonomously learn effective node removal strategies. In contrast, GDM [18] utilizes supervised learning, training on small instances solved by brute-force methods. Both approaches have demonstrated the ability to outperform CI in certain regimes, albeit without theoretical guarantees of optimality.
3. Exact algorithm
3.1. Branch-and-bound framework
In statistical physics, determining the exact ground state of the Ising spin glass model is a fundamental challenge. A prominent approach to addressing this is through tensor network contraction [27], where branch-and-bound (B&B) algorithms are often employed to identify the optimal contraction order [28]. However, the requisite graph-to-tensor-network transformation frequently yields dense intermediate representations that compromise sparsity, thereby significantly increasing computational complexity. Inspired by the efficacy of branch-and-bound in these contractions—yet seeking to avoid the overhead of dense tensors—we propose applying the technique directly to the NDP. Although branch-and-bound has been extensively utilized for ground state energy calculations in various other optimization contexts [29–33], its direct application to exact network dismantling remains unexplored. Our work bridges this gap by investigating the feasibility of a topology-based branch-and-bound approach on larger network scales.
Our algorithm navigates a decision tree where each node represents a partial configuration of the network. The process relies on two core mechanisms: (1) Branching, which recursively partitions the problem into disjoint sub-problems based on vertex state decisions; and (2) Bounding, which computes lower and upper bounds on the dismantling set size to eliminate suboptimal branches. The computational efficiency is governed by the tightness of these bounds [20]. To quantify the pruning power of our approach compared to exhaustive enumeration, we introduce the efficiency ratio k:
$\begin{eqnarray}k=\frac{{2}^{N}}{n},\end{eqnarray}$
where N is the total number of vertices and n is the number of branches actually explored by the algorithm. A higher k indicates a more effective contraction of the effective phase space.To illustrate the necessity of shifting from a microscopic to a mesoscopic perspective, we compare our approach against a naive vertex-based branch-and-bound baseline. Unlike exhaustive enumeration, this baseline employs standard pruning techniques but explores the configuration space by sequentially fixing individual vertex spins Si ∈ {+1, −1}, ignoring the potential to decompose the network into independent clusters (connected components). While this naive B&B improves upon brute force, it remains inefficient for our problem because it fails to exploit the decomposable structure of the solution space: for a random network with N = 30 vertices, it must explore ∼5 × 107 branches, yielding a modest efficiency of k ≈ 20. In stark contrast, our structure-aware algorithm achieves k ≈ 1.6 × 1017 on significantly larger networks (N = 83), demonstrating a dramatic reduction in computational complexity.
3.2. Structural branching strategy: from spins to clusters
The core of our algorithm lies in exploiting the topological constraints of the C-dismantling problem. In the language of percolation theory [34], the constraint LCC ≤ C is equivalent to forcing the system into a subcritical phase where the correlation length (maximum cluster size) is strictly bounded by a finite cutoff C.
For any pivot vertex v in the current largest connected component, the branching process explores two distinct configurations:
| • Scenario 1 (Site Decimation, Sv = −1). The vertex v is removed. This is a strictly local operation, analogous to the standard decimation procedure acting on a single site and its immediate edges. | |
| • Scenario 2 (Cluster Decoupling, Sv = +1). The vertex v is retained. To satisfy the subcritical constraint, v must be confined within a finite cluster ${\mathscr{G}}(v)$ of size $| {\mathscr{G}}(v)| \leqslant C$. This imposes an extended topological constraint: the boundary $\partial {\mathscr{G}}(v)$ must be removed (${{\boldsymbol{S}}}_{u}=-1,\forall u\in \partial {\mathscr{G}}(v)$). |
We formalize Scenario 2 by identifying all possible valid subcritical clusters ${\mathscr{G}}(v)$. If v is retained, the algorithm essentially performs a block operation (or mesoscopic update): it treats the entire cluster ${\mathscr{G}}(v)$ as a cohesive unit and targets its boundary for removal.
Figure 1 illustrates these decisions. Unlike Scenario 1 [figure 1(a)] which operates on the nearest neighbors, Scenario 2 [figures 1(b)–(d)] exploits medium-range structural information. By identifying and isolating an entire cluster in one step, we efficiently prune the search space by bypassing the combinatorial complexity of checking individual nodes within that cluster.
Figure 1. Branching scenarios for network dismantling. The pivot vertex is shown in green; vertices retained together with the pivot as a cluster ${\mathscr{G}}(v)$ are shown in yellow/brown; vertices that must be removed (either the pivot itself or the boundary $\partial {\mathscr{G}}(v)$) are shown in black. The four panels enumerate the branches generated at a single pivot for C = 2. (a) Scenario 1 (Sv = − 1): the pivot is directly removed; recursion then continues on G\{v}. This is a purely local (site-level) move. (b)–(d) Scenario 2 (Sv = + 1): the pivot is retained and must lie inside some connected subgraph ${\mathscr{G}}(v)$ with $| {\mathscr{G}}(v)| \leqslant C$; the entire boundary $\partial {\mathscr{G}}(v)$ is then removed in one mesoscopic step. Panels (b) and (c) show two distinct two-vertex clusters containing the pivot, each producing a different boundary and hence a different child sub-problem; panel (d) shows the degenerate singleton cluster ${\mathscr{G}}(v)=\{v\}$, in which case every immediate neighbour of v must be deleted. Scenarios 1 and 2 together exhaust all configurations of v consistent with the subcritical constraint, guaranteeing completeness of the search tree. |
The Branch-and-Bound Dismantling (BD) algorithm proceeds recursively. In each step, we select the vertex v with the HD within the current LCC to maximize the impact of the branching decision. We then iterate through all possible valid groups ${\mathscr{G}}(v)$ capable of containing v. The search is pruned immediately if the size of the current dismantling set plus the required boundary removals exceeds the size of the best-known solution found so far ($| {S}_{\min }| $). The initial upper bound is established using a heuristic method (e.g. CoreHD) to accelerate early pruning. By prioritizing high-degree nodes and exploiting the group constraint $| {\mathscr{G}}(v)| \leqslant C$, BD effectively transforms the search from vertex-based flipping to cluster-based decimation. This is particularly advantageous when C is small, as the number of valid subgraphs ${\mathscr{G}}(v)$ remains tractable. The procedure is detailed in Algorithm 1 .
3.3. Completeness and optimality of the pruning
We briefly justify why the combination of Scenario 1 and Scenario 2 enumerates all feasible dismantling configurations, and why the bounding step preserves optimality.
Completeness. For any pivot vertex v in the current LCC, every feasible configuration S must satisfy exactly one of the following: either (i) v ∈ S (i.e. Sv = − 1), which corresponds to Scenario 1; or (ii) v ∉ S (i.e. Sv = + 1), in which case the subcritical constraint LCC ≤ C forces v to reside in some connected component ${\mathscr{G}}(v)$ of size at most C in the residual graph, and the boundary $\partial {\mathscr{G}}(v)$ must be entirely removed. Enumerating all admissible ${\mathscr{G}}(v)$ (containing v, size ≤C, connected in G) therefore exhausts case (ii). The disjoint union of Scenarios 1 and 2 thus covers the full feasible space.
Optimality under pruning. At every recursive call, ∣Scurrent∣ together with the incurred boundary $| \partial {\mathscr{G}}(v)| $ (for Scenario 2) or {v} (for Scenario 1) constitutes a valid lower bound on the size of any dismantling set reachable from the current branch. The pruning rule (line 9 of Algorithm 1 ) discards a branch only when this lower bound already reaches or exceeds the incumbent $| {S}_{\min }| $. Hence no configuration strictly better than ${S}_{\min }$ is ever eliminated, and upon termination ${S}_{\min }$ is guaranteed to be a global optimum.
Branch-and-Bound Dismantling (BD)
| Input: Undirected graph G = (V, E), threshold C, current set Scurr, best solution Smin |
| Output: Updated minimal dismantling set Smin |
| 1: Function BD(G, Scurr) |
| 2: if ∣LCC(G)∣≤C then ⊳Global constraint satisfied |
| 3: if ∣Scurr∣ < ∣Smin∣ then |
| 4: Smin ← Scurr |
| 5: end if |
| 6: return |
| 7: end if |
| 8: Pruning: |
| 9: if ∣Scurr∣≥∣Smin∣ then return |
| 10: end if |
| 11: $v\leftarrow {{\rm{\arg }}\,{\rm{\max }}}_{u\in {\rm{LCC}}(G)}\,{\rm{\deg }}(u)$ ⊳Select pivot vertex |
| 12: Branch 1: Remove v |
| 13: BD(G\{v}, Scurr ∪ {v}) |
| 14: Branch 2: Retain v (Group Isolation) |
| 15: Identify all connected subgraphs $\{{{\mathscr{G}}}_{i}(v)\}$ where $v\in {{\mathscr{G}}}_{i}(v)$ and $| {{\mathscr{G}}}_{i}(v)| \leqslant C$ |
| 16: for each group ${{\mathscr{G}}}_{i}(v)$ do |
| 17: $D\leftarrow \partial {{\mathscr{G}}}_{i}(v)$ ⊳Boundary to remove |
| 18: ${G}^{{\prime} }\leftarrow G\setminus ({{\mathscr{G}}}_{i}(v)\cup D)$ ⊳Remove group and boundary |
| 19: BD(${G}^{{\prime} },{S}_{\,\rm{curr}\,}\cup D$) |
| 20: end for |
| 21: End Function |
3.4. Case study: the 9/11 terrorist network
We demonstrate the capability of BD to identify non-obvious critical nodes using the 9/11 terrorist network [35] (62 nodes, 159 edges). We solve the C = 9 dismantling problem.
Figure 2 compares the initial heuristic solution with the exact ground state found by BD. Initially, a greedy strategy might select high-degree nodes [figure 2(a)]. However, the exact algorithm identifies a subtler configuration [figure 2(b)] that involves removing vertices 45 and 24. Despite their lower degrees, these nodes act as ‘topological bridges’ whose removal is more cost-effective than targeting high-degree nodes. BD finds an optimal set of size ∣S∣ = 12, whereas FINDER requires 14 nodes, and CI requires even more (reducing LCC only to 18 after 16 removals). This case study highlights the algorithm’s ability to uncover hidden structural vulnerabilities that escape heuristic detection.
Figure 2. Exact dismantling of the 9/11 terrorist network (C = 9). (a) An initial solution derived from degree-based heuristics (∣S∣ = 15, LCC size = 9). (b) The optimal solution identified by BD (∣S∣ =12). Bold labels indicate key low-degree vertices (e.g., nodes 45 and 24) identified by the exact solver. These vertices serve as critical connectors that are overlooked by heuristics like HD or CI, which produce larger dismantling sets for the same threshold. |
4. Numerical experiments
4.1. Exact results on random graphs
The target fragmentation threshold was set to C = [0.05N]. To ensure a rigorous comparison, we fine-tuned the heuristic parameters: for CI, the radius l was varied from 1 to 30 to select the optimal outcome; for BPD, the parameter x was optimized over integer values. In the CoreHD algorithm, if no 2-core exists, we default to removing the HD vertex in the largest connected component.
For Erdős–Rényi (ER) graphs (N = 60–80, ⟨k⟩ = 3.5), our BD algorithm demonstrates superior performance. As shown in figure 3(a), BD consistently identifies smaller dismantling sets than all heuristics. Figure 3(b) illustrates the computational cost: despite the exponential nature of the problem, the high k-values indicate efficient pruning, maintaining tractability for these system sizes.
Figure 3. Results on Erdős–Rényi (ER) graphs. Networks were generated with a fixed seed and an average degree ⟨k⟩ = 3.5. (a) Dismantling set size ∣S∣ versus vertex count N. BPD exhibits the best average performance among heuristics. (b) Efficiency of the exact algorithm: k-value (pruning efficiency, blue) and computation time (green) versus N. The slope change in k reflects the transition from C = 3 to C = 4 (maintaining a 5% LCC threshold), illustrating the trade-off between group search complexity and pruning power. |
For random regular graphs (figure 4), we observe a pronounced increase in computational time compared to ER graphs. This stems from structural homogeneity—since all vertices possess identical degrees, the algorithm lacks topological gradients to guide early pruning, necessitating more extensive exploration. This is reflected by the significantly reduced k-values for N = 50–70. Nevertheless, BD guarantees optimality, providing a strict lower bound that confirms BPD’s superiority among approximate methods.
Figure 4. Performance on 4-regular random graphs. (a) Dismantling set size versus vertex count. BPD consistently outperforms other heuristics. (b) Computational metrics for BD: pruning efficiency (k-value) and runtime. The structural homogeneity of regular graphs makes pruning less effective (lower k) compared to ER graphs. |
Crucially, our algorithm significantly expands the tractable size limit for exact dismantling. Whereas machine learning approaches like GDM are typically trained on small instances (N ≈ 25) due to brute-force limitations, BD effectively handles graphs with N > 80. This capability is vital for applications where solution precision is non-negotiable.
4.2. Approximation and scalability
Empirical analysis reveals that high-degree vertices frequently populate the MDS, and optimal groups often exhibit sparse external connectivity. Building on these insights, we introduce an approximate variant, BDA. In BDA, we selectively employ the group-removal strategy only on clusters with sparse boundaries, accelerating the search on larger networks. With this approximation, BDA extends the tractable size of ER random graphs (with ⟨k⟩ = 3.5 and C = ⌊0.05N⌋) to N ≈ 110 on a single workstation.
BDA proves significantly faster than the exact BD on larger instances. While it sacrifices the guarantee of optimality, it consistently outperforms all heuristics. Table 1 presents results for 100-vertex ER graphs (⟨k⟩ = 3.5). BDA achieves better solution in all cases, with a pruning efficiency of k ∼ 1022.
Table 1. Performance on 100-vertex Erdős–Rényi graphs (⟨k⟩ = 3.5). BDA denotes our approximate algorithm. Bold values indicate the best found solution. BDA consistently outperforms heuristics while maintaining high computational efficiency. |
| Edges | BDA | CI | HD | CoreHD | BPD |
|---|---|---|---|---|---|
| 162 | 26 | 35 | 35 | 29 | 28 |
| 176 | 29 | 34 | 34 | 33 | 32 |
| 185 | 30 | 37 | 38 | 34 | 32 |
| 187 | 30 | 38 | 38 | 34 | 31 |
| 191 | 30 | 34 | 34 | 33 | 33 |
4.3. Results on real-world social networks
A key observation is that k-values for social networks are substantially higher than those for random graphs of comparable size. This enhancement stems from the heterogeneous degree distribution typical of social networks. The presence of high-degree hubs allows the algorithm to fragment the network rapidly upon testing ‘hub removal’ branches, leading to massive pruning of the remaining search space. Consequently, our algorithm explores fewer branches while maintaining high solution quality.
As shown in table 2, BDA significantly outperforms conventional heuristics, particularly on complex topologies like the ‘Football’ network (N = 115), where heuristics likely get trapped in local optima. BDA reduces the dismantling set size by ≈15% compared to the best heuristic (BPD/CoreHD).
Table 2. Performance on real-world social networks. N and E denote vertex and edge counts. Bold entries highlight optimal solutions (for N ≤ 80) or best-known solutions found by BDA. BDA demonstrates significant superiority on larger networks (Polbooks, Football). |
| Graph | N | E | k | BDA | CI | HD | CoreHD | BPD |
|---|---|---|---|---|---|---|---|---|
| Dolphins | 62 | 159 | 7.9 × 1011 | 23 | 23 | 27 | 25 | 24 |
| Lesmis | 77 | 254 | 2.3 × 1015 | 24 | 27 | 27 | 24 | 27 |
| Polbooks | 105 | 441 | 1.0 × 1024 | 39 | 45 | 47 | 45 | 45 |
| Football | 115 | 613 | 1.5 × 1027 | 69 | 80 | 81 | 81 | 81 |
| Adjnoun | 112 | 425 | 2.1 × 1026 | 39 | 43 | 43 | 42 | 41 |
4.4. Hybrid exact-heuristic strategy
To demonstrate scalability to large-scale networks, we propose a two-phase hybrid strategy for 2000-vertex ER graphs:
| • Preprocessing. Use BPD to dismantle the network down to a coarse threshold (e.g. LCC ≤ 100). | |
| • Refinement. Apply the exact BD algorithm to the residual components (now N ≤ 100) to reach the final target (e.g. C = 5). |
This approach leverages BPD’s efficiency for large-scale reduction and BD’s optimality for the difficult final fragmentation. Table 3 shows that this hybrid (BPD-BD) strategy consistently outperforms standalone BPD across all seeds and thresholds, reducing the dismantling set size by 1%–4% within practical runtimes (< 3 h).
Table 3. Performance on 2000-vertex ER graphs (⟨k⟩ = 3.5). Comparison of the hybrid BPD-BD approach versus standalone BPD. The hybrid method (bold) consistently yields smaller dismantling sets. |
| C | Algorithm | Seed1 | Seed2 | Seed3 | Seed4 | Seed5 |
|---|---|---|---|---|---|---|
| 3 | BPD-BD | 673 | 671 | 657 | 673 | 657 |
| BPD | 688 | 699 | 680 | 694 | 677 | |
| | ||||||
| 4 | BPD-BD | 600 | 614 | 586 | 618 | 600 |
| BPD | 615 | 628 | 600 | 624 | 618 | |
| | ||||||
| 5 | BPD-BD | 555 | 570 | 543 | 577 | 552 |
| BPD | 570 | 583 | 555 | 590 | 570 | |
4.5. Implementation and complexity
Our implementation (Python 3.9) runs on a single Intel i7-12700H core. We note that computational efficiency could be further enhanced by migrating loop-intensive operations to C++ and leveraging parallel execution, given that the branch-and-bound tree allows for asynchronous pruning. The algorithm’s complexity is primarily dictated by the vertex count N, average degree ⟨k⟩, and the heterogeneity of the degree distribution. We further remark on the role of the threshold C. In Scenario 2, the admissible clusters $\{{\mathscr{G}}(v):| {\mathscr{G}}(v)| \leqslant C\}$ are all connected subgraphs of size at most C rooted at the pivot, so the number of possible operations at a single vertex grows exponentially with C. For ER random graphs with ⟨k⟩ = 3.5, we find empirically that C should be kept at C ≤ 10 to maintain practical runtimes.
5. Conclusion
In this work, we have addressed the long-standing challenge of obtaining exact solutions for the NDP. By strictly formulating the process as a ground state search in statistical physics, and employing a cluster-constrained branch-and-bound framework that exploits the finite correlation length of the subcritical percolation phase, we successfully pushed the tractability limit of exact solutions to random graphs with up to 80 vertices. This approach represents a significant leap from previous brute-force limitations, offering a rigorous tool to explore the true energy landscape of network fragmentation.
Our results provide two critical insights. First, from a theoretical perspective, our exact solver serves as a definitive benchmark for the field. It reveals that while widely used heuristics like CI and CoreHD are efficient, they systematically fail to identify non-hub ‘topological bridges’ that are critical for optimal dismantling. We quantified this optimality gap, showing that our exact approach can improve dismantling efficiency by removing structurally redundant nodes. Second, regarding scalability, our approximate variant (BDA) and the hybrid BPD-BD framework demonstrate that the principles of exact pruning can be effectively adapted to larger networks (N ∼ 2000). This hybrid strategy effectively combines the speed of heuristics with the precision of exact solution, offering a superior trade-off between solution quality and computational time.
Looking forward, the inherent independence of branches in our algorithm suggests immediate potential for parallelization, which could further extend the scale of solvable networks. Moreover, the framework lays the foundation for analyzing more complex scenarios, such as dismantling in directed, weighted, or dynamic networks. We anticipate that these exact benchmarks will not only guide the design of next-generation heuristic algorithms but also deepen our understanding of the fundamental limits of network robustness in mission-critical applications, from infrastructure protection to epidemic containment.