On Graph Burning and Edge Burning

Given an instance $(G=(V,E),k)$ of Vertex Cover we construct a graph $G^{\prime }$ as follows:

• $\mathrm{■}$

  for every vertex $v$ of $V$, we add two adjacent vertices $v^1$ and $v^2$ in $G^{\prime }$,

• $\mathrm{■}$

  for every edge $\{u,v\}\in E$,

  • –

    we add two vertices $uv$ and $vu$ in $G^{\prime }$, additionally, we add the edges $\{u^1,uv\}$, $\{v^1,vu\}$ and $\{uv,vu\}$ in $G^{\prime }$. We then replace the edge $\{uv,vu\}$ by a path with $2n+3$ vertices, where $uv$ and $vu$ are the endpoints of the path. Let $w$ be the middle vertex of the path.

  • –

    we add a path $T_{uv}$ with $n+1$ vertices and make one of its endpoints adjacent to $w$.

• $\mathrm{■}$

  we add $2n+5$ pairs of adjacent vertices. Every pair is isolated with respect to the rest of the graph.

Notice that $G^{\prime }$ can be constructed in polynomial time.

We claim that $(G,k)$ is a $\mathrm{𝗒𝖾𝗌}$-instance for Vertex Cover if and only if $G^{\prime }$ has a burning sequence of length at most $k+2n+5$.

Assume that $G$ has a vertex cover $C$ of size at most $k$. We find an edge burning sequence $F$ for $G^{\prime }$. First, we add to $F$ the edges $\{v_i^1,v_i^2\}$ of $G^{\prime }$ that correspond to the vertices of $C$ in arbitrary order. We denote this set of edges as $C^{\prime }$. This means in the first $k$ rounds all the edges of $C^{\prime }$ are burned. After that we choose the $2n+5$ isolated edges of $G^{\prime }$ as burning sources for $F$. Hence, we need $k+2n+5$ rounds in order to burn these edges. Now we show that the rest edges can be burned within $k+2n+5$ rounds. As we said in the first $k$ rounds all the edges of $C^{\prime }$ are burned. Moreover, for every edge $\{u^1,u^2\}$ that does not belong to $C^{\prime }$ there is an edge of $C^{\prime }$ that is in distance $2n+5$ since $C$ is vertex cover of $G$. This means all the edges $\{u^1,u^2\}$ can be burned in the next $(2n+5)$ rounds. Observe also that all the edges between an edge of $C^{\prime }$ and an edge $\{u^1,u^2\}\notin C^{\prime }$ are in distance at most $2n+4$ from some edge of $C^{\prime }$. Furthermore, the edges of a path $T_{uv}$ are in distance at most $2n+4$ from some edge $\{v^1,v^2\}\in C^{\prime }$. Thus, all the edges of $G^{\prime }$ can be burned in $k+2n+5$ rounds.

For the opposite direction, assume that $G^{\prime }$ has a burning sequence $F$ of length at most $k+2n+5$. We show how to build a vertex cover $C$ for $G$ of size at most $k$. For every edge $\{u,v\}\in E$, we define $H_{uv}$ to be a subgraph of $G^{\prime }$ that contains the edges $\{u^1,u^2\}$ and $\{v^1,v^2\}$, all the edges in distance at most $n+2$ either from $\{u^1,u^2\}$ or $\{v^1,v^2\}$, all the edges in the path of $u^1$ to $v^1$ and the edges of the path $T_{uv}$. For every $H_{uv}$ and for each burning source $e$ in it, we check whether the distance between $e$ and $\{u^1,u^2\}$ is smaller than the distance between $e$ and $\{v^1,v^2\}$. If the former holds then we put $u$ in $C$ otherwise we put $v$ in $C$. We break ties arbitrarily. Next we prove that $C$ is a vertex cover of $G$. Assume that there is an edge $\{u,v\}\in E$, where neither $u$ nor $v$ belongs to $C$. This means that every burning source $e\in G^{\prime }$ is closer to some $\{x,y\}\in G^{\prime }$ other than $\{u^1,u^2\}$ and $\{v^1,v^2\}$. Thus, $H_{uv}$ does not contain any edge burning source. Observe that the distance between an edge $e$ outside of $H_{uv}$ and the last edge of $T_{uv}$ is at least $n+2n+5$. Hence, we need at least $n+2n+6$ rounds in order to burn the edges of $H_{uv}$ which is strictly larger than $k+2n+5$. This leads to a contradiction, and so $C$ is a vertex cover since for every edge $\{u,v\}\in E$ at least one of the endpoints belong to $C$. Finally, since we need $2n+5$ rounds to burn the isolated edges, we get that the vertex cover is at most $k$. $◀$

By construction, the graph $G^{\prime }$ in the proof of Theorem 6 is disconnected. Next, we can adjust the proof of Theorem 6 and show that the Edge Burning problem is also NP-hard on connected graphs. More precisely, let $G$ be a graph and let $v$ be a vertex of $G$. We extend this graph by adding a pair of adjacent vertices $\{x,y\}$ and make the vertex $x$ adjacent to $v$ of $G$. Observe that the minimum vertex cover of the new graph, $H$, is one more than in $G$, since we have added the edge $\{x,y\}$ and so one of the endpoints has to belong to the vertex cover. Let $\mathrm{\ell }$ the minimum vertex cover of $H$. Next, we follow the construction of Theorem 6 but instead of using the isolated pair of adjacent vertices, we add a path $P=(x^2,Q,Q^{\prime },e_1,Q^{\prime },e_2,Q^{\prime },\mathrm{\dots },Q^{\prime },e_{2n+5})$, where $Q$ is a sequence of $(\mathrm{\ell }+2n+4)$ vertices, $Q^{\prime }$ is a sequence of $(2n+4)$ vertices, and $e_1,e_2,\mathrm{\cdots },e_{2n+5}$ are pairs of adjacent vertices that correspond to the isolated pairs of adjacent vertices of Theorem 6. Notice that the number of the edges of $P\setminus \{x^2,Q\}$ is $(2n+4)(2n+5)+(2n+5)={(2n+5)}^2$. By Corollary 4 we get that any edge burning sequence for $P\setminus \{x^2,Q\}$ contains $2n+5$ edges.

Again, we wish to show that the extended graph has a vertex cover of size at most $\mathrm{\ell }$ if and only if there is an edge burning sequence with at most $\mathrm{\ell }+2n+5$ sources. Observe that any vertex cover in the extended graph contains either $x$ or $y$. Without loss of generality assume that $x$ belong to vertex cover, otherwise we can swap $y$ and $x$. For one direction, we can burn all the edges by burning first the edge $\{x^1,x^2\}$, next the remaining edges that correspond to the vertices of the vertex cover and finally the edges of the path $P\setminus \{x^2,Q\}$ by using the algorithm for finding an edge burning sequence on a path previously described. For the other direction, assume that there is an edge burning sequence of size $\mathrm{\ell }+2n+5$. Then, since the number of the edges of the path $P\setminus \{x^2,Q\}$ is ${(2n+5)}^2$ we need $2n+5$ sources to burn it. Moreover, the distance between these sources and $\{x^1,x^2\}$ is $\mathrm{\ell }+2n+5$. Thus, the remaining $\mathrm{\ell }$ sources need to be in $H$, and so, the corresponding vertices will be the vertex cover of size $\mathrm{\ell }$.

Hence, combining Theorems 3 and 6 and since the line graph of a connected graph is a connected claw-free graph, we get the following result.

The first claim is straightforward since in the first round we can burn only one edge. Assume now that $Eb(G)=2$, this means that there are two sources, $(e_1,e_2)$. If $G$ has only the edges $e_1$ and $e_2$ then we have the claim. Assume that there are more than two edges in the graph. Since $Eb(G)=2$ and $e_1$ is the first source, the edges of $E(G)\setminus \{e_1,e_2\}$ are incident to $e_1$ in order to be burned in the second round. Hence, there is at most one edge non incident to $e_1$ and that can be the edge $e_2$. In the other direction, we assume first there is an edge $e$ such that every other edge of the graph is incident to $e$. Then if we burn $e$ in the first round then all the other edges will be burned in the second round. Observe that if there is exactly one edge non-incident to $e$ we can also burn this edge at the end of the second round. Thus, in both cases the $Eb(G)=2$. $◀$ Using Observation 8, we present an algorithm to compute the edge burning number for split graphs in the following theorem.

Let $G=(V,E)$ be a split graph with clique partition $(C,I)$. Based on Observation 8, we can check in linear time whether $Eb(G)=2$; otherwise, we show that it must be $Eb(G)=3$. In the first round we arbitrarily burn an edge from the clique $C$. In the second round all the incident edges will be burned and we burn again one of the remaining unburned edges. At this point every vertex of the clique has at least one burned incident edge. Thus, in the third round all the edges of the clique will be burned as well as all the edges between the vertices of the clique and the vertices of the independent set. Since there is no edge between the vertices of $I$, all the edges of the graph have been burned. Hence, $Eb(G)=3$. Clearly, the above procedure can be implemented in linear time. $◀$

Even in the case where the graph is a complete split graph, i.e., every vertex of the independent set is adjacent to every vertex of the clique, the edge burning number is at most $3$, while the burning number of a complete split graph is $2$. For example, see Figure 2.

Next, we consider the class of cographs. Let $G=(V,E)$ and $H=(U,F)$ be two undirected graphs with $V\cap U=\mathrm{\varnothing }$. The disjoint union of $G$ and $H$ is the graph obtained from the union of $G$ and $H$, denoted by $G\oplus H=(V\cup U,E\cup F)$. The complete join of $G$ and $H$ is the graph obtained from the union of $G$ and $H$ and adding edges between every pair of vertices that belong to different graphs, denoted by $G\otimes H=(V\cup U,E\cup F\cup \{vu\mid v\in V,u\in U\})$. A graph is a cograph if it can be generated from single-vertex graphs and recursively applying the disjoint union and complete join operations. By definition, the complement of a cograph is also a cograph. Cographs are exactly the graphs that do not contain chordless paths on $4$ vertices, $P_4$, as induced subgraphs [7], and they can be recognized in linear time [8]. In the following theorem, we present an algorithm to compute the edge burning number for a cograph.

Let $G=(V,E)$ be a connected cograph, then the last operation need to be complete join. Let $G=H_1\otimes H_2$. Using Observation 8 in linear time we can determine if $Eb(G)=2$; otherwise we show that the $Eb(G)=3$. We consider as a first source an edge $vu$ such that $v\in H_1$ and $u\in H_2$. By definition, $v$ is adjacent to every vertex $H_2$ and $u$ is adjacent to every vertex $H_1$, and so, at the end of the second round all the vertices of $G$ have at least one burned incident edge. Thus, in the third round all the edges will be burned. The above steps can be implemented in linear time by using a suitable data structure, called cotree [8], (see for e.g., Figure 3). The construction of the cotree of $G$ takes time $O(n+m)$ [8]. $◀$

For any graph $G$ it is known that $\sqrt{𝖽+1}\le b(G)\le \mathrm{𝗋𝖺𝖽}+\mathrm{𝟣}$ [4]. Moreover, by Theorem 2 we have $b(G)-1\le Eb(G)\le b(G)+1$. The observation yields from combining these two results. $◀$ Based on the observation above, we can obtain a trivial XP algorithm for the edge burning problem parameterized by the diameter $𝖽$ of the graph. We compute all the subsets of edges of size at most $𝖽$ and for each such subset we check all the permutations. Every permutation can be considered as a sequence for the edge burning problem. Observe that this can be done in $O(𝖽!\cdot {𝗇}^{\mathrm{𝟤}(𝖽+\mathrm{𝟣})})$ time. An XP algorithm has also been given in [12] for the graph burning problem parameterized by the diameter. An interesting direction to explore next is to find a parameter with respect to which the edge burning problem admits an FPT algorithm. We consider graphs with bounded neighborhood diversity and show that the edge burning problem is FPT and admits a linear kernel when parameterized by neighborhood diversity.

The neighborhood diversity has been defined by Lampis [15]. For a graph $G(V,E)$, two vertices $x$ and $y$ in $V$ have the same type if $N(x)\setminus \{y\}=N(y)\setminus \{x\}$.

Observe that the vertices of a given type not only have the same (closed) neighborhood in $G$, but also form either a clique or an independent set in $G$. Further, there exists a polynomial time algorithm that finds a minimum partition of $V$ into neighborhood types [15]. In the following theorem, we present a linear kernel for the edge burning problem parameterized by the neighborhood diversity of the input graph, similar to [11] for the graph burning problem.

Let $G=(V,E)$ be a graph with neighbohood diversity, $\mathrm{𝗇𝖽}$, and let $C_1,C_2,\mathrm{\cdots },C_{\mathrm{𝗇𝖽}}$ be the type classes of $G$. We show that edge burning admits a $5\mathrm{𝗇𝖽}$-kernel. To do that, we apply one of the following reduction rules for every type class in $G$:

To show that the rule is sound, observe that if $C_i$ forms a clique and contains at least $5$ vertices then in at most 3 rounds all the incident edges to the vertices of $C_i$ can be burned. More precisely, if an edge incident to a vertex of $C_i$ is burned, then in the next round all edges of $G[C_i]$ that are incident to that vertex will be burned. Thus, in the following round all the edges of $G[C_i]$ will be burned as well as all the incident edges from others classes to the vertices of $C_i$. On the other hand, if we set fire on an edge of $G[C_i]$ then in two rounds we have that every vertex of $G[C_i]$ have at least one burned incident edge, and so, in the next round all the rest incident edges to $C_i$ will be burned. Hence, it is enough to keep 5 vertices for such a class $C_i$ since a clique with 5 vertices needs 3 rounds in order to be burned.

To show that the rule is sound, observe that if we pick an edge incident to a vertex of $C_i$ as a source, then in the next round all the vertices of $C_i$ will have at least one burned incident edge. This is because the endpoint of the source edge that is not in $C_i$ is adjacent to every vertex of $C_i$. Thus, in the following round all incident edges to the vertices of $C_i$ will be burned. Now, observe that the same holds even if an edge incident to a neighbor of $C_i$ burned, since the vertices of $C_i$ have the same neighborhood. Therefore, it is enough to keep 3 vertices. Finally, Rules 13.1 and 13.2 can be applied in polynomial time and the resulting graph has $\mathrm{𝗇𝖽}$ classes with at most 5 vertices in each class. $◀$ In the following sections, we present our results on graph burning.

Let $P$ be any diametral path in the tree, $𝖽$ be the diameter of the tree, and $c$ be a center of the tree. Assume by contradiction that $c$ is not contained in $P$. Let $x_1$ and $x_2$ be the two endpoints of the path $P$. Let ${𝗏}_{\mathrm{𝗆𝗂𝖽}}$ be a vertex contained in $P$ and is at a distance at least $\lfloor 𝖽/2\rfloor$ from $x_1$ and $x_2$. Therefore, $\mathrm{𝖾𝖼𝖼}({𝗏}_{\mathrm{𝗆𝗂𝖽}})\le \lceil 𝖽/\mathrm{𝟤}\rceil$. Otherwise, it will contradict that the length of the diameter of the tree is $𝖽$. Further, it also implies that the eccentricity of any center for the tree is $\le \lceil 𝖽/2\rceil$. Next, we consider the unique path between ${𝗏}_{\mathrm{𝗆𝗂𝖽}}$ and $c$ in the tree.

1. 1.

   $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗏}_{\mathrm{𝗆𝗂𝖽}})>\mathrm{𝟣}$: Consider the following paths: from $c$ to $x_1$ and from $c$ to $x_2$. At least one of the two paths must contain ${𝗏}_{\mathrm{𝗆𝗂𝖽}}$. Without loss of generality, suppose the path from $c$ to $x_1$ contains ${𝗏}_{\mathrm{𝗆𝗂𝖽}}$. This implies that $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗑}_{\mathrm{𝟣}})=\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗏}_{\mathrm{𝗆𝗂𝖽}})+\mathrm{𝖽𝗂𝗌𝗍}({𝗏}_{\mathrm{𝗆𝗂𝖽}},{𝗑}_{\mathrm{𝟣}})>\mathrm{𝟣}+\lfloor 𝖽/\mathrm{𝟤}\rfloor \ge \lceil 𝖽/\mathrm{𝟤}\rceil$. Therefore, $\mathrm{𝖾𝖼𝖼}(c)>\lceil 𝖽/2\rceil$. But this contradicts that $c$ is a center of the tree because there exists a vertex ${𝗏}_{\mathrm{𝗆𝗂𝖽}}$ with $\mathrm{𝖾𝖼𝖼}({𝗏}_{\mathrm{𝗆𝗂𝖽}})\le \lceil 𝖽/\mathrm{𝟤}\rceil$.

2. 2.

   $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗏}_{\mathrm{𝗆𝗂𝖽}})=\mathrm{𝟣}$: In this case both the paths, from $c$ to $x_1$ and from $c$ to $x_2$, must contain ${𝗏}_{\mathrm{𝗆𝗂𝖽}}$. We consider the following two scenarios.

   1. (a)

      Diameter $𝖽$ is even: For $x_i,i\in \{1,2\}$, we have $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗑}_{𝗂})=\mathrm{𝟣}+\mathrm{𝖽𝗂𝗌𝗍}({𝗏}_{\mathrm{𝗆𝗂𝖽}},{𝗑}_{𝗂})=\mathrm{𝟣}+𝖽/\mathrm{𝟤}>\lceil 𝖽/\mathrm{𝟤}\rceil$. Therefore, $\mathrm{𝖾𝖼𝖼}(c)>\lceil 𝖽/2\rceil$ and it contradicts that $c$ is a center.

   2. (b)

      Diameter $𝖽$ is odd: For $x_i,i\in \{1,2\}$, consider the $x_i$ for which $\mathrm{𝖽𝗂𝗌𝗍}({𝗑}_{𝗂},{𝗏}_{\mathrm{𝗆𝗂𝖽}})=(\mathrm{𝟣}+𝖽)/\mathrm{𝟤}$. Then, $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗑}_{𝗂})=\mathrm{𝟣}+\mathrm{𝖽𝗂𝗌𝗍}({𝗏}_{\mathrm{𝗆𝗂𝖽}},{𝗑}_{𝗂})=\mathrm{𝟣}+\frac{𝖽+\mathrm{𝟣}}{\mathrm{𝟤}}>\lceil 𝖽/\mathrm{𝟤}\rceil$. Therefore, $\mathrm{𝖾𝖼𝖼}(c)>\lceil 𝖽/2\rceil$ and it contradicts that $c$ is a center.

Therefore, if $c$ is a center of the tree and $P$ is any diametral path of the tree, then $P$ must contain $c$. Hence the lemma. $◀$ Next we make the following observation about two paths on a tree.

The proof follow immediately from the fact that a tree is an acyclic graph. Otherwise, if the common vertices do not form an induced path, then a subset of vertices belonging to only $P_1$, a subset of vertices belonging to only $P_2$, and a subset of vertices common to $P_1$ and $P_2$ form a cycle. Furthermore, since the common vertices induce a path, it must be a subpath of the two overlapping paths. $◀$ Before presenting the algorithm, we prove some useful properties.

Suppose not, and there exists an optimum solution that places the first activator on a vertex other than the centers. Since we are constrained to place all the activators on a path, a center can be burned only in the second or higher rounds. Since we assumed that the diametral paths have only centers as the common vertices and at least two diametral paths are there, the solution would require $\ge \mathrm{𝟤}+\lceil 𝖽/\mathrm{𝟤}\rceil$ rounds to burn the tree completely. However, from Lemma 17, every diametral path in a tree must contain every center. Therefore, any solution that places the first activator in a center would require $\le \mathrm{𝟣}+\lceil 𝖽/\mathrm{𝟤}\rceil$ rounds to completely burn the tree, contradicting that the solution we started with is an optimum solution. Hence the Lemma. $◀$

From Lemma 19, the first activator must be on a center. After that the optimum may place the remaining activators on one of the diametral paths. But it will take $\lceil 𝖽/\mathrm{𝟤}\rceil$ rounds to burn the other diametral paths. Therefore, any optimum solution takes $\mathrm{𝟣}+\lceil 𝖽/\mathrm{𝟤}\rceil$ rounds. $◀$

Let $P^{\prime }$ be a non diametral path and assume that all the activators in an optimum solution are on the path $P^{\prime }$. Let $P$ be a diametral path and $𝖽$ be the length of the diameter. Note that any optimum solution takes at most $1+\lceil 𝖽/2\rceil$ rounds. We have the following two cases.

1. 1.

   $P^{\prime }$ and $P$ are edge disjoint: In this case, $P^{\prime }$ must contain one of the centers, say $c$, and the first activator must be on that center. Otherwise, the solution will take $>1+\lceil 𝖽/2\rceil$ rounds contradicting that it is optimal. Placing all the activators on $P^{\prime }$ starting with the first activator on the center $c$ takes $1+\lceil 𝖽/2\rceil$ rounds. Let ${𝗑}_{\mathrm{𝟣}}^{\prime }$ and ${𝗑}_{\mathrm{𝟤}}^{\prime }$ be the endpoints of path $P^{\prime }$. Clearly, $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗑}_{\mathrm{𝟣}}^{\prime })\le \lceil 𝖽/\mathrm{𝟤}\rceil$ and $\mathrm{𝖽𝗂𝗌𝗍}(𝖼,{𝗑}_{\mathrm{𝟤}}^{\prime })\le \lceil 𝖽/\mathrm{𝟤}\rceil$. Therefore, placing all the activators on $P$ starting with the first activator on the center $c$ yields another optimal solution.

2. 2.

   $P^{\prime }$ and $P$ are not edge disjoint: From Observation 18, the common vertices between $P$ and $P^{\prime }$ induce a subpath. Let $\widehat{P}$ be that subpath. Let $\widehat{{𝗑}_{\mathrm{𝟣}}}$ and $\widehat{{𝗑}_{\mathrm{𝟤}}}$ be the endpoints of $\widehat{P}$. Let ${𝗑}_{\mathrm{𝟣}}^{\prime }$ be the endpoint of $P^{\prime }$ nearest to $\widehat{{𝗑}_{\mathrm{𝟣}}}$ and ${𝗑}_{\mathrm{𝟤}}^{\prime }$ be the endpoint of $P^{\prime }$ nearest to $\widehat{{𝗑}_{\mathrm{𝟤}}}$. Similarity, let ${𝗑}_{\mathrm{𝟣}}$ be the endpoint of $P$ nearest to $\widehat{{𝗑}_{\mathrm{𝟣}}}$ and ${𝗑}_{\mathrm{𝟤}}$ be the endpoint of $P$ nearest to $\widehat{{𝗑}_{\mathrm{𝟤}}}$. Clearly, $\mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟣}}},{𝗑}_{\mathrm{𝟣}})\ge \mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟣}}},{𝗑}_{\mathrm{𝟣}}^{\prime })$ and $\mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟤}}},{𝗑}_{\mathrm{𝟤}})\ge \mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟤}}},{𝗑}_{\mathrm{𝟤}}^{\prime })$. Therefore, placing all the activators on $P^{\prime }$ will contribute $\max \{\mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟣}}},{𝗑}_{\mathrm{𝟣}}),\mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟣}}},{𝗑}_{\mathrm{𝟤}})\}$ many rounds in addition to burning the subpath $\widehat{P}$ and the rest of the tree. Instead, placing all the activators on $P$ will contribute $\max \{\mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟣}}},{𝗑}_{\mathrm{𝟣}}^{\prime }),\mathrm{𝖽𝗂𝗌𝗍}(\widehat{{𝗑}_{\mathrm{𝟤}}},{𝗑}_{\mathrm{𝟤}}^{\prime })\}$ many rounds in addition to burning the subpath $\widehat{P}$ and rest of the tree. Thus, placing all the activators on $P$ is another optimal solution.

$◀$ Based on the above lemmas, we present a simple algorithm (Algorithm 1) for the GbAP problem on trees. In the following lemma we prove the approximation guarantee of Algorithm 1.

From Lemma 19 in the case when the tree has two diametral paths with only the centers as common vertices, the first activator must be on a center. Furthermore, by Lemma 20 any optimum solution takes $\mathrm{𝟣}+\lceil 𝖽/\mathrm{𝟤}\rceil$ rounds in this case. Therefore, $c$ followed by any arbitrary sequence of $\lceil 𝖽/\mathrm{𝟤}\rceil$ vertices on the diametral path $P$ as activators is an optimal solution. In the other case, the tree has either a unique diametral path or overlapping diametral paths with length of the common subpath strictly greater than $2$. In that case, Lemma 21 states that there exists an optimum solution that places all the activators on a diametral path. In this case, Algorithm 1 finds a sequence to optimally burn the diametral path $P$ and outputs the same sequence as the burning sequence for the GbAP problem on $T$. Let ALG be the number rounds required by Algorithm 1 and let OPT be the number of rounds required by an optimum solution. It is straight forward to argue that after burning the path $P$ in $\sqrt{𝖽+\mathrm{𝟣}}$ rounds, Algorithm 1 will take at most $\mathrm{𝖮𝖯𝖳}$ many additional rounds. Therefore, $\mathrm{𝖠𝖫𝖦}\le \sqrt{𝖽+\mathrm{𝟣}}+\mathrm{𝖮𝖯𝖳}$. But number of rounds required by any optimal solution is at least the number of rounds required to burn the diametral path. Therefore, $\mathrm{𝖮𝖯𝖳}\ge \sqrt{𝖽+\mathrm{𝟣}}$ and $\frac{\mathrm{𝖠𝖫𝖦}}{\mathrm{𝖮𝖯𝖳}}\le \mathrm{𝟤}$. Hence, the lemma follows. $◀$ Finally, in Lemma 23 we prove the running time of Algorithm 1.

In a tree, a diametral path $P$, the length of $P$, and the centers of $P$ can be found using two invocations of a breadth first search algorithm. Any diametral path $P^{\prime }$ other than $P$ must contain at least all the centers. Therefore, the existence of such a path can be checked using another breadth first search from one of the (at most two) centers. Finally, finding an optimal burning sequence on a path takes $O(n)$ time. Therefore, the running time of Algorithm 1 is $O(n)$. $◀$ Combining Lemma 22 and Lemma 23 yields the following theorem.

Let $k=|𝒮|$. Let $\mathrm{𝖠𝖫𝖦}$ be the number of rounds required by our approach and let $\mathrm{𝖮𝖯𝖳}$ be the number of rounds required by an optimum solution. Clearly, $\mathrm{𝖮𝖯𝖳}\ge k$. It is easy to observe that after burning the activators in the set $𝒮$, our approach will require at most $\mathrm{𝖮𝖯𝖳}$ many additional rounds. Therefore, $\mathrm{𝖠𝖫𝖦}\le 𝗄+\mathrm{𝖮𝖯𝖳}$ and $\frac{\mathrm{𝖠𝖫𝖦}}{\mathrm{𝖮𝖯𝖳}}\le \mathrm{𝟤}$. Hence the theorem. $◀$

Let $k=|𝒮|$. Among the $k!$ different sequences of the activators in $𝒮$, at least one results in the optimal burning sequence. Therefore, probability that we obtain an optimal burning sequence by sampling uniformly at random without replacements is at least $\frac{1}{k!}$. Let $\mathrm{𝖠𝖫𝖦}$ be the number of rounds required by our approach and let $\mathrm{𝖮𝖯𝖳}$ be the number of rounds required by an optimum solution. Clearly, $\mathrm{𝖮𝖯𝖳}\ge k$. In the case our sampling does not obtain an optimal burning sequence, it is easy to observe that after burning the activators, our approach will require at most $\mathrm{𝖮𝖯𝖳}$ many additional rounds. Therefore, In the case our sampling does not obtain an optimal burning sequence, total rounds required is $\le \mathrm{𝟤}\cdot \mathrm{𝖮𝖯𝖳}$. Hence, $\mathrm{𝖠𝖫𝖦}\le \frac{\mathrm{𝟣}}{𝗄!}\cdot \mathrm{𝖮𝖯𝖳}+(\mathrm{𝟣}-\frac{\mathrm{𝟣}}{𝗄!})\cdot (\mathrm{𝟤}\cdot \mathrm{𝖮𝖯𝖳})$ and $\frac{\mathrm{𝖠𝖫𝖦}}{\mathrm{𝖮𝖯𝖳}}\le \mathrm{𝟤}-\frac{\mathrm{𝟣}}{𝗄!}$. Hence the theorem. $◀$

Let $\{o_1,o_2,\mathrm{\dots },o_k\}\in \mathrm{𝗉𝖾𝗋𝗆}(𝒮)$ be an optimal burning sequence. Therefore, such a sequence satisfies the condition ${𝖭}_{𝗄-\mathrm{𝟣}}[{𝗈}_{\mathrm{𝟣}}]\cup {𝖭}_{𝗄-\mathrm{𝟤}}[{𝗈}_{\mathrm{𝟤}}]\cup {𝖭}_{𝗄-\mathrm{𝟥}}[{𝗈}_{\mathrm{𝟥}}]\mathrm{\dots }{𝖭}_{\mathrm{𝟢}}[{𝗈}_{𝗄}]=$ V. Since Algorithm 2 uses an exhaustive search on the set $\mathrm{𝗉𝖾𝗋𝗆}(𝒮)$, it must provide an optimal burning sequence. $◀$

Let $m$ be the number of edges and $n$ be the number of vertices in graph $G$. Computing the ${𝖭}_{𝗋}[𝗏]$ data structure requires a single breadth first search for vertex $𝗏$. Therefore, the first for loop (Line 1 to 5) takes $O((m+n)\cdot k)$ times. Each set ${𝖭}_{𝗋}[𝗏]$ is of size at most $n$. The second for loop (Line 6 to 10 in Algorithm 2) takes $O(n)$ time for every sequence in the set $\mathrm{𝗉𝖾𝗋𝗆}(𝒮)$. Therefore, total time required by the second for loop is $O(n\cdot k^k)$. Thus, total running time of Algorithm 2 is $O((m+n)\cdot k+n\cdot k^k)$. For $m=O(n^2)$, running time is $O(k^k\cdot n^2)$ = $O(2^{k\log k}\cdot n^2)$. Hence, the lemma follows. $◀$ Combining Lemma 28 and Lemma 29 yields the following theorem.