Lower bound of network dismantling problem.

The network dismantling problem is one of the most fundamental problems in network science. It aims to identify the minimum number of nodes, such that after their removal the network is broken into many disconnected pieces with a sub-extensive size. However, the identification of the minimum removed nodes belongs to the class of nondeterministic polynomial problems. Although many heuristic algorithms have been proposed to identify the removed nodes, the smallest dismantling set remains unknown. Therefore, the determination of a good lower bound of dismantling sets is of great significance to evaluating the performances of heuristic algorithms. The minimum number of deleted nodes to dismantle a network is strictly no smaller than that to dismantle its any subnetwork in nature. Any lower bound of a subnetwork is indeed a lower bound of the original network. Utilizing the heterogeneous degree distribution and 2-core properties, we find that with previous removal of some appropriate nodes, the lower bound obtained on the basis of the subnetwork is counterintuitively significantly better than the one obtained directly on the original network, especially for the real-world networks.