# Research in Scientific Computing in Undergraduate Education

### 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 $k \geq 1$ 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 $k \geq 2$ this problem is known to be computationally hard (it is NP-complete) so approximate algorithms are required for the solution.