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.