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 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 a synthetic benchmark, a real-world benchmark, and a 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 three benchmarks.