A derandomized approximation algorithm for the critical node detection problem

In this paper we propose an efficient approximation algorithm for determining solutions to the critical node detection problem (CNDP) on unweighted and undirected graphs. Given a user-defined number of vertices k>0k>0, the problem is to determine which k nodes to remove such as to minimize pairwise connectivity in the induced subgraph. We present a simple, yet powerful, algorithm that is derived from a randomized rounding of the relaxed linear programming solution to the CNDP. We prove that the expected solution quality obtained by the linear-time algorithm is bounded by a constant. To highlight the algorithm quality four common complex network models are utilized, in addition to four real-world networks.