On new approaches of assessing network vulnerability: Hardness and approximation

Thang N. Dinh, Ying Xuan, My T. Thai, Panos M. Pardalos, Taieb Znati

Research output: Contribution to journalArticlepeer-review

112 Citations (Scopus)


Society relies heavily on its networked physical infrastructure and information systems. Accurately assessing the vulnerability of these systems against disruptive events is vital for planning and risk management. Existing approaches to vulnerability assessments of large-scale systems mainly focus on investigating inhomogeneous properties of the underlying graph elements. These measures and the associated heuristic solutions are limited in evaluating the vulnerability of large-scale network topologies. Furthermore, these approaches often fail to provide performance guarantees of the proposed solutions. In this paper, we propose a vulnerability measure, pairwise connectivity, and use it to formulate network vulnerability assessment as a graph-theoretical optimization problem, referred to as β-disruptor. The objective is to identify the minimum set of critical network elements, namely nodes and edges, whose removal results in a specific degradation of the network global pairwise connectivity. We prove the NP-completeness and inapproximability of this problem and propose an O(log n log log n) pseudo-approximation algorithm to computing the set of critical nodes and an O(log 1.5n) pseudo-approximation algorithm for computing the set of critical edges. The results of an extensive simulation-based experiment show the feasibility of our proposed vulnerability assessment framework and the efficiency of the proposed approximation algorithms in comparison to other approaches.

Original languageEnglish
Article number6051504
Pages (from-to)609-619
Number of pages11
JournalIEEE/ACM Transactions on Networking
Issue number2
Publication statusPublished - Apr 2012
Externally publishedYes


  • Approximation algorithm
  • hardness
  • network vulnerability
  • pairwise connectivity

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'On new approaches of assessing network vulnerability: Hardness and approximation'. Together they form a unique fingerprint.

Cite this