Dismantling and Vertex Cover of Network through Message Passing

The dismantling problem and minimum vertex cover (MVC) problem of network are two fundamental NP-hard problems where the former aims to find a minimal subset of nodes whose removal leaves the network broken in small components of sub-extensive size and the latter is also to find a minimal vertex set which contains at least one incident vertex of every edge. Both of them have a wide range of applications related to circuit design, communication, network security, transportation, epidemic control, molecular biology and economics. In this brief, we first propose a novel belief-propagation equation for the spin glass model of the MVC problem. A belief-propagation-guided decimation (BPD) algorithm is then presented which could construct approximate optimal vertex cover of network. In addition, based on the relationship between the network dismantling problem and the MVC problem, we propose a simple and fast algorithm formed by the MVC and a general node reinsertion strategy, for solving the network dismantling problem. The effectiveness of the proposed algorithms is finally verified by comparing with other well-known algorithms on a number of real world networks.