On the smallest pseudo target set identification problem for targeted attack on interdependent power-communication networks

Arun Das, Chenyang Zhou, Joydeep Banerjee, Arunabha Sen, Lloyd Greenwald

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


Recognizing the need for a deeper understanding of the interdependence between critical infrastructures, such as the power grid and the communication network, a number of models have been proposed and analyzed in the last few years. However, most of these proposed models are over simplified and fail to capture complex interdependencies that may exist between these critical infrastructures. The recently proposed Implicative Interdependency Model is able to capture these complex interdependencies involving conjunctive and disjunctive relationships to overcome most of these limitations. Due to the existing interdependencies between the power and communication networks, a failure involving a small set of power and/or communication network entities can trigger a cascading event, resulting in the failure of a much larger set of entities through the cascading failure process. This implies that an adversary with an intent of destroying a specific set of entities E′ (real targets), no longer needs to make an effort to destroy E′ directly, but instead identify a set of smaller entities E′ (pseudo targets), whose destruction eventually leads to the destruction of the real target set E′ due to the cascading failure process. A clever adversary will thus try to identify the smallest set of pseudo target entities E00, whose destruction eventually destroys E′. We refer to this problem as the Smallest Pseudo Target Set Identification Problem (SPTSIP). We divide the problem into four classes, and show that it is solvable in polynomial time for one class, and is NP-complete for others. We provide an approximation algorithm for the second class, and for the most general class, we provide an optimal solution using ILP, and a heuristic solution. We evaluate the efficacy of our heuristic using power and communication network data of Maricopa County, Arizona. The experiments show that our heuristic almost always produces near optimal results.

Original languageEnglish (US)
Title of host publication2015 IEEE Military Communications Conference, MILCOM 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781509000739
StatePublished - Dec 14 2015
Event34th Annual IEEE Military Communications Conference, MILCOM 2015 - Tampa, United States
Duration: Oct 26 2015Oct 28 2015

Publication series

NameProceedings - IEEE Military Communications Conference MILCOM


Other34th Annual IEEE Military Communications Conference, MILCOM 2015
Country/TerritoryUnited States


  • Biological system modeling
  • Communication networks
  • Complexity theory
  • Power grids
  • Power system faults
  • Power system protection
  • Target tracking

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'On the smallest pseudo target set identification problem for targeted attack on interdependent power-communication networks'. Together they form a unique fingerprint.

Cite this