Speaker: |
Pritam Bhattacharya |

Organiser: |
Deepesh Data |

Date: |
Friday, 26 Sep 2014, 14:00 to 15:30 |

Venue: |
D-405 (D-Block Seminar Room) |

(Scan to add to calendar)

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)}$).