ABSTRACT Given a graph and a set of activated/infected nodes, we consider the problem of determining the set of nodes that minimizes the network propagation on the subgraph that results from the removal of those nodes. To measure network propagation, we assume that a node is activated/infected in the resulting subgraph if there is a path from an activated/infected node in to node . Several mixed‐integer programs are presented to find the critical nodes to prevent propagation on directed and undirected graphs. Two compact models are devised by adapting the best‐known models for determining a set of critical nodes in a graph to this problem. A new compact model is devised from a network interdiction formulation, and a new path‐formulation model is introduced. We show that all the models provide the same linear relaxation bound and compare them on a set of instances from the literature. To address the computational challenges of large networks, several efficient heuristics are introduced. The results show that the compact model from the interdiction perspective is faster, allowing it to solve to optimality sparse networks with up to 10 000 nodes.
Agra et al. (Thu,) studied this question.