The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results

Abstract

In $2$-neighbourhood bootstrap percolation on a graph $G$, an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least $2$ already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. The maximum time $t(G)$ is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved [7] that deciding if $t(G)\ge k$ is polynomial time solvable for $k=2$, but is NP-Complete for $k=4$ and is NP-Complete if the graph is bipartite and $k=7$. In this paper, we solve the open questions. Let $n = |V(G)|$ and $m = |E(G)|$. We obtain an $\varTheta (m n^5)$-time algorithm to decide if $t(G)\ge 3$ in general graphs. In bipartite graphs, we obtain an $\varTheta (m n^3)$-time algorithm to decide if $t(G)\ge 3$ and an $O(m n^{13})$-time algorithm to decide if $t(G)\ge 4$. We also prove that deciding if $t(G)\ge 5$ is NP-Complete in bipartite graphs.

1 Introduction

We consider a problem in which an infection spreads over the vertices of a connected simple graph $G$ following a deterministic spreading rule in such a way that an infected vertex will remain infected forever. Given a set $S \subseteq V(G)$ of initially infected vertices, we build a sequence $S_0, S_1, S_2, \ldots$ in which $S_0=S$ and $S_{i+1}$ is obtained from $S_i$ using such spreading rule.

Under $r$-neighbour bootstrap percolation on a graph $G$, the spreading rule is a threshold rule in which $S_{i+1}$ is obtained from $S_i$ by adding to it the vertices of $G$ which have at least $r$ neighbours in $S_i$. We say that a set $S_0$ percolates $G$ (or that $S_0$ is a percolating set of $G$) if eventually every vertex of $G$ becomes infected, that is, there exists a $t$ such that $S_t = V(G)$. In that case, we define $t_r(S)$ as the minimum $t$ such that $S_t = V(G)$. And define, the percolation time of $G$ as $t_r(G) = \max \{t_r(S) : S \text { percolates } G\}$. In this paper, we shall focus on the case where $r=2$ and in such case we omit the subscript of the functions $t_r(S)$ and $t_r(G)$.

Bootstrap percolation was introduced by Chalupa, Leath and Reich [13] as a model for certain interacting particle systems in physics. Since then it has found applications in clustering phenomena, sandpiles [19], and many other areas of statistical physics, as well as in neural networks [1] and computer science [15].

There are two broad classes of questions one can ask about bootstrap percolation. The first, and the most extensively studied, is what happens when the initial configuration $S_0$ is chosen randomly under some probability distribution? For example, vertices are included in $S_0$ independently with some fixed probability $p$. One would like to know how likely percolation is to occur, and if it does occur, how long it takes.

The answer to the first of these questions is now well understood for various graphs. An interesting case is the one of the lattice graph $[n]^d$, in which $d$ is fixed and $n$ tends to infinity, since the probability of percolation under the $r$-neighbour model displays a sharp threshold between no percolation with high probability and percolation with high probability. The existence of thresholds in the strong sense just described first appeared in papers by Holroyd, Balogh, Bollobás, Duminil-Copin and Morris [3, 5, 20]. Sharp thresholds have also been proved for the hypercube (Balogh and Bollobás [2], and Balogh, Bollobás and Morris [6]). There are also very recent results due to Bollobás, Holmgren, Smith and Uzzell [10], about the time percolation take on the discrete torus $\mathbb {T}^d_n = (\mathbb {Z}/n\mathbb {Z})^d$ for a randomly chosen set $S_0$.

The second broad class of questions is the one of extremal questions. For example, what is the smallest or largest size of a percolating set with a given property? The size of the smallest percolating set in the $d$-dimensional grid, $[n]^d$, was studied by Pete and a summary can be found in [4]. Morris [22] and Riedl [24], studied the maximum size of minimal percolating sets on the square grid and the hypercube $\{0,1\}^d$, respectively, answering a question posed by Bollobás. However, it was proved in [12, 14] that finding the smallest percolating set is NP-complete for general graphs. Another type of question is: what is the minimum or maximum time that percolation can take, given that $S_0$ satisfies certain properties? Recently, Przykucki [23] determined the precise value of the maximum percolation time on the hypercube $2^{[n]}$ as a function of $n$, and Benevides and Przykucki [8, 9] have similar results for the square grid, $[n]^2$, also answering a question posed by Bollobás. In particular, they have a polynomial time algorithm to compute the maximal percolation time on square grids.

Here, we consider the decision version of the maximum time percolation problem, as stated below.

percolation time

Input: A graph $G$ and an integer $k$.

Question: Is $t(G) \ge k$?

In 2013, Benevides et al. [7] proved that deciding if $t(G)\ge k$ is polynomial time solvable for $k=2$, but is NP-Complete for $k=4$ and is NP-Complete if the graph is bipartite and $k=7$. In this paper, we solve the open questions. Let $n = |V(G)|$ and $m = |E(G)|$. We obtain a $\varTheta (m n^5)$-time algorithm to decide if $t(G)\ge 3$ in general graphs. In bipartite graphs, we obtain $O(m n^{13})$-time algorithm to decide if $t(G)\ge 4$ and prove that deciding if $t(G)\ge 5$ is NP-Complete.

1.1 Related Works and Some Notation

It is interesting to notice that infection problems appear in the literature under many different names and were studied by researches of various fields. The particular case in which $r=2$ in $r$-neighbourhood bootstrap percolation is also a particular case of a infection problem related to convexities in graph.

A finite convexity space [21, 25] is a pair $(V,\mathcal {C})$ consisting of a finite ground set $V$ and a set $\mathcal {C}$ of subsets of $V$ satisfying $\emptyset , V \in \mathcal {C}$ and if $C_1,C_2\in \mathcal {C}$, then $C_1\cap C_2\in \mathcal {C}$. The members of $\mathcal {C}$ are called $\mathcal {C}$ -convex sets and the convex hull of a set $S$ is the minimum convex set $H(S) \in \mathcal {C}$ containing $S$.

A convexity space $(V,\mathcal {C})$ is an interval convexity [11] if there is a so-called interval function $I:\left( {\begin{array}{c}V\\ 2\end{array}}\right) \rightarrow 2^V$ such that a subset $C$ of $V$ belongs to $\mathcal {C}$ if and only if $I(\{ x,y\})\subseteq C$ for every two distinct elements $x$ and $y$ of $C$. With no risk of confusion, for any $S \subseteq V$, we also denote by $I(S)$ the union of $S$ with $\bigcup _{x,y\in S} I(\{x,y\})$. In interval convexities, the convex hull of a set $S$ can be computed by exhaustively applying the corresponding interval function until obtaining a convex set.

The most studied graph convexities defined by interval functions are those in which $I(\{x,y\})$ is the union of paths between $x$ and $y$ with some particular property. Some common examples are the $P_3$-convexity [17], geodetic convexity [18] and monophonic convexity [16]. We observe that the spreading rule in $2$-neighbours bootstrap percolation is equivalent to $S_{i+1} = I(S_i)$ where $I$ is the interval function which defines the $P_3$-convexity: $I(S)$ contains $S$ and every vertex belonging to some path of 3 vertices whose extreme vertices are in $S$. For these reasons, sometimes we call a percolating set by hull set.

2 $t(G)\ge 5$ Is NP-Complete in Bipartite Graphs

In [7], it was proved that deciding if $t(G)\ge 7$ is NP-Complete in bipartite graphs. The following theorem improves this result.

Theorem 1

Deciding if $t(G)\ge k$ is NP-Complete in bipartite graphs for any $k\ge 5$.

Fig. 1.

Bipartite gadget for each clause $C_i$.

Proof

(Sketch of the proof). Given $m$ clauses $\mathcal {C}=\{C_1,\ldots ,C_m\}$ on variables $X=\{x_1, \ldots ,x_n\}$ as an instance of $3$ -SAT, we denote the three literals of $C_i$ by $\ell _{i,1}$, $\ell _{i,2}$ and $\ell _{i,3}$. We construct a graph $G$ as follows. For each clause $C_i$ of $\mathcal {C}$, add to $G$ a gadget as the one of Fig. 1. Then, for each pair of literals $\ell _{i,a}, \ell _{j,b}$ such that one is the negation of the other, add a vertex $y_{(i,a),(j,b)}$ adjacent to $w_{i,a}$ and $w_{j,b}$. Let $Y$ be the set of all vertices created this way. Finally, add a vertex $z$ adjacent to all vertices in $Y$ and a pendant vertex $z'$ adjacent to only $z$. Denote the sets $\{u^A_{i,1}, u^A_{i,2}, u^A_{i,3},u^B_{i,1}, u^B_{i,2}, u^B_{i,3}\}$ and $\{w_{i,1}, w_{i,2}, w_{i,3}\}$ by $U_i$ and $W_i$, respectively. Let $U = \cup _{1\le i\le m} U_i$, $W = \cup _{1\le i\le m} W_i$ and $L$ be the set of vertices of degree one in $G$.

We first consider the case $k=5$. We show that $\mathcal {C}$ is satisfiable if and only if $G$ contains a hull set with percolation time at least 5.

Suppose that $\mathcal {C}$ has a truth assignment. For each clause $C_i$, let $k_i$ denote an integer in $\{1,2,3\}$ such that $\ell _{i,k_i}$ is true. Let $S' = \{u^A_{i,k_i} : 1\le i \le m\}$ and $S = S'\cup L$. It is easy to see (from Fig. 1) that all vertices in the clause gadgets are infected in time at most 4. It is also easy to see that $\{w_{i,k_i}: 1\le i \le m\}\subset I^1(S)$ (that is, $S$ infects $w_{i,k_i}$ in time 1 for every $1\le i \le m$). Moreover, $\{w_{i,k'_i}: k'_i\ne k_i, 1\le i \le m\}\subset I^3(S)$, but $\{w_{i,k'_i}: k'_i\ne k_i, 1\le i \le m\}\cap (I^1(S)\cup I^2(S))=\emptyset$ (that is, $S$ infects all the other $w_{i,k'_i}$ in time exactly 3). Since we used a truth assignment, we have that all vertices of $Y$ are infected in time exactly 4 and consequently the vertex $z$ is infected in time 5. Therefore, $G$ has percolation time at least $5$.

Now, suppose that $t(G)\ge 5$ and let $S$ be any hull set of $G$ with $t(S)\ge 5$. Note that $L\subseteq S$; also for any clause $C_i$, we have $U_i\cap S \ne \emptyset$ because $|N(u^A_{i,j})-U_i|\le 1$ and $|N(u^B_{i,j})-U_i|\le 1$, for all $i,j$. This implies that $W\subseteq I^3(S)$, $U\cup Y\subseteq I^4(S)$ and $z\in I^5(S)$. Furthermore, if $Y\cap I^3(S)\not = \emptyset$ then $z\in I^4$ and $t(S)\le 4$, a contradiction. Then $Y\cap I^3(S)=\emptyset$, which means that no pair $\{u^C_{i,a}, u^D_{j,b}\}$, $C,D\in \{A,B\}$, where $\ell _{i,a}$ is the negation of $\ell _{j,b}$, is in $S$. This means that assigning true to each $\ell _{i,j}$ for which $u^C_{i,j}\in S$, $C\in \{A,B\}$, gives us an assignment that satisfies $\mathcal {C}$.

For values $k>5$, it suffices to subdivide the edge $zz'$ into a path $P$ of length $k-5$, appending a new leaf vertex to each vertex in $P$.   $\blacksquare$

3 $t(G)\ge 3$ Is $\varTheta (mn^3)$-Time Decidable in Bipartite Graphs

The following theorem is the main result of this section.

Theorem 2

Deciding if $t(G)\ge 3$ is $\varTheta (mn^3)$-time solvable in bipartite graphs.

To prove this, we obtain an important structural result. Given a vertex $u$ of a graph $G$, let $N_d(u)$ be the set of all vertices at distance $d$ from $u$. Let $N(u)=N_1(u)$, $N[u]=N(u)\cup \{u\}$ and $N_{\ge d'}(u)=\cup _{d\ge d'}N_d(u)$. Let $T_0$ be the set of vertices with degree 1.

Lemma 1

Let $G$ be a bipartite graph. Then $t(G)\ge 3$ if and only if there are three vertices $u$, $v$ and $s$ such that $v\in N(u)$, $s\in N_2(u)$ and $T_0\cup N_{\ge 3}(u)\cup \{v,s\}$ percolates $u$ at time 3.

Because of space restrictions, we give only the main ideas of the proof (the proofs are in the appendix).

Proof

(Sketch of the proof). Firstly, suppose that $t(G)\ge 3$. Then there exists a hull set $S'$ and a vertex $u$ such that $S'$ percolates $u$ at time 3. It is not difficult to see that $T_0\subseteq S'$ and that $S=S'\cup N_{\ge 3}(u)$ is also a hull set which percolates $u$ at time 3. If $S$ contains a vertex in $N(u)$, let $v$ be such a vertex. Otherwise, let $v$ be a neighbour of $u$ with smaller percolating time with respect to the hull set $S$. Since the graph is bipartite, the distance from $v$ to any other vertex of $N(u)$ is at least two. Then it is not difficult to see that all vertices in $N(u)$ percolated at time $\ge 2$ by $S$ are also percolated at time $\ge 2$ by $S\cup \{v\}$. By analysing two possibilities about the vertices in $N(u)-\{v\}$, we can conclude (using the fact that the graph is bipartite) that there exists a vertex $s\in N_2(u)\setminus N(v)$ such that $S\cup \{v,s\}$ also percolates $u$ at time 3. Moreover we can prove that $(S\setminus (N(u)\cup N_2(u)))\cup \{v,s\}$ percolates $u$ at time 3 and we are done.

Secondly, suppose that there are three vertices $u$, $v$ and $s$ such that $v\in N(u)$, $s\in N_2(u)$ and $S_0=T_0\cup N_{\ge 3}(u)\cup \{v,s\}$ percolates $u$ at time 3. We then show how to construct a hull set $S$ such that $t(S)\ge 3$. We begin with $S=S_0$. Each step adds one vertex to $S$ and, at the end of each step, it is guaranteed that $S_i$ percolates $u$ at time $\ge 2$ and percolates at least one vertex in $\{u\} \cup N(u)$ at time $\ge 3$. Let $S_i$ be the constructed set at the end of step $i$. If $S_i$ is not a hull set, we can prove that there are two adjacent vertices $q\in N_2(u)$ and $w\in N(u)$ which are not percolated by $S_i$. Let $S_{i+1}=S_i\cup \{q\}$. It is not difficult to see that $S_{i+1}$ also percolates $u$ at time $\ge 2$. We then prove that $S_{i+1}$ percolates $w$ at time $\ge 3$. If $S_{i+1}$ is a hull set, we are done. Otherwise, repeat the construction until obtaining a hull set.   $\blacksquare$

The idea of the algorithm is as follows. Considering that the graph is connected, the algorithm selects in each step a vertex $u$ and obtains the sets $N(u)$, $N_2(u)$, $N_{\ge 3}(u)$ and $T_0$ in time $O(m)$. After, the algorithm selects a vertex $v$ in $N(u)$ and a vertex $s$ in $N_2(u)$ and, then, computes the percolation process of $T_0\cup N_{\ge 3}(u)\cup \{v,s\}$ in time $O(m)$ for, at most, three steps. If, for some triple $(u,v,s)$, $u$ is percolated in time $3$, return that $t(G)\ge 3$. Otherwise, return that $t(G)<3$.

4 $t(G)\ge 3$ Is $\varTheta (mn^5)$-Time Decidable in General Graphs

The following theorem is the main result of this section.

Theorem 3

Deciding if $t(G)\ge 3$ is $\varTheta (mn^5)$-time solvable in general graphs.

To prove this, we obtain an important structural result. Let $u$ and $v$ be vertices of $G$. Let $k$ be such that $v\in N_k(u)$. The following definitions are technical, but represent a simple fact: if $v$ is a separator (that is, its removal disconnects the graph) and some connected component of $G-v$ contains only vertices of $N_{k+1}(u)$, then any hull set must contain at least one vertex of this component.

Let $\mathcal {T}_0^u$ be the family of subsets of $V(G)$ such that $T_0\in \mathcal {T}_0^u$ if and only if, for every separator $v$ and every connected component $H_{v,i}$ of $G-v$ such that $u\not \in V(H_{v,i})$ and $V(H_{v,i} \subseteq N(v)$, $T_0$ contains exactly one vertex of $H_{v,i}$, and every vertex of $T_0$ satisfies this property.

Lemma 2

Let $G$ be a simple graph. Then $t(G)\ge 3$ if and only if there is a vertex $u$, a subset $T_0\in \mathcal {T}^u_0$ and a subset $F$ with $|F|\le 4$ such that $T_0\cup N_{\ge 3}(u)\cup F$ percolates $u$ at time 3.

Moreover, we prove that any set of the family $\mathcal {T}^u_0$ can be chosen. That is, if $T_0\cup N_{\ge 3}(u)\cup F$ percolates $u$ at time 3 for some $T_0\in \mathcal {T}^u_0$, then $T'_0\cup N_{\ge 3}(u)\cup F$ also percolates $u$ at time 3 for any $T'_0\in \mathcal {T}^u_0$.

Because of space restrictions, we give only the main ideas of the proof (the proofs are in the appendix).

Proof

(Sketch of the proof). Firstly, suppose that $t(G)\ge 3$. Then there exists a hull set $S'$ and a vertex $u$ such that $S'$ percolates $u$ at time 3. Since $S'$ is a hull set, we can prove that there is a subset $T_0\subseteq S'$ such that $T_0\in \mathcal {T}^u_0$. It is not difficult to see that $S=S'\cup N_{\ge 3}(u)$ is also a hull set which percolates $u$ at time 3. Let $F'=S\setminus (T_0\cup N_{\ge 3}(u))=(S\cap N_{\le 2}(u))\setminus T_0$. If $|F'|\le 4$, then let $F=F'$ and we are done. Otherwise, we can prove with some effort that there exists a subset $F\subseteq N_{\le 2}(u)$ with $|F|\le 4$ such that $(S\setminus F')\cup F$ percolates $u$ at time 3, and we are done.

Now suppose that there is a vertex $u$, a subset $T_0\in \mathcal {T}^u_0$ and a subset $F$ with $|F|\le 4$ such that $S_0=T_0\cup N_{\ge 3}(u)\cup F$ percolates $u$ at time 3. We then show how to construct a hull set $S$ such that $t(S)\ge 3$. We begin with $S=S_0$. Each step adds one vertex to $S$ and, at the end of each step, it is guaranteed that $S_i$ percolates some vertex $u_i$ at time $\ge 3$ ($u_0=u$) and percolates $u$ at time $\ge 2$. Let $S_i$ be the constructed set at the end of step $i$. If $S_i$ is a hull set, we are done. So, assume that $S_i$ is not a hull set. Let $Y_i$ be the set of vertices not percolated by $S_i$.

At first, assume that there exists a vertex $y_i\in Y_i\cap N_2(u_i)$ with no neighbour percolated by $S_i$ at time $\ge 2$. Let $S'_{i+1}=S_i\cup \{y_i\}$. Clearly, $u_i$ has at most one neighbour percolated by $S_i$ at time $\le 1$ and, by the choice of $y_i$, $u_i$ is not adjacent to $y_i$. It is not difficult to prove that every neighbour of $u_i$ percolated by $S_i$ at time $\ge 2$ is also percolated by $S'_{i+1}$ at time $\ge 2$. Finally, if some neighbour $z$ of $u_i$ is not percolated by $S_i$, but is percolated by $S'_{i+1}$, it is not difficult to prove that its percolating time is $\ge 2$, since, otherwise, $z$ should have a neighbour in $S_i$, a contradiction because $z$ would have two neighbours percolated by $S_i$. Then $S'_{i+1}$ also percolates $u_i$ at time $\ge 3$ (and we let $u_{i+1}=u_i$) and it is not difficult to see that $S'_{i+1}$ also percolates $u$ at time $\ge 2$. Let $S_{i+1} = S'_{i+1} \cup N_{\ge 3}(u_{i+1})$. Since the set $S'_{i+1}$ percolates $u_{i+1}$ at time $\ge 3$, it is easy to see that the set $S_{i+1}$ also percolates $u_{i+1}$ at time $\ge 3$.

Fig. 2.

Vertices of the component $C_i$ before and after the addition of $y_i$ to $S$.

Secondly, assume that every vertex $y_i\in Y_i\cap N_2(u_i)$ has exactly one neighbour percolated by $S_i$ and its percolating time is $\ge 2$. Let $y_i\in Y_i\cap N_2(u_i)$, let $C_i$ be the connected component of $G[Y_i]$ which contains $y_i$ and let $z_i$ be the neighbour of $y_i$ with percolating time $\ge 2$. If every vertex of $C_i$ is adjacent to $z_i$, then $C_i$ has only vertices in $N(u)$ or only vertices in $N_2(u)$ (otherwise, there would be one vertex in $N_2(u)$ adjacent to $u$, a contradiction), and every vertex of $C_i$ has no neighbour in $N_3(u)$ (and consequently $z_i$ is a separator). Therefore, $T_0$ has a vertex $\ell$ in $C_i$, a contradiction since there are no vertices percolated by $S_i$ in $C_i$.

We then conclude that there exist a vertex $y'_i$ in $C_i$ whose neighbour $z'_i$ with percolating time $\ge 2$ is distinct from $z_i$ (that is, $z'_i\ne z_i$). Let $S_{i+1}=S_i\cup \{y_i\}\cup N_{\ge 3}(y'_i)$. It is not difficult to see that all vertices in $C_i$ are percolated by $S_{i+1}$. We can prove that $S_{i+1}$ percolates $y'_i$ at time $\ge 3$ and, letting $u_i=y'_i$, we are done.

After some time steps, say $t$ time steps, $S_t$ percolates all vertices of $N_2(u_i)$, since we are only including vertices from $N_2(u_i)$. It is not difficult to see that this fact implies that $S_t$ is a hull set and, since $S_t$ percolates $u_t$ at time $\ge 3$, we have that $t(G)\ge 3$.   $\blacksquare$

The idea of the algorithm is as follows. Considering that the graph is connected, the algorithm selects in each step a vertex $u$ and obtains a set $T_0\in \mathcal {T}^u_0$ in time $O(m)$ (applying breadth-first search, for example). After, the algorithm selects a subset $F$ with at most 4 vertices and computes the percolation process of $T_0\cup N_{\ge 3}(u)\cup F$ in time $O(m)$ for, at most, three steps. If, for some pair $(u,F)$, $u$ is percolated in time $3$, return that $t(G)\ge 3$. Otherwise, return that $t(G)<3$ (Fig. 2).

5 $t(G)\ge 4$ Is $\varTheta (mn^{13})$-Time Decidable in Bipartite Graphs

The following theorem is the main result of this section.

Theorem 4

Deciding if $t(G)\ge 4$ is $\varTheta (mn^{13})$-time solvable in bipartite graphs.

To prove this, we obtain an important structural result. Let $\mathcal {T}_0$ be the family of subsets of $V(G)$ such that $T_0\in \mathcal {T}_0$ if and only if $T_0$ contains all vertices with degree one and, for every pair of adjacent vertices $u$ and $v$, both with degree two, $T_0$ has either $u$ or $v$. It is easy to see that every hull set must contain a set $T_0\in \mathcal {T}_0$, since each edge $uv$ with that property induces a co-convex set (that is, $V(G)-\{u,v\}$ is convex). Clearly, the size of $\mathcal {T}_0$ can be exponential in the number of vertices. However, we can prove that we need to check only a polynomial number of subsets $T_0\in \mathcal {T}_0$.

Let $V^u$ be the subset of vertices $v\in N[u]$ such that there is an induced $P_3$ $vxy$, where $x$ and $y$ have degree two. Given a vertex $u$ and a vertex $v\in V^u$, we also define the sets $C_v^u$ and $D_v^u$: for every induced $P_3$ $vxy$, where $x$ and $y$ have degree two, $x\in C_v^u$ and $y\in D_v^u$. It is worth noting that, for every $x\in C_v^u$ and $y$ in $D_v^u\cap N(x)$, $T_0$ must contain either $x$ or $y$.

Let $\mathcal {T}^u_0$ be a family such that $T_0\in \mathcal {T}^u_0$ if and only if $N_{\ge 4}(u) \subseteq T_0$, $T_0$ contains all vertices that have degree 0, and exactly one of the cases below occurs:

• there is a vertex $v\in V^u$ such that $T_0$ has at least one vertex in $D_v^u$, at most one vertex in $C_v^u$ and, for every $v'\in V^u$, $v'\ne v$, and every $x\in C_{v'}^u$ and $y\in D_{v'}^u \cap N(x)$ where $x,y\not \in C_v^u \cup D_v^u$, $T_0$ contains $\{x,y\} \cap N_k(u)$, where $k = 2$, if $v\in N(u)$, and $k=3$, if $v = u$.

• for each vertex $v\in V^u$, $T_0$ contains all vertices in $C_v^u$, except at most one vertex $v'\in V^u$, in which case $T_0$ contains at most one vertex in $C_{v'}^u$.

It is worth noting that the set $\mathcal {T}^u_0$, for any vertex $u$, is a subset of the set $\{T_0\cup N_{\ge 4}(u):\ \forall T_0 \in \mathcal {T}_0\}$. It is also important to observe that the set $\mathcal {T}^u_0$ can be obtained in $O(n^2)$ time.

Lemma 3

Let $G$ be a bipartite graph. Then $t(G)\ge 4$ if and only if there is a vertex $u$, a subset $T_0\in \mathcal {T}^u_0$ and a subset $F$ with $|F|\le 10$ such that $T_0\cup F$ percolates some vertex at time 4.

Proof

(Sketch of the proof). Firstly, suppose that $t(G)\ge 4$. Then there is a hull set $S''$ and a vertex $u$ such that $S''$ percolates $u$ at time 4. It is easy to see that the set $S=S''\cup N_{\ge 4}(u)$ is a also a hull set that percolates $u$ at time 4. With this, there is a set $T\in \mathcal {T}_0$ such that $T_0=T\cup N_{\ge 4}(u)\subseteq S$.

Assume that there is a vertex $v\in V^u$ percolated at time $\ge 3$ by $S$ and a vertex $x\in C_v^u\setminus S$. It is not difficult to see that $x$ is percolated at time $\ge 4$ by $S$. Let $k=2$, if $v\in N(u)$, or $k = 3$, if $v=u$. Let $S'$ be the union of $S$ with all sets $\{y_1,y_2\}\cap N_k(u)$ such that $y_1\in C_{v'}^u$ and $y_2\in D_{v'}^u\cap N(y_1)$ for some $v'\in V^u$, $v'\ne v$, and $y_1,y_2\not \in C_v^u\cup D_v^u$. Since the graph is bipartite, each vertex added to $S$ is either at distance 4 from $x$ or, if it is at distance 2 from $x$, they share only one common neighbor, which is the only vertex $z$ in the set $\{N(x) \cap D_V^u\}$ (in this case, we have that $z\in S$). Then $S'$ percolates $x$ at time $\ge 4$. Therefore, we have that there is a set $T_0' \in \mathcal {T}_0^u$ such that $T_0 \subseteq S'$. Since $S'$ percolates $x$ at time $\ge 4$, it percolates some vertex at time 4. Thus, it is possible to prove that there is a set $F$, with $|F| \le 10$, such that, $F \cup T_0'$ percolates some vertex at time 4.

Now assume that all vertices in $V^u$ percolated at time $\ge 3$ by $S$ are such that all vertices in $C_v^u$ are in $S$. Since $u$ is percolated at time 4 by $S$, then either (a) there is a vertex $v\in V^u$ percolated at time $\ge 3$ by $S$ and some vertex $x \in C_v^u$ such that $S'=(S -\{x\})\cup (N(x)\cap D_v^u)$ percolates $v$ at time $\ge 3$, or, since there is at most one vertex in $V^u$ that is percolated at time $\le 2$, (b) there is at most one vertex $v\in V^u$ such that there is a vertex $x\in C_v^u\setminus S$. If (a), then $x$ is percolated at time $\ge 4$, and we are in the same case of the previous paragraph. If (b), then, if $v$ is percolated at time $\le 1$ by $S$, then it is easy to see that $S'=S\cup C_v^u$ percolates $u$ at time 4 and, if $v$ is percolated at time 2 by $S$, then $S'=S$ has at most one vertex in $C_v^u$. If we have that $v$ is percolated at time $\le 1$ or 2 by $S$, then there is a set $T_0' \in \mathcal {T}^u_0$ such that $T_0' \subseteq S'$. Since $S'$ percolates some vertex $x'$ at time 4, it is possible to prove that there is a set $F$, with $|F| \le 10$, such that, $F \cup T_0'$ percolates $x'$ at time 4.

Now, suppose that there is a vertex $u$, a set $F$, with $|F| \le 10$, and a set $T_0 \in \mathcal {T}^u_0$ such that the set $F \cup T_0$ percolates some vertex $x$ at time 4. Then, we have that the set $S_0 = F \cup T_0 \cup N_{\ge 4}(x)$ percolates $x$ at time 4.

We then show how to construct a hull set $S$ such that $t(S)\ge 4$. We begin with $S=S_0$, and, at each step, we add one vertex to $S$ and, at the end of each step, it is guaranteed that $S_i$ percolates some vertex at time 4. Let $S_i$ be the constructed set at the end of step $i$. If $S_i$ is a hull set, we are done. So, assume that $S_i$ is not a hull set. Let $Y_i$ be the set of vertices not percolated by $S_i$.

Suppose that there exists a vertex $y_i\in Y_i\cap N_2(x)$ with no neighbour percolated by $S_i$ at time $\ge 2$. Let $S_{i+1}=S_i\cup \{y_i\}$. Clearly, $x$ has at most one neighbour percolated by $S_i$ at time $\le 1$ and, by the choice of $y_i$, $u_i$ is not adjacent to $y_i$. It is possible to prove, basing ourselves heavily on the fact that the graph is bipartite, that every neighbour of $x$ that either is percolated by $S_i$ at time $\ge 3$ or it is not percolated by $S_i$, if it is percolated by $S_{i+1}$, it is percolated by $S_{i+1}$ at time $\ge 3$.

When all vertices in the set $Y_i\cap N_2(x)$ have a neighbour percolated by $S_i$ at time $\ge 2$, suppose that there exists a vertex $y_i\in Y_i\cap N_3(x)$ with no neighbour percolated by $S_i$ at time $\ge 2$. Let $S_{i+1}=S_i\cup \{y_i\}$. Since all vertices in $Y_i\cap N_2(x)$ have a neighbour percolated by $S_i$ at time $\ge 2$, it is not difficult to prove that, if a vertex in $N_2(x) \cap Y_i$ is percolated by $S_{i+1}$, it is percolated by $S_{i+1}$ at time $\ge 2$. Thus, all vertices in $N_(x)$ that either are percolated at time $\ge 3$ by $S_i$ or are not percolated by $S_{i+1}$ are percolated by $S_{i+1}$ at time $\ge 3$. Therefore, $x$ is percolated by $S_{i+1}$ at time 4. It is worth noting the fact that $y_i$ is at distance at least two of every vertex that is percolated at time $\ge 2$ by $S_i$ and is adjacent to some vertex in $N_2(x) \cap Y_i$, which implies that it is not possible to go back to the previous state, i.e., it is not possible that there is a vertex in $Y_i\cap N_2(x)$ with no neighbour percolated by $S_{i+1}$ at time $\ge 2$.

When all vertices in the set $Y_i\cap N_2(x)$ and in the set $Y_i\cap N_3(x)$ have a neighbour percolated by $S_i$ at time $\ge 2$, let $C_i$ be any connected component of $G[Y_i]$. We have that every vertex of $C_i$ has exactly one neighbour outside $C_i$, which is percolated at time $\ge 2$ by $S_i$. We have that $C_i$ has at least 3 vertices because, otherwise, one vertex of $C_i$ would also be in $T_0$ and, consequently, in $X_i$. Thus, since the graph is bipartite, there are two vertices $y_i$ and $y_i'$ that are at distance 2 of each other. It is possible to prove that the set $S_i \cup \{y_i\}$ percolates $y_i'$ at time $\ge 4$ because it percolates all vertices adjacent to $y_i$ at time $\ge 3$. Also, in every connected component of $G[Y_i]$, there is at least one vertex in $N_2(x)$ and one vertex in either $N(x)$ or $N_3(x)$. If $y_i'$ is in $N_2(x)$ (resp. $N(x)$ or $N_3(x)$), let $S_{i+1} = S_i \cup \{y_i\} \cup ((Y_i - V(C_i)) \cap N_2(x))$ (resp. $S_{i+1} = S_i \cup \{y_i\} \cup ((Y_i - V(C_i)) \cap (N(x) \cup N_3(x)))$). It is possible to prove that $S_{i+1}$ percolates all the remaining connected component of $G[Y_i]$ and, thus, it is be a hull set. Also, it is possible to prove that $S_{i+1}$ percolates $y_i'$ at time $\ge 4$. Therefore, $S_{i+1}$ is a hull set that percolates $y_i'$ at time $\ge 4$.   $\blacksquare$

Fig. 3.

Vertices of the component $C_i$ before and after the addition of $y_i$ to $S$.

The idea of the algorithm is as follows. Considering that the graph is bipartite and connected, the algorithm selects in each step a vertex $u$, a set $T_0\in \mathcal {T}^u_0$ and a subset $F$ with at most 10 vertices, and computes the percolation process of $T_0\cup F$ for at most 4 steps (recall that $T_0\supseteq N_{\ge 4}(u)$). If, for some triple $(u,T_0,F)$, some vertex $x$ is percolated in time 4, return that $t(G)\ge 4$. Otherwise, return that $t(G)<4$. Since there are $O(n^2)$ sets in $\mathcal {T}^u_0$ that can also be computed in $O(n^2)$-time, then the algorithm decides if $t(G)\ge 4$ in $O(mn^{13})$ time (Fig. 3).

6 Conclusion

In this paper, we showed the NP-Completeness of the maximum time percolation problem for a fixed $k=5$ for bipartite graphs, and showed polynomial computable characterizations of general and bipartite graphs for a fixed $k=3$ and of bipartite graphs for a fixed $k=4$. Using these results, since the NP-Completeness was proved in [7] for a fixed $k\ge 4$ for general graphs, we were able to solve the remaining open questions regarding the maximum time percolation problem for a fixed $k$ and showed the threshold for polynomiality in general graphs ($k=3$) and in bipartite graphs ($k=4$).

We conclude with some interesting directions for future investigation. Can the maximum time percolation problem in induced subgraphs and subgraphs of $d$-dimensional grids be solved in polynomial time? Can the complexity of the algorithms, which is directly related to the size of the sets that initially percolate some vertex at time $k$, be improved? Is there a relation between the $P_3$-Caratheódory number [26] and the size of the sets that initially percolate some vertex at time $k$?