# Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems
## 3 NP-Hardness
The set \(B\) of possible barriers in this proof is the set of all \(k\) diagonals \(a_{i}\), for \(i=1,2,...,k\). Let us assume that barriers can be built at speed one. Defining the fire's speed, \(v\), by \(v(t+0.5)=r\) ensures that the firefighter can build barriers of total length at most \(t+0.5\) before the fire reaches the circle and the whole process terminates. Hence, no diagonal of length \(>\)\(2t\) can be built. On the other hand, if we make radius \(r\) large enough to satisfy  
\[\left(\frac{a_{i}}{2}\right)^{2}\ <\ \left(1-\frac{t^{2}}{(t+0.5)^{2}}\right)r^{2},\]  
Then \(vt<\sqrt{r^{2}-(a_{i}/2)^{2}}\) holds, meaning that the fire has not reached the \(i\)th triangle at time \(t\) (the shaded region in Figure 1). Figure 1: Constructing firefighter instances to show NP-hardness. Therefore, finding the optimal solution for the firefighting problem is equivalent to finding the subset of integers from the subset-sum problem whose sum is as close to \(t\) as possible, without exceeding \(t\). We observe that an additive error less than \(1/k^{2}\) in the lengths of the diagonals would be tolerable in this construction. Thus, vertices can be described by rationals of length polynomial in the bit length of the input. The proof of Theorem 2 would not work if the firefighter were allowed to build barriers freely anywhere in the polygon. But it turns out that the complexity of the problem does not decrease in this more liberal setting. **Theorem 3**. : _The geometric firefighter problem and the budget fence problem are NP-hard for star-shaped polygons even if there is no restriction as to where the barriers can be built, and curved barriers are allowed._  
Proof. : First, we shall show that the geometric firefighter problem for a simple polygon is \(NP\)-hard even if the endpoints of the barriers are not required to be vertices of the polygon. This holds both in the case where the barriers have to be straight-line segments, and in the case where they are allowed to be arbitrary curves. We modify the construction used in the proof for the convex polygons, where \(2k\) of the points lie on the circle \(C\) and \(k\) points lie inside \(C\). The modification is as follows. We will use unnecessarily huge values to simplify the arguments. Firstly, we become more specific concerning the edges connecting consecutive vertices lying on the circle \(C\). This means that the circle \(C\) may have to be much larger than it had to be in the previous proof. We require that each one of these longer edges has length at least \(10s^{2}\), where \(s\) is the sum of all the integers in the instance of the subset-sum problem. (It is still acceptable if some of these diagonals are much larger, but their length has to be bounded by a polynomial in \(s\).) We will assume without loss of generality that \(s>t\), that each integer \(a_{i}\) is smaller than \(t\) and that \(k>10\) (otherwise the problem is easy to solve). Secondly, we adjust the relative speed of the firefighter with respect to the fire. As before, the firefighter has enough time to build barriers of total length precisely \(t\), until the fire reaches anyone of the small diagonals \(e_{i}\) of length \(a_{i}\), which are the candidate barriers and cut the corresponding triangles. But, in addition, we require that the speed of the fire is \(60s^{2}\) times larger than the speed of the firefighter. Thirdly, we replace each small triangle cut by one of the small diagonals \(e_{i}\) by a square \(q_{i}\) of area \(9s^{3}\cdot a_{i}\) (In this way, its side has length smaller than \(3\cdot s^{2}\), which suffices in order to make all these squares fit around the circle \(C\) with no overlaps.). Recall that \(a_{i}\) is the length of \(e_{i}\). The square is placed in such a way that the diagonal \(e_{i}\) cuts off this square from the rest of the polygon, and \(e_{i}\) is in the middle of one of the sides of the square. This finishes the construction.