Complexity among combinatorial problems from epidemics

Juan Piccini

doi:10.1111/itor.12444

2017-08-21

PRE

Juan Piccini *

Franco Robledo

Pablo Romero

DOI：10.1111/itor.12444

原文链接

原文求助

摘要

En 中文

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 fromfurther contact with infected individuals). Transitions S -> I -> R occur at constant rates gamma(S), gamma(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.

Keyword:

combinatorial optimization problem

graph fragmentation problem

computational complexity