Hyperbolic intersection graphs and (quasi)-polynomial time
Hyperbolic intersection graphs and (quasi)-polynomial time
复制标题
双曲交集图和（拟）多项式时间
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sándor Kisfaludi
中科院分区：
文献类型：
--
作者：
Sándor Kisfaludi
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 $dgeq 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.
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 $dgeq 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.