Complexity among combinatorial problems from epidemics

A cornerstone in epidemic modeling is the classical susceptible–infected–removed model, or SIR. In this model, individuals are divided into three classes: susceptible (those who can be infected), infected, and removed (those who suffered the infection and recovered, gaining immunity from further contact with infected individuals). Transitions S → I → R occur at constant ratesγ S , γ I . The SIR model is both simple and useful to understand cascading failures in a network. Nevertheless, a shortcoming is the unrealistic assumption of random contacts in a fully mixed large population. More realistic models are available from authoritative literature in the field. They consider a graph and an epidemic spread governed by probabilistic rules. In this paper, a combinatorial optimization problem is introduced using graph‐theoretic terminology, inspired by an extremal analysis of epidemic modeling. The contributions are threefold. First, a general node immunization problem is defined for node immunization under budget requirements, using probabilistic networks. The goal is to minimize the expected number of deaths under a particular choice of nodes in the system to be immunized. In the second stage, a highly virulent environment leads to a purely combinatorial problem without probabilistic law, called the graph fragmentation problem (GFP). We prove the corresponding decision version for the GFP belongs to the class of NP ‐complete problems. As a corollary, SIR‐based models also belong to this set. Third, a GRASP (greedy randomized adaptive search procedure) heuristic enriched with a path‐relinking post‐optimization phase is developed for the GFP. Finally, an experimental analysis is carried out under graphs taken from real‐life applications.