A novel algorithm for the generalized network dismantling problem based on dynamic programming

For an undirected network G=(V,E) with removal cost on each node, the generalized network dismantling problem is to find a node subset S⊆V with the minimum overall removal cost, such that the size of each connected component in G−S is not larger than a given integer K. This issue has wide applications at network destruction (e.g., combating crime network) or network defense (e.g., strengthening the infrastructure), and has gained growing attentions from various research fields. In graph theory, cut nodes play important roles in ensuring network connectivity, which could of course be regarded as potential removal candidates for this network dismantling problem. This paper is primarily dedicated to this point. Here, having the aid of an auxiliary block-cut tree, we transform the network dismantling problem into a relatively simple problem −− tree dismantling problem, and then design a bottom-up dynamic programming algorithm (abbreviated as DPA) to dismantle this auxiliary tree by removing cut nodes with minimum overall removal costs. This DPA dismantling strategy has been tested on both synthetic networks and real-world networks, and numerical experiments demonstrate the superiority of this method. Our results shed light on more explorations of network structure from the cut-node perspectives.