Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree

Abstract

We give an approximation scheme for the TSP in $d$-dimensional hyperbolic space that has optimal dependence on $\epsilon$ under Gap-ETH. For any fixed dimension $d\ge 2$ and for any $\epsilon >0$ our randomized algorithm gives a $(1+\epsilon )$-approximation in time $2^{O(1/{\epsilon }^{d-1})}{n}^{1+o(1)}$. We also provide an algorithm for the hyperbolic Steiner tree problem with the same running time. Our algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG'25). Moreover, we have a new non-uniform portal placement, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces.

To appear in SoCG 2026