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

Yangming Zhou, Gezi Wang, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1832-1841
Number of pages10
JournalIEEE Transactions on Computational Social Systems
Volume11
Issue number2
DOIs
StatePublished - Apr 1 2024

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction
  • Social Sciences (miscellaneous)
  • Modeling and Simulation

Keywords

  • Complex systems
  • critical node detection
  • heuristic search
  • k-vertex cut (k-VC) problem
  • local search

Fingerprint

Dive into the research topics of 'Detecting k-Vertex Cuts in Sparse Networks via a Fast Local Search Approach'. Together they form a unique fingerprint.

Cite this