Hyperbolic intersection graphs and (quasi)-polynomial time

Résumés déjà disponibles dans d'autres langues : en

Auteurs : Sándor Kisfaludi-Bak

25 pages, 3 figures

Résumé : 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 ply, then all studied problems can be solved in polynomial time. This contrasts with the fact that these problems require $2^{Ω(\sqrt{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^{Ω(\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.

Soumis à arXiv le 10 Déc. 2018

Posez des questions sur cet article à notre assistant IA

Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.

La licence de l'article ne nous permet pas de nous appuyer sur son contenu et l'assistant IA ne peut se servir que des métadonnées de l'article plutôt que de l'article complet.

Instructions pour utiliser l'assistant IA ?

Résultats du processus de synthèse de l'article arXiv : 1812.03960v1

La licence de cet article ne nous permet pas de nous appuyer sur son contenu et le processus de synthèse est ici effectué avec les métadonnées de l'article plutôt qu'avec l'article en tant que tel.

Le résumé n'est pas encore prêt
Créé le 09 Jul. 2026
Disponible dans d'autres langues : en

Évaluez la qualité du contenu généré par l'IA en votant

Note : 0

Pourquoi avons-nous besoin de votes ?

Les votes sont utilisés pour déterminer si nous devons réexécuter nos outils de synthèse. Si le compte atteint -10, nos outils peuvent être redémarrés.

Certains éléments de l'article ne sont pas encore résumés, vous pouvez relancer le processus de synthèse en cliquant sur le bouton Exécuter ci-dessous.

La licence de cet article spécifique ne nous permet pas de nous appuyer sur son contenu et les outils de synthèse seront exécutés en utilisant les métadonnées de l'article plutôt que l'article complet. Cependant, l'outil produira quand même un bon résultat, et vous pouvez également essayer nos outils sur des papiers avec des licences plus ouvertes.

Articles similaires résumés avec nos outils d'IA

Naviguez à travers encore plus d'articles similaires en utilisant une

représentation arborescente

Recherchez des articles similaires (en version bêta)

En cliquant sur le bouton ci-dessus, notre algorithme analysera tous les articles de notre base de données pour trouver le plus proche en fonction du contenu des articles complets et pas seulement des métadonnées. Veuillez noter que cela ne fonctionne que pour les articles pour lesquels nous avons généré des résumés et que vous pouvez le réexécuter de temps en temps pour obtenir un résultat plus précis pendant que notre base de données s'agrandit.

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.