# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 3 NP-Hardness  
A natural approach to show NP-hardness of the geometric firefighter problem is a reduction from the graph firefighter problem, which is known to be NP-hard even for trees of maximum degree three [3]. This approach yields the following theorem. Theorem 3.1: _The geometric firefighter problem is NP-hard for simple polygons, when the barriers can be chosen from a given set of pairwise disjoint diagonals of identical length._  
Proof: Let \(T\) be a rooted tree with maximum degree three which is a part of an instance of the aforementioned firefighter problem on trees. The fire is supposed to break at the root of \(T\). First, we draw \(T\) in the plane in such a way that each drawn edge has the same length \(d\). Next, we replace each vertex with a small square of the same size \(s\) that is polynomially smaller than the edge length. The fire is supposed to break at the top of the root square. The edge from the parent (if any) is supposed to touch the top of the square while the at most three edges to the children are supposed to touch the bottom of the square. Then, we split each drawn edge into two parallel edges forming an \"edge pipe\" of thickness \(\delta\) that is polynomially smaller than the square size \(s\). The thickness \(\delta\) is also so small that the area of such an edge pipe is polynomially smaller than that of a vertex square. In this way, we obtain a simple polygon \(T^{\prime}\). Furthermore, we set the propagation speed of the fire and the speed of drawing a barrier so that in a time unit, the fire can propagate within the radius of \(d+s\) in an open area and a barrier of length \(\delta\) can be drawn. Observe that the fire while reaching vertices may be delayed by the time taken by a traversal of polynomially small fraction of the edge length \(d\) since in general the distance to traverse in a vertex square may slightly exceed \(s\). This however does not affect the main arguments. Finally, we define the set of allowed barriers to be the diagonals of length \(\delta\) \"closing\" the pipes at their ends further away from the root square. Now the crucial observation is that drawing such an allowed diagonal \(e\) saves roughly the area of \(k\) vertex squares, i.e., \(ks^{2}\), in \(T^{\prime}\), where \(k\) is the number of vertices without firefighter saved by placing a firefighter at the root of the subtree of \(T\) corresponding to the subpolygon of \(T^{\prime}\) cut off by \(e\). In this way we can efficiently reduce an instance (of the decision version) of the aforementioned known NP-hard firefighter problem on the tree \(T\) to an instance (of the decision version) of the geometric firefighter problem on the polygon \(T^{\prime}\). If we allow for a large range of the lengths of barriers, then we obtain NP-hardness for the geometric firefighter problem with diagonal barriers even for convex polygons. Theorem 3.2: _The geometric firefighter problem is \(NP\)-hard even for convex polygons, even if the set of allowed barriers is restricted to a set of pairwise disjoint diagonals._  
Proof: We reduce from the subset-sum problem [20]. Let \(\{a_{1},a_{2},...,a_{k}\}\) be the set of positive integers, \(s:=\sum_{i=1}^{k}a_{i}\), and let \(t\) be the desired target sum in the subset-sum problem we want to solve by using the firefighter algorithm for convex polygons. The convex polygon \(P\) is constructed as follows. It has \(3k\) vertices. Of these vertices, \(2k\) lie on a circle \(C\) of radius \(r\) (to be determined later) centred at the fire source. Every third vertex \(v_{i}\) of the convex polygon lies in the interior of this circle \(C\). Vertex \(v_{i}\) can be cut off by a diagonal of length \(a_{i}\); see Figure 1. The resulting triangle is of height \(h\), independent of index \(i\), so that its area equals \(h\cdot a_{i}/2\). Two consecutive vertices of polygon \(P\) situated on \(C\) are at distance greater than \(2t\). ( The precise location of the vertex \(v_{i}\) is not essential, as long as it lies on or inside the circle \(C\).)