### Network analysis: spread of diseases and attacks

Spread of disease or of attacks can be modeled by graphs in which nodes represent people and edges represent connections. The attacker’s (or bacteria’s) problem is: given a connected graph, in which a vertex is infected if or more of its neighbors are infected, an *irreversible k-conversion set* is a subset of the nodes such that if we plant a disease on the nodes of this subset, the entire graph will become infected. The object of this research project is to computationally explore the size of minimal irreversible k-conversion sets in graphs, in particular in rectangular or toroidal grids.

When this problem is known to be computationally hard (it is NP-complete) so approximate algorithms are required for the solution.

### References & Readings

- Graph-theoretical problems arising from defending against bioterrorism and controlling the spread of fires. Fred Roberts, DIMACS (graphdiseasespreadmodels-thresholdfirefighterddr4-26-06)
- DIMACS 2002-2009 Special Focus on Computational and Mathematical Epidemiology
- Web game provides breakthrough in predicting spread of epidemics