A randomized algorithm with local search for containment of pandemic disease spread

In this paper we present a randomized rounding algorithm for approximating the cardinality-constrained critical node detection problem. This problem seeks to fragment a given network into subgraphs no larger than a prescribed cardinality by removing the smallest possible subset of vertices from the original graph. The motivating application is containment of pandemic disease by prophylactic vaccination, however, the approach is general. We prove that a derandomized algorithm provides a 1/(1-theta)-approximation to the optimal objective value for theta a rounding threshold, in expectation. To improve the practical performance a local search is subsequently performed. We verify the algorithm's performance using four common complex network models with different structural properties and over a variety of cardinality constraints. (C) 2014 Elsevier Ltd. All rights reserved.