Hardness of Vertex Guarding Polygons With Holes

The VERTEX GUARD (VG) problem is defined as follows: Given a polygon P (with holes allowed) with n vertices, find a smallest subset S of the set of vertices of P such that every point in the polygon P can be seen from at least one vertex in S. The vertices in S are called the vertex guards.

In this talk, we will prove that VERTEX GUARD is NP-hard by showing a reduction from SET COVER which was put forward by Eidenbenz, Stamm and Widmayer in 1998. If time permits, we will also present our own modifications to this reduction that proves that VERTEX GUARD is NP-hard even when considering the special class of polygons with holes that are weakly visible from an edge. In fact, we can show that there cannot exist a polynomial time algorithm for the vertex guard problem with an approximation ratio better than $((1−\epsilon)/12)\ln n$ for any $\epsilon>0$, unless NP $\subseteq$ TIME($n^{\mathcal{O}(\log\log n)}$).