The Threshold Shortest Path Interdiction Problem for Critical Infrastructure Resilience Analysis

Abstract

We formulate and solve the threshold shortest path interdiction problem, which we define as follows: Find a finite set of arcs to attack within a network such that the resulting shortest path from a given source node to a given destination is longer than a specified threshold. Ultimately we are concerned with determining the number of such attacks and using it as a measure of resilience or lack thereof, in an instance of the shortest-path interdiction problem. We develop and implement algorithms to reduce the required computational effort to solve this counting problem exactly. We illustrate via test cases the impact of different interdiction combinations with regards to the threshold value. Whether these interdictions are random occurrences or intentional, this analysis provides decision makers a tool with which to more completely characterize the resilience of a system of interest.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 2017
Accession Number
AD1046817

Entities

People

  • Charles R. Clark

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Energy and Power Technologies
  • Engineered Resilient Systems

DTIC Thesaurus Topics

  • Algorithms
  • Dynamic Programming
  • Flow Network
  • Homeland Security
  • Infrastructure
  • Interdiction
  • National Security
  • Operations Research
  • Parallel Computing
  • Parallel Processing
  • Resilience
  • Risk
  • Risk Analysis
  • Security
  • United States
  • United States Naval Academy
  • Vulnerability

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Military History / Militaries and War Studies
  • Theoretical Analysis.