Managing network risk via critical node identification

We consider methodologies for managing risk in a telecommunication network based on identification of the critical nodes. The objective is to identify a set of vertices with a specified cardinality whose deletion results is maximum number of disconnected components. This is referred to as the CRITICAL NODE PROBLEM, and finds application in epidemic control, telecommunications, and military tactical planning, among others. From a telecommunication perspective, the set of critical nodes helps determine which players should be removed from the network in the event of a virus outbreak. Conversely, in order to maintain maximum global connectivity, it should be ensured that the critical nodes remain intact. In this chapter, we review the recent work in this area and examine formulations based on integer linear programming.