Complexity among combinatorial problems from epidemics. (21st August 2017)

• Record Type: Journal Article
• Authors: Piccini, Juan; Robledo, Franco; Romero, Pablo
• Other Names: Dias Joana Matos guestEditor.; Rocha Humberto guestEditor.; Viana Ana guestEditor.
• Is Part Of: International transactions in operational research. Volume 25:Number 1(2018)
• Page Start: 295
• Page End: 318
• Publication Date: 2017-08-21
• Subjects: combinatorial optimization problem -- graph fragmentation problem -- computational complexity; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12444
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: 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.