Minimal percolating sets for mutating infectious diseases

This paper is dedicated to the study of the interaction between dynamical systems and percolation models, with views toward the study of viral infections whose virus mutate with time. Recall that $r$-bootstrap percolation describes a deterministic process where vertices of a graph are infected once $r$ neighbors of it are infected. We generalize this by introducing $F\left(t\right)$-bootstrap percolation, a time-dependent process where the number of neighboring vertices that need to be infected for a disease to be transmitted is determined by a percolation function $F\left(t\right)$ at each time $t$. After studying some of the basic properties of the model, we consider smallest percolating sets and construct a polynomial-timed algorithm to find one smallest minimal percolating set on finite trees for certain $F\left(t\right)$-bootstrap percolation models.

Figure 1

Depiction of 2-bootstrap percolation, where shaded vertices indicated infected nodes.

Figure 2

Percentage of nodes infected at time $t$ for $F\left(t\right)$-bootstrap percolation with initial probability $p$, on graphs with 100 nodes and 300 edges.

Figure 3

(a) In this tree, having nodes 2,4,5 infected (shaded) initially is sufficient to ensure that the whole tree is infected. (b) This minimal percolating set shaded is of size 5.

Figure 4

Panels (a–c) show the first three updates through the algorithm in Sec. 5d, where the vertices considered at each time are shaded and each vertex is assigned the value of $t_{*}$.

Figure 5

Panels (a, b) update 4–5 through the algorithm. Panel (c) sets $A_0$ in light shade, and infected vertices as gridded vertices.

Figure 6

Panels (a–c) update through the algorithm in Sec. 5d after setting $A_0$ to be as in Fig. 5.

Figure 7

Final steps of the algorithm, as in Fig. 5.

Figure 8

The size of smallest minimal percolating sets on perfect trees with height 4, with a constant and a nonconstant percolation function $F\left(t\right)$.

Figure 9

Trials done on 10 000 random trees of $n$ nodes, taking the average, and dividing it by $n$ for the fraction of node needed to be initially infected for the model to percolate.

Figure 10

Degree 2 tree with 5 nodes.