Maximum number of steps for $2$-neighbour bootstrap percolation

Question

This question is a follow-up to this question posted on Mathematica SE.

So as to keep the question self-contained, the problem is as follows:

$n^2$ computers are connected in a $n\times n$ network grid. At the start exactly $n$ of them are infected with a virus. The virus spreads like this: if any computer is directly connected to at least $2$ infected neighbours, it will also become infected.

(based on problem $2$ in this link).

The number of solutions to $n$ infected computers on an $n\times n$ grid appears to be OEIS sequence A146971. The numbers of possible starting positions is clearly ${n^2}\choose{n}$.

It is trivial to generate a starting position with $n$ steps (including first position):

Here is an example of a starting position on a $10\times 10$ grid that takes $49$ steps:

I looked at this paper, but the algorithm proposed for a square grid appears to be related to but not identical to the problem above (or am I missing something?).

As @MartinEnder pointed out in his answer, this is essentially an outer totalistic cellular automaton with a von Neumann neighbourhood, using the weights

$$\begin{bmatrix} 0 & 2 & 0 \\ 2 & 1 & 2 \\ 0 & 2 & 0 \\ \end{bmatrix}$$

Is there a polynomial-time algorithm that can be used to generate:

1. The starting position for $n$ points that takes the maximum number of steps?
2. All possible arrangements for $n$ infected computers on an $n\times n$ grid?

The max number of steps appears to require a spiral-like progression. I wonder whether it is possible to exploit this observation to generate max number of steps for $n$ initial points?

Added

The following matrices:

$\left( \begin{array}{c} 1 \\ \end{array} \right)$ $\left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ \end{array} \right)$ $\left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)$ $\left( \begin{array}{cccc} 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right)$ $\left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ \end{array} \right)$

$\left( \begin{array}{cccccc} 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ \end{array} \right)$ $\left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ \end{array} \right)$ $\left( \begin{array}{cccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$

take ${1, 2, 5, 10, 15, 22, 29, 38}$ stepts to complete the grid respectively. The $6\times 6,$ $7\times 7$ and and the $8\times 8$ are best guesses, but the $n \times n$ matrices for $n=1$ to $5$ (ie ${1, 2, 5, 10, 15}$) are longest possible number of steps.

eg:

Module[{a, b, d = #}, a = {
{{1}},
{{1, 0}, {0, 1}},
{{1, 0, 1}, {0, 0, 0}, {0, 0, 1}},
{{1, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}},
{{1, 0, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 1, 0, 1}},
{{1, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 1}},
{{1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 1, 0, 1}},
{{0, 1, 0, 0, 0, 0, 1, 0}, {0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0}}
}[[#]];
b = Most@FixedPointList[CellularAutomaton[
{1018, {2, {{0, 2, 0}, {2, 1, 2}, {0, 2, 0}}}, {1, 1}}, {#, 0}][[1, 2 ;; -2, 2 ;; -2]] &, a];
{Length@b, ListAnimate[ArrayPlot /@ b, 
DefaultDuration -> Ceiling[Sqrt[Length@b]], AnimationRunning -> False]}] &@8

Are $22,29,38$ the maximum number of steps for $n=6,7,8$?

The only sequence that matches this in OEIS is A179207: $f(n)=\big{|}\left \lceil{(n^2-3)/2}\right \rceil + n - 1 \big{|}$. This agrees with the upper bound of $13 n^2/18+O(n)$ proved in the paper @EspeciallyLime gave in his answer below. It doesn't need to agree with the lower bound given in the paper, since the lower bound in the paper does not have the extra restriction of using only $n$ points to start with on an $n \times n$ grid. The example in fig.12 (p.20) uses $15$ starting points on a $12 \times 12$ grid for example.

Is there any reason why the maximum number of steps for $n$ points on an $n \times n$ grid shoud equal $\big{|}\left \lceil{(n^2-3)/2}\right \rceil + n - 1 \big{|}$?

Answer 1

The process you describe is called 2-neighbour bootstrap percolation. For general graphs (rather than a square grid), finding the maximum number of steps is NP-hard (Benevides, Campos, Dourado, Sampaio, Silva, European Journal of Combinatorics, 2015).

For the square grid, here is a paper getting good bounds on the maximum number of steps. Most other results out there are about random initial sets (rather than worst-case) though.