Heuristic Search with Cut-point Based Strategy for Critical Node Problem

The critical node problem (CNP) aims to deal with critical node identification in a graph, which has extensive applications in many fields. Solving CNP is a challenging task due to its computational complexity, and it attracts much attention from both academia and industry. In this paper, we propose a population-based heuristic search algorithm called CPHS (Cut Point based Heuristic Search) to solve the CNP, which integrates two main ideas. The first one is a cut point based greedy strategy in the local search, and the second one involves the functions used to update the solution pool of the algorithm. Besides, a mutation strategy is applied to solutions with probability based on the overall average similarity to maintain the diversity of the solution pool. Experiments are performed on the synthetic benchmark, real-world benchmark and large-scale network benchmark to evaluate our algorithm. Compared with state-of-the-art algorithms, our algorithm has better performance in terms of both solution quality and run time on all the benchmarks.