Small Independent Sets versus Small Separator in Geometric Intersection Graphs

Malory Marin, Rémi Watrigant

While most classical NP-hard graph problems cannot be solved in time $2^{o(n)}$ on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomen…