Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: 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 $\mathbb{H}^d$.
Using a new separator theorem, we show that unit ball graphs in $\mathbb{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 $\mathbb{R}^d$. We also show that these algorithms in $\mathbb{H}^d$
are optimal up to constant factors in the exponent under ETH.
  This drop in dimension has the largest impact in $\mathbb{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 $\mathbb{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(\sqrt{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.

37
The categories of this paper are: supr-con
17
The categories of this paper are: q-fin
31
The categories of this paper are: ao-sci
0
The categories of this paper are: hep-ph
28
The categories of this paper are: alg-geom
24
The categories of this paper are: dg-ga
22
The categories of this paper are: chao-dyn
18
The categories of this paper are: econ
29
The categories of this paper are: funct-an
13
The categories of this paper are: quant-ph
9
The categories of this paper are: nlin
27
The categories of this paper are: comp-gas
14
The categories of this paper are: math-ph
4
The categories of this paper are: cond-mat
33
The categories of this paper are: plasm-ph
11
The categories of this paper are: hep-lat