# Heuristics for Spreading Alarm throughout a Network
## 2 Burning Number and Previous Algorithms  
In this paper, we only consider finite undirected unweighted simple graphs (aka networks). The problem was originally defined for graphs and therefore the graph theory terminology is retained in this section. Let us have a \(\mathbf{G}=(\mathbf{V},\mathbf{E})\) where \(\mathbf{V}\) is a vertex set and \(\mathbf{E}\) is an edge set. For vertices \(u\), \(v\in\mathbf{V}\), the distance \(\mathrm{dist}_{G}(u;v)\) between them in a graph is the number of edges in a shortest path connecting them. Based on [1], the burning number \(bn(\mathbf{G})\) of a graph \(\mathbf{G}\) is the smallest integer \(k\) for which there are vertices \(x_{1},\ldots,x_{k}\) such that for every vertex \(u\) of \(\mathbf{G}\), there is some \(i\in\{1,\ldots,k\}\) with \(\mathrm{dist}_{G}(u;x_{i})\leq k-i\). Sequence \(x_{1},\ldots,x_{k}\) of vertices from \(\mathbf{G}\) from the above definition is called a shortest burning sequence (there may be several such sequences). A burning sequence and burning number are based on a metaphor of a fire spreading among the vertices of a graph. At each discrete time step \(t_{i}\) starting at \(1\) and terminating at \(k\), a fire starts at a vertex \(x_{i}\), if it is not already burning. Then the fire starts at all neighboring vertices of the vertices which are already burning (except of the neighbors of the just ignited vertex \(x_{i}\)). The condition \(\forall u\in\mathbf{V}(\mathbf{G})\): \(\exists i\in\{1,\ldots,k\}\): \(\mathrm{dist}_{G}\left(u;x_{i}\right)\leq k-i\) guarantees, that after \(k\) steps all the vertices of \(\mathbf{G}\) are burning. An additional condition \(\forall i,j\in\mathbf{V}(\mathbf{G})\in\{1,\ldots,k\}\): \(\mathrm{dist}_{G}(x_{i};x_{j})\geq j-i\) might be included, which means, that in the sequence \(x_{1},\ldots,x_{k}\), one does not try to start a fire at a vertex, which is already burning. However, if the burning sequence is the shortest, this condition is superfluous. In Figure 1 are presented single time steps (from left to right, top to bottom) of the optimal process of burning an artificially designed graph. The optimum burning number of this graph is seven, since it was burned in seven steps and in no step a greater number of nodes could have been burned. In each time step, one node is painted with a new color, which means, that this node is \"burned from the outside\" as a part of the burning sequence. All the neighbors of the already burned nodes, which are not yet burned, are also burned (in Figure 1 they are painted with the same color as their painted neighbors). However, the colors only serve to provide an additional piece of information, one non-white color for all burned nodes would be sufficient. In addition, when two or more different colored nodes are neighbors of a white (i.e., not yet burned) node, the decision regarding which of the neighboring colors to choose from would have to be arbitrary. Nevertheless, in Figure 1 such a situation does not occur. Figure 1 presents more clearly the problem of the selection of the vertices in the shortest burning sequence, i.e., which vertices should be colored (aka burned) from outside and in which permutation determining their time schedule. Until now, the only known approximation algorithm generating a burning sequence for the general graphs was an algorithm by [PERSON] and [PERSON] [3]. This algorithm has an approximation ratio of \(3\), which means, that the optimal, i.e., the shortest possible burning sequence is guaranteed not to be shorter than one third of the burning sequence length provided by the approximation algorithm. The [PERSON] algorithm [3] starts with a guess, that the burning number equals \(3g-3\). The \"shortened\" burning sequence is initially empty. Then, starting from an arbitrary node, a randomly selected node is added to the \"shortened\" burning sequence, if all the nodes already in the burning sequence have a graph distance from the selected node at least \(2g-1\).