# Lecture by Sándor Kisfaludi-Bak (Max Planck Institut Saarbrücken): Separators and exact algorithms for geometric intersection graphs

Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH).

### Time & Location

Feb 03, 2020 | 02:15 PM

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

Room 005 (Ground Floor)