Hyperbolic intersection graphs and (quasi)-polynomial time

Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.

Les articles les plus proches

1. Très proche Cite cet article Pas pertinent

   Structure and Independence in Hyperbolic Uniform Disk Graphs

   Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak et al. · 2024 · International Symposium on Computational Geometry · cité 6 fois · Pas encore résumé

   Résumé scientifique

   We consider intersection graphs of disks of radius $r$ in the hyperbolic plane. Unlike the Euclidean setting, these graph classes are different for different values of $r$, where very small $r$ corresponds to an almost-Euclidean setting and $r \in \Omega(\log n)$ corresponds to a firmly hyperbolic setting. We observe that larger values of $r$ create simpler graph classes, at least in terms of separators and the computational complexity of the \textsc{Independent Set} problem. First, we show that intersection graphs of disks of radius $r$ in the hyperbolic plane can be separated with $\mathcal{O}((1+1/r)\log n)$ cliques in a balanced manner. Our second structural insight concerns Delaunay com…

2. Proche Cité par cet article Pas pertinent

   Fine-Grained Complexity of Coloring Unit Disks and Balls

   C. Biró, Édouard Bonnet, Dániel Marx et al. · 2017 · International Symposium on Computational Geometry · cité 26 fois · Pas encore résumé

   Résumé scientifique

   On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set , 3-Coloring , Hamiltonian Cycle , Dominating Set can be solved in time $2^{O(\sqrt{n})}$ on an $n$-vertex planar graph, while no $2^{o(n)}$ algorithms exist for general graphs, assuming the Exponential Time Hypothesis (ETH). The square root in the exponent seems to be best possible for planar graphs: assuming the ETH, the running time for these problems cannot be improved to $2^{o(\sqrt{n})}$. In some cases, a similar speedup can be obtained for 2-dimensional geometric problems,…

3. Proche Pas pertinent

   Small Independent Sets versus Small Separator in Geometric Intersection Graphs

   Malory Marin, Rémi Watrigant · 2026 · Embedded Systems and Applications · Pas encore résumé

   Résumé scientifique

   While most classical NP-hard graph problems cannot be solved in time $2^{o(n)}$ on general graphs under the Exponential Time Hypothesis (ETH), many exhibit the square-root phenomenon and admit optimal algorithms running in time $2^{O(\sqrt{n})}$ on certain geometric intersection graphs, such as planar graphs or unit disk graphs. In 2018, de Berg et al. developed a general algorithmic framework for such problems on intersection graphs of similarly sized fat objects in $\mathbb{R}^d$, achieving running times of the form $2^{O(n^{1-1/d})}$, along with matching lower bounds under ETH. In this paper, we identify problems that do not exhibit the square-root phenomenon, yet still admit subexponenti…

4. Proche Pas pertinent

   Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs

   Hsien-Chih Chang, Jie Gao, Hung Le · 2024 · cité 5 fois · Pas encore résumé

   Résumé scientifique

   Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs are one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly-subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two…

5. Proche Cite cet article Pas pertinent

   ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space

   F. Fomin, P. Golovach, Tanmay Inamdar et al. · 2021 · Foundations of Software Technology and Theoretical Computer Science · cité 2 fois · Pas encore résumé

   Résumé scientifique

   De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexponential algorithms on geometric graphs with tight (up to ETH) running times. This framework is based on dynamic programming on graphs of weighted treewidth resulting in algorithms that use super-polynomial space. We introduce the notion of weighted treedepth and use it to refine the framework of de Berg et al. for obtaining polynomial space (with tight running times) on geometric graphs. As a result, we prove that for any fixed dimension $d \ge 2$ on intersection graphs of similarly-sized fat objects many well-known graph problems including Independent Set, $r$-Dominating Set for constant $r$, Cycle Cover, Hamiltonian C…

6. Proche Pas pertinent

   Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

   Timothy M. Chan, Hsien-Chih Chang, Jie Gao et al. · 2025 · IEEE Annual Symposium on Foundations of Computer Science · cité 19 fois · Pas encore résumé

   Résumé scientifique

   We give the first truly subquadratic time algorithm, with ${O^{\ast}}\left( {{n^{2 - 1/18}}} \right)$ running time, for computing the diameter of an n-vertex unit-disk graph, resolving a central open problem in the literature. Our result is obtained as an instance of a general framework, applicable to different graph families and distance problems. Surprisingly, our framework completely bypasses sublinear separators (or r-divisions) which were used in all previous algorithms. Instead, we use low-diameter decompositions in their most elementary form. We also exploit bounded VC-dimension of set systems associated with the input graph, as well as new ideas on geometric data structures. Among th…

7. Proche Cite cet article Pas pertinent

   Separator Theorem and Algorithms for Planar Hyperbolic Graphs

   Sándor Kisfaludi-Bak, Jana Masaríková, E. J. V. Leeuwen et al. · 2023 · International Symposium on Computational Geometry · cité 7 fois · Pas encore résumé

   Résumé scientifique

   The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar $\delta$-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed $\delta \geq 0$, we can find balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. A…

8. Proche Pas pertinent

   Weak Unit Disk and Interval Representation of Planar Graphs

   Muhammad Jawaherul Alam, S. Kobourov, S. Pupyrev et al. · 2014 · arXiv.org · preprint, non relu par les pairs · cité 1 fois · Pas encore résumé

   Résumé scientifique

   We study a variant of intersection representations with unit balls, that is, unit disks in the plane and unit intervals on the line. Given a planar graph and a bipartition of the edges of the graph into near and far sets, the goal is to represent the vertices of the graph by unit balls so that the balls representing two adjacent vertices intersect if and only if the corresponding edge is near. We consider the problem in the plane and prove that it is NP-hard to decide whether such a representation exists for a given edge-partition. On the other hand, every series-parallel graph admits such a representation with unit disks for any near/far labeling of the edges. We also show that the represen…

Les travaux antérieurs sur lesquels il s’appuie

1. Proche* Pas pertinent

   Hyperbolic Random Graphs: Separators and Treewidth

   Thomas Bläsius, T. Friedrich, Anton Krohmer · 2016 · Embedded Systems and Applications · cité 45 fois · Pas encore résumé
2. Proche Pas pertinent

   Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs

   Thomas Bläsius, Philipp Fischbeck, T. Friedrich et al. · 2019 · Theory of Computing Systems · cité 15 fois · Pas encore résumé

   Résumé scientifique

   The computational complexity of the VertexCover problem has been studied extensively. Most notably, it is NP-complete to find an optimal solution and typically NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, whi…

3. Proche Pas pertinent

   Asymptotics of convex sets in Euclidean and hyperbolic spaces

   Igor Rivin · 2009 · Advances in Mathematics · cité 8 fois · Pas encore résumé

   Résumé scientifique

   We study convex sets C of finite (but non-zero) volume in and . We show that the intersection C8 of any such set with the ideal boundary of has Minkowski (and thus Hausdorff) dimension of at most (n-1)/2, and this bound is sharp, at least in some dimensions n. We also show a sharp bound when C8 is a smooth submanifold of . In the hyperbolic case, we show that for any k(n-1)/2 there is a bounded section S of C through any prescribed point p, and we show an upper bound on the radius of the ball centered at p containing such a section. We show similar bounds for sections through the origin of a convex body in , and give asymptotic estimates as 1kn.

4. Proche Pas pertinent

   The complexity of Dominating Set in geometric intersection graphs

   M. de Berg, Sándor Kisfaludi-Bak, G. Woeginger · 2019 · Theoretical Computer Science · cité 17 fois · Pas encore résumé

   Résumé scientifique

   Abstract We study the parameterized complexity of the dominating set problem in geometric intersection graphs. • In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP -complete and contained in FPT (when parameterized by the solutio…

5. Proche Pas pertinent

   Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs

   F. Fomin, D. Lokshtanov, Fahad Panolan et al. · 2017 · Discrete & Computational Geometry · cité 41 fois · Pas encore résumé

   Résumé scientifique

   We give algorithms with running time 2O(klogk)·nO(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{\mathcal {O}({\sqrt{k}\log {k}})} \cdot n^{\mathcal {O}(1)}$$\end{document} for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains a path on exactly/at least k vertices, a cycle on exactly k vertices, a cycle on at least k vertices, a feedback vertex set of size at most k, and a set of k pairwise vertex-disjoint cycles. For the first three problems, no subexpo…

Les articles qui le citent

1. Proche Utilise cet article en profondeur Pas pertinent

   A quasi-polynomial algorithm for well-spaced hyperbolic TSP

   Sándor Kisfaludi-Bak · 2020 · International Symposium on Computational Geometry · cité 10 fois · Pas encore résumé

   Résumé scientifique

   We study the traveling salesman problem in the hyperbolic plane of Gaussian curvature $-1$. Let $\alpha$ denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an $n^{O(\log^2 n)\max(1,1/\alpha)}$ algorithm for Hyperbolic TSP. This is quasi-polynomial time if $\alpha$ is at least some absolute constant, and it grows to $n^{O(\sqrt{n})}$ as $\alpha$ decreases to $\log^2 n/\sqrt{n}$. (For even smaller values of $\alpha$, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of $n^{O(\sqrt{n})}$.)

2. Proche Pas pertinent

   Layered tree-independence number and clique-based separators

   Clément Dallard, Martin Milanič, Andrea Munaro et al. · 2025 · arXiv.org · preprint, non relu par les pairs · cité 6 fois · Pas encore résumé

   Résumé scientifique

   Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublinear weight, we investigate relations between layered tree-independence number, weight of clique-based separators, clique cover degeneracy and independence degeneracy. In particular, we provide a number of results bounding these parameters on geometric intersection graphs. For example, we show that the layered tree-independence number is $\mathcal{O}(g)$ for $g$-map graphs, $\mathcal{O}(\frac{r}{\tanh r})$ for hyperbolic uniform disk graphs with radius $r$, and $\mathcal{O}(1)$ for spherical uniform disk graphs with…

3. Apparenté Utilise cet article en profondeur Pas pertinent

   Curvature and complexity: Better lower bounds for geodesically convex optimization

   Christopher Criscitiello, Nicolas Boumal · 2023 · Annual Conference Computational Learning Theory · cité 14 fois · Pas encore résumé

   Résumé scientifique

   We study the query complexity of geodesically convex (g-convex) optimization on a manifold. To isolate the effect of that manifold's curvature, we primarily focus on hyperbolic spaces. In a variety of settings (smooth or not; strongly g-convex or not; high- or low-dimensional), known upper bounds worsen with curvature. It is natural to ask whether this is warranted, or an artifact. For many such settings, we propose a first set of lower bounds which indeed confirm that (negative) curvature is detrimental to complexity. To do so, we build on recent lower bounds (Hamilton and Moitra, 2021; Criscitiello and Boumal, 2022) for the particular case of smooth, strongly g-convex optimization. Using a…

4. Apparenté Pas pertinent

   Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs

   Thomas Bläsius, Emil Dohse, Deborah Haun et al. · 2026 · International Symposium on Computational Geometry · cité 2 fois · Pas encore résumé

   Résumé scientifique

   Hyperbolic uniform disk graphs (HUDGs) are intersection graphs of disks with some radius $r$ in the hyperbolic plane, where $r$ may be constant or depend on the number of vertices in a family of HUDGs. We show that HUDGs with constant clique number do not admit \emph{product structure}, i.e., that there is no constant $c$ such that every such graph is a subgraph of $H \boxtimes P$ for some graph $H$ of treewidth at most $c$. This justifies that HUDGs are described as not having a grid-like structure in the literature, and is in contrast to unit disk graphs in the Euclidean plane, whose grid-like structure is evident from the fact that they are subgraphs of the strong product of two paths and…

5. Apparenté Pas pertinent

   Hyperbolic Sphericity

   Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt · 2026 · Pas encore résumé

   Résumé scientifique

   The sphericity of a graph is the minimum dimension d such that the graph has an intersection representation of d-dimensional balls of equal radius. While sphericity has been studied in Euclidean space, we initiate the study of hyperbolic sphericity. The hyperbolic sphericity of a graph can be significantly smaller than its Euclidean counterpart, but, contrary to the Euclidean setting, depends strongly on the radius of the balls. We show that, if the radius of the balls can be chosen depending on the graph, the hyperbolic sphericity is upper bounded by the Euclidean sphericity. This extends a previous result for 2-dimensional hyperbolic space, i.e., uniform disk graphs, to arbitrary dimension…