New for: D1
and mention some related problems that I am still working on.
Several classical NP-complete graph problems - for example Independent
Set and Dominating Set - have algorithms with running time 2^{O(n)}.
Under the Exponential Time Hypothesis (ETH) significant speedups are not
possible. However, if we introduce geometric constraints on our graphs,
then these running times can be beaten: often 2^O(sqrt(n)) time is
sufficient. In this talk, I will showcase separation techniques that
yield these improved running times when we consider various geometric
intersection graphs, i.e., graphs where the vertices correspond to a set
of objects in Euclidean space, and edges are added between pairs of
intersecting objects. Our lower bound framework shows that the obtained
running times have the best (asymptotic) exponents under ETH. If time
allows, I will end by pushing these algorithmic and lower bound
techniques to their limits, either by allowing more general objects or
by changing the underlying space.