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

This paper presents Gap-ETH-tight randomized approximation schemes for the Traveling Salesperson Problem and Steiner Tree in $d$-dimensional hyperbolic space with running time $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$, achieved through a novel hybrid hyperbolic quadtree decomposition, non-uniform portal placement, and weighted crossing analysis.

The Gist

Imagine you are a delivery driver trying to visit a list of customers and return to your depot, but there's a catch: you aren't driving on a flat, boring map like the one on your phone. You are driving in Hyperbolic Space.

What is Hyperb Space? (The "Pizza Dough" Analogy)

Think of a flat sheet of paper (Euclidean space). If you draw a circle, the area inside grows normally. Now, imagine that sheet is made of stretchy pizza dough. If you pull the edges, the dough stretches out. In Hyperbolic Space, the "dough" stretches exponentially as you move away from the center.

• The Consequence: The space gets huge very quickly. A small neighborhood near you looks normal, but just a little further out, there is so much room that the number of places you can go doubles, then quadruples, then explodes.
• The Problem: The "Traveling Salesman Problem" (TSP) asks for the shortest route to visit a bunch of points. In normal space, we have great tricks to solve this quickly. But in this stretching, exploding space, the old tricks fail because the "map" is too big and weird.

The Paper's Big Achievement

The authors of this paper have invented a new, super-smart way to find a nearly perfect route (and a similar solution for connecting points with a network, called the "Steiner Tree") in this weird, stretching space.

They didn't just find a solution; they found the fastest possible solution that we can theoretically hope for, given current computer science limits.

How Did They Do It? (The Three Magic Tricks)

To solve this, they had to invent three new tools. Here is how they work, using simple analogies:

1. The "Hybrid Tree" Map (The Ladder and the Lattice)

In normal space, we solve these problems by dividing the map into a grid (like a chessboard) and then breaking those squares into smaller squares (a "Quadtree").

• The Problem: In Hyperbolic space, if you try to make a grid, the squares get weird. Near the center, they look like normal squares. But as you go out, the "squares" get so big and distorted that a single square might need to split into thousands of smaller pieces. This breaks the math.
• The Solution: They built a Hybrid Tree.
  • Near the center (Level < 0): It acts like a normal, boring grid (Euclidean).
  • Farther out (Level > 0): It switches to a "Binary Tiling" structure. Imagine a tree where every branch splits into exactly two new branches, forever.
  • Why it works: This structure respects the natural "stretching" of the space. It's like having a ladder that turns into a tree as you climb higher, perfectly matching the shape of the universe you are driving in.

2. The "Smart Portals" (The Non-Uniform Bus Stops)

To solve the problem efficiently, the algorithm forces the route to only cross the boundaries between these map sections at specific "Portals" (like bus stops).

• The Old Way: In normal space, you put bus stops evenly spaced everywhere.
• The New Way: In Hyperbolic space, the "sides" of the map sections are huge. If you put bus stops evenly, you'd need millions of them, and the computer would crash.
• The Innovation: They placed Smart Portals.
  • Near the "bottom" of a section (where the space is small), they put many portals close together.
  • Near the "top" (where the space is massive), they put very few portals, spaced far apart.
  • The Analogy: Imagine a highway. Near the city center (small area), you have a bus stop every block. In the middle of the desert (huge area), you only have a bus stop every 50 miles. This saves massive amounts of time while still letting the driver get where they need to go.

3. The "Weighted Crossing" (The Heavy vs. Light Crossings)

The algorithm needs to prove that the driver won't get lost by crossing boundaries too many times.

• The Problem: In normal space, crossing a line is easy to count. In Hyperbolic space, a single line can be crossed thousands of times by a route that looks short, because the space is so stretched.
• The Innovation: They introduced a Weighted System.
  • Imagine every time the route crosses a boundary, it gets a "ticket."
  • If the crossing happens in a "heavy" (small, dense) area, the ticket costs a lot.
  • If the crossing happens in a "light" (huge, sparse) area, the ticket costs almost nothing.
  • By counting the cost of the crossings rather than just the number, they proved the route stays efficient.

Why Does This Matter?

1. It's the Best Possible: They proved that you can't do this much faster than they did (unless a major computer science theory called "Gap-ETH" is wrong). They hit the speed limit.
2. Real World Use: Hyperbolic space isn't just math fantasy. It's used to model:
   • The Internet: How data flows through complex networks.
   • Social Networks: How friends of friends connect.
   • AI and Machine Learning: Organizing massive amounts of data efficiently.
3. Future Tools: This paper builds the "hammer and screwdriver" for future engineers to build better algorithms for curved, complex worlds.

Summary

The authors took a problem that seemed impossible to solve quickly in a "stretchy" universe. They built a custom map (Hybrid Tree), placed bus stops intelligently (Non-uniform Portals), and created a new way to count mistakes (Weighted Analysis). The result is a super-fast, near-perfect navigation system for the most complex geometric spaces we know.

Technical Summary

Here is a detailed technical summary of the paper "Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree."

1. Problem Statement

The paper addresses the Metric Traveling Salesman Problem (TSP) and the Steiner Tree problem in $d$-dimensional hyperbolic space ($H^d$).

• Context: While Polynomial Time Approximation Schemes (PTAS) exist for these problems in Euclidean space ($R^d$) and doubling metric spaces with running times that are tight under the Gap Exponential Time Hypothesis (Gap-ETH), extending these results to non-doubling spaces like hyperbolic space has been an open challenge.
• Specific Challenge: Hyperbolic space exhibits exponential volume growth, meaning the number of points at a certain distance grows exponentially. This "exponential expansion" breaks the assumptions of standard hierarchical decompositions (like quadtrees) used in Euclidean PTAS, where the number of children per cell is constant.
• Goal: To design a $(1+\epsilon)$-approximation algorithm for TSP and Steiner Tree in $H^d$ that achieves Gap-ETH-tight running times, matching the efficiency of the best Euclidean algorithms (up to polylogarithmic factors).

2. Methodology and Key Innovations

The authors adapt the classic Arora-style dynamic programming framework, which relies on a hierarchical decomposition of the space, random shifting, and "patching" tours to cross cell boundaries only at specific "portals." However, they introduce three critical novel components to handle the geometry of hyperbolic space:

A. Hybrid Hyperbolic Quadtree (Hybrid Tree)

Standard hyperbolic quadtrees (e.g., Kisfaludi-Bak & Van Wordragen, 2025) decompose space into cells where the number of children is unbounded due to exponential expansion. This would make the dynamic programming (DP) state space too large.

• Solution: The authors propose a Hybrid Hyperbolic Quadtree.
  • Negative Levels ($\ell < 0$): Resemble a slightly distorted Euclidean quadtree (based on the binary tiling of $H^d$).
  • Non-Negative Levels ($\ell \ge 0$): These cells are "open" at the bottom. A cell at level $\ell$ is the union of a binary tiling cell and its $2^{d-1}$children from level$\ell-1$.
  • Key Property: This structure ensures that every cell has a bounded number of children (at most $2^d$), which is crucial for keeping the DP exponent manageable, while still capturing the large-scale tree-like structure of hyperbolic space.

B. Non-Uniform Portal Placement

In Euclidean space, portals are placed uniformly on cell boundaries. In hyperbolic space, the surface area of a cell's side facet grows exponentially with its diameter. A uniform grid would require exponentially many portals, leading to a double-exponential running time.

• Solution: The authors introduce a non-uniform portal placement strategy.
  • Weighted Analysis: They analyze the "crossings" of the optimal tour with cell boundaries. They observe that intersections with large facets (near the "bottom" of the space) are exponentially rare.
  • Strategy: They place portals densely near the "top" of the side facets (where the tour is likely to cross) and sparsely (or not at all) near the bottom.
  • Result: This reduces the total number of portals on a side facet to $O(r^{d-1})$, avoiding the exponential blow-up.

C. Weighted Crossing Analysis & Structure Theorem

Proving that a near-optimal tour exists that crosses boundaries only at portals is the core of Arora-style proofs.

• Challenge: In hyperbolic space, a tour can cross a vertical hyperplane an unbounded number of times, unlike in Euclidean space where crossings are proportional to the tour length.
• Solution: The authors use a weighted crossing analysis. They assign a weight of $1/z(p)$to each intersection point$p$(where$z$ is the vertical coordinate in the Poincaré half-space model).
  • They prove that the sum of these weights is bounded by the tour length.
  • This allows them to bound the expected "patching cost" (the cost of modifying the tour to go through portals) even when the number of crossings is unbounded.

D. Hyperbolic Banyan for Steiner Tree

For the Steiner Tree problem, leaf cells may contain Steiner points. In Euclidean space, a dense grid of potential Steiner points (a "banyan") suffices. In hyperbolic space, a dense grid is too large.

• Solution: They construct a Hyperbolic Banyan by placing potential Steiner points along the edges of a triangulation of the input points and portals. This ensures a $(1+\epsilon)$-approximation without requiring an exponential number of points.

3. Main Results

Theorem 1 (Randomized Algorithm)

For any fixed dimension $d \ge 2$ and $\epsilon > 0$, there exists a randomized $(1+\epsilon)$-approximation algorithm for TSP and Steiner Tree in $H^d$ with running time:
$$2^{O(1/\epsilon^{d-1})} \cdot n^{1+o(1)} \cdot (\log n)^{2d(d-1)}$$

• Significance: The dependence on $\epsilon$ is $2^{O(1/\epsilon^{d-1})}$, which matches the best known Euclidean algorithms and is proven to be Gap-ETH-tight (Corollary 3).

Corollary 2 (Deterministic Algorithm)

If the input point set $P$ has a constant diameter, the algorithm can be derandomized to run in:
$$2^{O(\text{diam}(P) + 1/\epsilon^{d-1})} \cdot n^{d+1} \cdot (\log n)^{2d(d-1)}$$

• Note: For general point sets with super-constant diameter, a deterministic algorithm with the same $\epsilon$-dependence remains an open problem.

Corollary 3 (Lower Bound)

Under Gap-ETH, no algorithm can solve TSP in $H^d$ in time $2^{\gamma/\epsilon^{d-1}} \cdot \text{poly}(n)$for any$\gamma > 0$. This confirms the optimality of the authors' running time regarding$\epsilon$.

4. Significance and Impact

1. Bridging Euclidean and Hyperbolic Optimization: This work demonstrates that the powerful Arora-style framework can be successfully adapted to non-doubling, negatively curved spaces, resolving a question posed by García-Castellanos et al. regarding hyperbolic Steiner Tree.
2. Optimality: The algorithms achieve the theoretically best possible dependence on $\epsilon$ (Gap-ETH-tight), proving that hyperbolic TSP is not inherently harder than Euclidean TSP in terms of approximation complexity, provided the dimension is fixed.
3. New Geometric Tools: The introduction of the Hybrid Quadtree, Non-uniform Portal Placement, and Weighted Crossing Analysis provides a new toolkit for geometric optimization in curved spaces. These techniques are likely applicable to other problems in Riemannian manifolds.
4. Practical Relevance: Given the increasing use of hyperbolic geometry in machine learning (e.g., embeddings for hierarchical data) and network science, establishing efficient geometric optimization tools in this domain is a significant step forward for both theory and practice.

5. Limitations and Open Questions

• Derandomization: A fully deterministic algorithm with the optimal $\epsilon$-dependence for point sets of super-constant diameter is not yet achieved.
• Light Spanners: The authors note that their running time is slightly slower than the fastest Euclidean algorithms because they lack "light" Steiner spanners for hyperbolic space. Finding such spanners could further improve the $n$-dependence.
• Linear Dependence on $n$: It remains open whether a linear dependence on $n$ (i.e., $O(n)$ instead of $n^{1+o(1)}$) is achievable for hyperbolic TSP.