Simulated Hill Climbing Search for the Solutions of k-Vertex Cut Problems

A k-vertex cut problem aims to find a minimum subset of nodes whose removal decomposes a graph into at least k connected components, which belongs to the family of critical node detection problems. It is an important NP-hard problem with various real-world applications. In this paper, we propose a simple and effective simulated hill climbing search (SHCS) to solve it. SHCS consists of three complementary search phases: forward search, stagnation search and backward search. Extensive experiments on two groups of widely-used benchmark instances are conducted to evaluate performance. The results show that it significantly outperforms the state-of-the-art algorithms in terms of both solution quality and computational time on most of the instances.