A fast heuristic algorithm for the critical node problem

Overview & Synopsis

The critical node problem (CNP) aims to identify a subset of critical nodes in an undirected graph such that removing these critical nodes minimizes the pairwise node connectivity over the residual graph. CNP has various applications; however, it is computationally challenging. This paper introduces FastCNP, a fast heuristic algorithm for solving the problem. FastCNP employs an effective two-phase node exchange strategy to locate high-quality solutions and applies a destructive-constructive perturbation procedure to drive the search to new regions when the search stagnates. Computational results on 16 popular benchmark instances show that FastCNP finds improved best results (new upper bounds) for 6 instances, and matches the best-known results for 9 instances.