Detecting <inline-formula> <tex-math notation="LaTeX">$k$</tex-math> </inline-formula>-Vertex Cuts in Sparse Networks via a Fast Local Search Approach

Yangming Zhou, Gezi Wang, Meng Chu Zhou

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

The <italic>k</italic>-vertex cut (<italic>k</italic>-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 <italic>k</italic> 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 <italic>k</italic>-VC problem. FLS also demonstrates its excellent performance.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalIEEE Transactions on Computational Social Systems
DOIs
StateAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

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

Keywords

  • COVID-19
  • Codes
  • Complex systems
  • Pandemics
  • Proteins
  • Search problems
  • Social networking (online)
  • Task analysis
  • critical node detection
  • heuristic search
  • k-vertex cut (k-VC) problem
  • local search

Fingerprint

Dive into the research topics of 'Detecting <inline-formula> <tex-math notation="LaTeX">$k$</tex-math> </inline-formula>-Vertex Cuts in Sparse Networks via a Fast Local Search Approach'. Together they form a unique fingerprint.

Cite this