LAUSR

The identification of critical network components is of interest to both interdictors wishing to degrade the network’s performance, and to defenders aiming to preserve network performance in the face of disruption. In this study, novel formulations for the defender’s problem, based on the dual to the multi-commodity flow problem, are developed to solve the critical node problem (CNP), in which the nodes can be disabled, for a variety of commonly-studied objectives, including minimum connectivity, cardinality-constraint CNP, and β-disruptor problem. These objectives have applications in many types of networks, including transportation, communications, public health, and terrorism. Extensive computational experiments are presented, demonstrating that the proposed models dramatically reduce the computational time needed to solve such problems when compared to the best-performing models in the current literature. The proposed CNP models perform particularly well for networks that are originally disconnected (before interdiction) and for networks with a large number of two-degree nodes.