Abstract
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 , 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.
Type
Publication
Computers and Operations Research
