Hyperbolic intersection graphs and (quasi)-polynomial time

We study unit ball graphs (and, more generally, so-called noisy uniform ball graphs) in d-dimensional hyperbolic space, which we denote by ℍd. Using a new separator theorem, we show that unit ball graphs in ℍd enjoy similar properties as their Euclidean counterparts, but in one dimension lower: many standard graph problems, such as Independent Set, Dominating Set, Steiner Tree, and Hamiltonian Cycle can be solved in 2O(n1–1/(d–1)) time for any fixed d ≫ 3, while the same problems need 2O(n1–1/d) time in ℝd. We also show that these algorithms in ℍd are optimal up to constant factors in the exponent under ETH. This drop in dimension has the largest impact in ℍ2, where we introduce a new technique to bound the treewidth of noisy uniform disk graphs. The bounds yield quasi-polynomial (nO(log n)) algorithms for all of the studied problems, while in the case of Hamiltonian Cycle and 3-Coloring we even get polynomial time algorithms. Furthermore, if the underlying noisy disks in ℍ2 have constant maximum degree, then all studied problems can be solved in polynomial time. This contrasts with the fact that these problems require time under ETH in constant maximum degree Euclidean unit disk graphs. Finally, we complement our quasi-polynomial algorithm for Independent Set in noisy uniform disk graphs with a matching nΩ(log n) lower bound under ETH. This shows that the hyperbolic plane is a potential source of NP-intermediate problems.