We study unit ball graphs (and, more generally, so-called noisy uniform ball graphs) in d-dimensional hyperbolic space, which we denote by H^d. Using a new separator theorem, we show that unit ball graphs in H^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 2^{O(n^{1-1/(d-1)})} time for any fixed d\geq 3, while the same problems need 2^{O(n^{1-1/d})} time in R^d. We also show that these algorithms in H^d are optimal up to constant factors in the exponent under ETH. This drop in dimension has the largest impact in H^2, where we introduce a new technique to bound the treewidth of noisy uniform disk graphs. The bounds yield quasi-polynomial (n^{O(\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 H^2 have constant ply , then all studied problems can be solved in polynomial time. This contrasts with the fact that these problems require 2^{\Omega(n)} time under ETH in constant-ply Euclidean unit disk graphs. Finally, we complement our quasi-polynomial algorithm for Independent Set in noisy uniform disk graphs with a matching n^{\Omega(\log n)} lower bound under ETH. As far as we know, this is the first natural problem with a quasi-polynomial lower bound that is shown to be tight .
We study unit ball graphs (and, more generally, so-called noisy uniform ball graphs) in d-dimensional hyperbolic space, which we denote by H^d. Using a new separator theorem, we show that unit ball graphs in H^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 2^{O(n^{1-1/(d-1)})} time for any fixed d\geq 3, while the same problems need 2^{O(n^{1-1/d})} time in R^d. We also show that these algorithms in H^d are optimal up to constant factors in the exponent under ETH. This drop in dimension has the largest impact in H^2, where we introduce a new technique to bound the treewidth of noisy uniform disk graphs. The bounds yield quasi-polynomial (n^{O(\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 H^2 have constant maximum degree , then all studied problems can be solved in polynomial time. This contrasts with the fact that these problems require 2^{\Omega(n)} 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^{\Omega(\log n)} lower bound under ETH. This shows that the hyperbolic plane is a potential source of NP-intermediate problems .
R
ply
maximum degree
R
constant-ply
constant maximum degree
R
As far as we know, this is the first natural problem with a quasi-polynomial lower bound that is shown to be tight
This shows that the hyperbolic plane is a potential source of NP-intermediate problems