Detecting k-Vertex Cuts in Sparse Networks via a Fast Local Search Approach

The {k} -vertex cut ({k} -VC) problem belongs to the family of the critical node detection problems, which aims to find a minimum subset of vertices whose removal decomposes a graph into at least {k} connected components. It is an important NP-hard problem with various real-world applications, e.g., vulnerability assessment, carbon emissions tracking, epidemic control, drug design, emergency response, network security, and social network analysis. In this article, we propose a fast local search (FLS) approach to solve it. It integrates a two-stage vertex exchange strategy based on neighborhood decomposition and cut vertex, and iteratively executes operations of addition and removal during the search. Extensive experiments on both intersection graphs of linear systems and coloring/DIMACS graphs are conducted to evaluate its performance. Empirical results show that it significantly outperforms the state-of-the-art (SOTA) algorithms in terms of both solution quality and computation time in most of the instances. To evaluate its generalization ability, we simply extend it to solve the weighted version of the {k} -VC problem. FLS also demonstrates its excellent performance.