====== Michael Dobbins (Binghamton) ======

====== Candidate Sets for the Art Gallery Problem ======

===== Abstract for the Combinatorics Seminar 2019 May 7 =====

The decision version of the Art Gallery Problem asks, for a given polygon P and integer k, whether P can be guarded by k points. In other words, can P be covered by the visibility regions of at most k points in P? A set C (of any size) is called a candidate set for (P,k) when, if G can be guarded by k points, it can be guarded by k points in C. I will show that it is not possible for an algorithm to produce a subexponential-sized candidate set in subexponential time unless the Exponential Time Hypothesis fails.

This is joint work with Tillmann Miltzow.


----