In this chapter we discuss a common derandomized approximation algorithm for yielding a constant-tunable approximation bound to two variants of the critical node detection problem. The goal of the respective problems is to reduce total pairwise connectivity or number of vertices to delete in order to achieve bounded component sizes in the residual graph, respectively. Our algorithms are built upon previous research and improved by an efficient local search algorithm that incorporates the closeness centrality. We show that the original approximation algorithm bounds remain in tact, while the practical performance is greatly improved. To highlight the results we utilize five common network data sets of various sizes.