Analysis and Complexity of Node-Immunization under Natural Disasters

Inhalt:
The object under study is natural disaster management via node-immunization subject to budget constraints. The system is modelled by a network, where a single node is exposed to a natural disaster that is immediately propagated through neighbouring nodes. The goal is to choose a node-immunization strategy in order to minimize the disaster. Examples of natural disasters include a fire, an electric shock or pandemics, among others. Our contribution is three-fold. First, the system under risk is modelled by means of a combinatorial optimization problem. Second, the hardness and universal inapproximability to optimality is formally proved. Third, the optimum immunization strategy is found for all acyclic graph, elementary cycles and some bipartite graphs, in strong contrast to the previous negative results.