WorksComputer Science
Inapproximability of Euclidean Steiner Tree
Abstract
We consider the Euclidean Steiner Tree problem of connecting given points in by a shortest network allowing the addition of Steiner points anywhere in the space. Arora [FOCS'96/'97, J. ACM'98] gave a polynomial-time approximation scheme (PTAS) for Euclidean Steiner Tree and TSP in every fixed dimension, and Trevisan [STOC'97, SICOMP'00] proved that Euclidean TSP is APX-hard in dimensions. They left open whether Euclidean Steiner Tree admits a PTAS in high dimension. Our first contribution settles this thirty-year-old question by proving APX-hardness in dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in dimensions. This dimension bound is tight up to a factor of , since Arora's scheme is a PTAS in up to dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time and proved matching Gap-ETH lower bounds for Euclidean TSP and Rectilinear Steiner Tree, but left a corresponding lower bound for Euclidean Steiner Tree as an open question. Our second contribution answers this question with a nearly tight lower bound on the dependence on accuracy for Euclidean Steiner Tree. However, given the recent claimed refutations of ETH and hence Gap-ETH by OpenAI and Anthropic, we use the weaker assumption that 3SAT has no truly subexponential-time algorithm, that is, no -time algorithm on formulas of size for any constant (a hypothesis one might call weak ETH). Under this assumption, we prove that no -approximation algorithm runs in time for any such .
Introduction
We consider the Euclidean Steiner Tree problem of connecting given points in by a shortest network. These points are called terminals and additional Steiner points may be placed anywhere in the space. The length of a network is the sum of its Euclidean edge lengths.
The problem has its roots in the Fermat–Torricelli problem and nineteenth-century work on shortest networks. It was later studied by Jarník and Kössler [28] and by Gilbert and Pollak [27]; see Brazil, Graham, Thomas, and Zachariasen [9] for a historical account. Garey, Graham, and Johnson [26, 25] proved NP-hardness even in the plane.
In the 1990s, Arora [2] obtained a polynomial-time approximation scheme (PTAS) for the plane and a quasipolynomial-time approximation scheme for higher fixed dimensions. Independently, Mitchell [33] developed a planar PTAS based on guillotine subdivisions. Arora later improved his scheme [3, 4], obtaining a randomised PTAS that runs in time for every fixed dimension . His method recursively partitions the space and restricts where and how often a near-optimal network crosses region boundaries. Dynamic programming then combines solutions for the smaller regions.
Rao and Smith [36] reduced the running time to for fixed dimension and accuracy. For Euclidean Steiner Tree, their bound is . Their method combines recursive dissections with banyans, sparse geometric graphs containing near-optimal Steiner trees for every subset of the terminals. Kisfaludi-Bak, Nederlof, and Węgrzycki [32] later removed the logarithmic factor in the exponent using sparsity-sensitive patching, obtaining an approximation scheme running in time for Euclidean TSP, Euclidean Steiner Tree, and Rectilinear Steiner Tree. They also proved matching Gap-ETH lower bounds for Euclidean TSP and Rectilinear Steiner Tree, leaving the corresponding bound for Euclidean Steiner Tree as an open question.
The exponential dependence of these schemes on the dimension led Arora [2] to ask whether his scheme in could run in time , with an exponent linear in . For Euclidean TSP, Trevisan [39, 40] proved APX-hardness in dimensions, so such a scheme is unlikely: in these dimensions, it would run in time for fixed , and would thus solve NP-hard problems in quasipolynomial time [4]. Trevisan also proved APX-hardness for Rectilinear Steiner Tree in dimensions.
Ruling out a PTAS for Euclidean Steiner Tree in high dimension has since been described as “a notoriously long standing open problem” [24]. The main difficulty is that Steiner points can be placed anywhere. Fleischmann, Gavva, and Karthik [22, 23] studied the distinction between the discrete problem, where Steiner points must come from a given set of candidates, and the continuous problem, where they may lie anywhere. They established APX-hardness for the discrete problem in every metric and its continuous counterpart in , and reduced the continuous to the discrete problem in metrics. For the continuous Euclidean problem, Fleischmann, Gamboa Quintero, Karthik, Matějka, and Petri [24] connected approximation hardness with the structure of optimal Steiner trees for regular simplices and simplicial complexes. They formulated structural conjectures that would imply APX-hardness and revisited a conjecture of Smith [38] about the optimal topology for the regular simplex. We instead prove APX-hardness through a gap-preserving reduction from three-dimensional matching.
Remark. This paper was almost finished when the OpenAI and Anthropic preprints [34, 13] claiming to refute ETH appeared. The proofs of Theorems 2 and 3 originally relied on ETH and Gap-ETH, respectively, but weaker assumptions on the running time of 3SAT, and even NP SUBEXP, now suffice for some of the bounds. We believe these reductions remain valuable, as discussed throughout the paper and in § 8.
Our contributions. We prove that Euclidean Steiner Tree admits no PTAS in dimensions unless P = NP, and give conditional lower bounds showing that the exponent is nearly optimal in every fixed dimension. First, we establish APX-hardness in logarithmic dimension.
Theorem 1. Euclidean Steiner Tree is APX-hard in dimensions.
This rules out a PTAS in arbitrary dimension unless P = NP, answering Arora’s question. The dimension is close to optimal for APX-hardness: for fixed accuracy, Arora’s scheme [4] runs in subexponential time in dimensions, so APX-hardness there would imply NP SUBEXP. Padding the construction also rules out a PTAS in much lower dimension under NP SUBEXP.
Theorem 2. Unless NP SUBEXP, Euclidean Steiner Tree admits no PTAS in dimensions.
Theorem 2 is tight up to a factor of in the dimension. Arora’s scheme [4] runs in time , which remains polynomial for every fixed whenever . In this range, , so for sufficiently large the exponent of is at most , giving . Thus Euclidean Steiner Tree admits a PTAS in up to dimensions, but, unless NP SUBEXP, not in dimensions. Under the same assumption, a doubly exponential dependence of the running time on the dimension is therefore unavoidable; § 8 discusses the remaining gap.
Second, we establish lower bounds on the dependence on accuracy in every fixed dimension. We obtain nearly tight bounds under the following weaker form of ETH, which has not been refuted by the announced SAT algorithms.
Hypothesis 1 (Weak ETH). has no truly subexponential-time algorithm, that is, no algorithm running in time on formulas of size for any constant .
Theorem 3. Under weak ETH, for every fixed and every constant , Euclidean Steiner Tree in admits no -approximation algorithm running in time
Under Gap-ETH, the same reduction would have ruled out running time for every fixed . This would have matched the known scheme’s dependence on accuracy in the exponent, answering the question of Kisfaludi-Bak, Nederlof, and Węgrzycki [32].
Under weak ETH, the power of in the exponent can be made arbitrarily close to , the power achieved by the known scheme. This leaves room for subpolynomial savings in the exponent, but excludes any fixed reduction in this power. For every fixed , it rules out running times such as , which APX-hardness in dimensions does not exclude, as Arora [4] observed. The restriction in this example is necessary: in the plane, the known scheme already runs in time .
Even under NP SUBEXP, the same reduction rules out running time for some constant independent of . Thus the power of in the exponent cannot be bounded independently of the dimension.
Even if Gap-ETH fails, improving the PTAS appears highly nontrivial: such an improvement would yield a faster gap-3SAT algorithm, while the claimed ETH refutations rely on sophisticated algebraic methods.
As a by-product, our reduction proves APX-hardness for a completion version of Euclidean Steiner Tree, where parts of the network are already built and must be connected by additional segments of minimum total length. The result holds already in (Theorem 20), answering a question of Bartlmae, Jünger, and Langetepe [7] negatively for .
Techniques. All our results follow the same reduction strategy. We first reduce three-dimensional matching to Euclidean Cable Steiner Tree, a generalization of Euclidean Steiner Tree in which each terminal is a connected union of line segments rather than a point. We call these unions cables; they are pairwise disjoint, and only the length added outside them is counted (Figure 1). A separation condition rules out unintended connections between the cables, ensuring that the minimum cost of connecting them encodes the size of a maximum matching.
Figure 1. Cables (black) and a shortest network connecting them (red). Connections may attach in cable interiors, and only the red segments are paid for.
We then replace each cable by densely spaced terminals and show that a short tree spanning them can be made to follow the cables at small extra cost. Up to this error, the optimum equals the total cable length plus the minimum connection cost. Each result therefore reduces to a layout problem: drawing separated cables of small total length so that the approximation gap survives.
In linear dimension, we construct such a layout by giving each gadget and each cable its own coordinate direction. We reduce the dimension to by applying the Johnson–Lindenstrauss lemma [29] to the terminals and Kirszbraun’s extension theorem [31] to the Steiner points. This preserves the Steiner optimum up to small distortion, following the argument of Karthik C. S. [41 Section 4.2]. Padding the resulting instance gives Theorem 2 under NP SUBEXP.
For fixed , the cables must be longer, and we use the cube-wiring theorem of de Berg, Bodlaender, Kisfaludi-Bak, Marx, and van der Zanden [19] to route them with total length small enough to match the Gap-ETH bound. In the plane, we use the crossovers of Garey, Graham, and Johnson [25] to split crossing cables into pieces that are again separated. An elegant aspect of our approach is that the same reduction framework handles high dimensions, fixed , and the plane.
Further related work. In general metrics, Steiner Tree is APX-hard [8], NP-hard to approximate within 96/95 [12], and approximable within [10]. In the plane, Euclidean Steiner Tree is NP-hard even when the terminals lie on two parallel lines [37]. Approximation schemes are also known for TSP [6] and Steiner Forest [11] in metrics of bounded doubling dimension. For Euclidean TSP, de Berg, Bodlaender, Kisfaludi-Bak, and Kolay [16, 17] gave an ETH-tight exact algorithm in every fixed dimension. Our routing uses the cube-wiring theorem from the related framework of de Berg, Bodlaender, Kisfaludi-Bak, Marx, and van der Zanden [19] for ETH-tight bounds in geometric intersection graphs. Related questions arise in clustering, where centres may lie anywhere in the space. Euclidean -means is APX-hard [5], and Cohen-Addad and Karthik [14], followed by Cohen-Addad, Karthik, and Lee [15], established stronger inapproximability bounds for -means and -median in metrics.
Preliminaries
In a three-dimensional matching instance , the element set is partitioned into three parts of size , and each triple in contains one element from each part. A matching consists of pairwise disjoint triples and is perfect if it has size . We consider -, where each element occurs in at most three triples, implying . Write for the instance size and for the maximum size of a matching. All our reductions use the following gap version, in which YES instances have a perfect matching.
The proof is given in Section A.3.
Lemma 4. For some constant , distinguishing from is NP-hard for instances of -. Moreover:
(i) Under Gap-ETH, no algorithm distinguishes these cases in time .
(ii) Under weak ETH, no algorithm distinguishes these cases in time for any constant .
(iii) Under NP SUBEXP, there is a constant such that no algorithm distinguishes these cases in time .
We may assume that every element occurs in at least one triple, since otherwise has no perfect matching. This gives and hence .
Coordinates. We use irrational coordinates for convenience; rounding them to polynomial bit length preserves our bounds, since moving each of terminals by at most some very small changes the optimum by at most .
Technical Overview
All our reductions use the gap version of three-dimensional matching from Theorem 4, which asks whether an instance with parts of size admits a perfect matching or has no matching larger than .
APX-hardness in linear dimension
Warm-up: connecting cables. We first consider a variant of the problem in which the terminals are trees of line segments, which we call cables.
Definition 5 (Euclidean Cable Steiner Tree).
Input: a finite collection of pairwise disjoint cables in a Euclidean space, each a connected union of finitely many line segments.
Feasible solutions: finite sets of line segments, possibly meeting at Steiner points, that together with the cables form a connected network.
Objective: minimize the total length of the added segments.
We first explain how cables encode a matching, then replace them by densely spaced point terminals while preserving the approximation gap.
Given , our goal is to construct a cable instance with minimum connection cost , where . Equivalently, has a matching of size at least if and only if the cables can be connected at cost at most .
This identity yields a constant hardness gap for Euclidean Cable Steiner Tree, since each missing matching triple increases the connection cost by . With , the minimum connection cost is , so
The ratio between these bounds is the constant .
The construction, illustrated in Figure 2, has one cable for each element and an additional backbone cable. The cables remain disjoint and stay far apart except near gadgets, where short connections can join them.

Figure 2. A cable instance with and the triples (left), (middle), and (right), so . Only the red connections contribute to the cost; the element cables and backbone are shown in grey. An optimal network uses the four-port Steiner tree at one square and three fallback segments, with total cost .
We use two types of gadgets, shown in Figure 3. We first describe the gadgets and specify which cables attach to each one, showing how they encode a matching; the geometric layout will be described later. For each triple , draw a square gadget of side with corners labelled , , , . For each element , draw a fallback gadget consisting of two points at distance , labelled and . We call these labelled points ports. For each label , a single cable connects all ports labelled outside the gadgets. We call the backbone. Thus contains the corner labelled of each square gadget for a triple containing and the point labelled of its fallback gadget, while the backbone contains the port labelled of every gadget.

Figure 3. Connection costs at the gadgets, with cables in grey and added connections in red. A square for a triple can join , while the fallback for joins to the backbone . Only the four-port Steiner tree improves on the baseline of per connection, saving exactly .
For the forward implication, let be a matching of size . For each triple in , join its three element cables to the backbone using the four-port Steiner tree in its square (Figure 3(c)), of length . Since the triples in are disjoint, this connects element cables; join each of the remaining cables to the backbone by its fallback segment, of length . The resulting network is connected and has total cost .
For the converse, a network connecting the cables may attach anywhere along them. For the analysis, we therefore require different cables to stay far apart except near shared gadgets, making connections elsewhere expensive. For each gadget , let be its centre and the closed ball of radius 20 around .
Definition 6. The cables are separated if the following conditions hold.
(S1) Between cables. The balls are pairwise more than 20 apart. Inside each ball , the cables consist exactly of the straight segments extending from the ports of directly away from to the boundary of . Any two points on different cables less than 20 apart lie in a common ball.
(S2) Within a cable. Every cable segment has length at least 1. Non-incident segments of the same cable are at least 1 apart, and incident segments meet at an angle of at least .
Figure 4 illustrates these conditions.

Figure 4. Separated cables.
We show that there is an optimal network that is clean: it consists precisely of the cables, fallback segments, and Steiner trees joining all four corners of selected squares (Figure 3(c) and (d)). Removing a part of the network that joins cables leaves at most components. One contains the backbone, and each other component contains an element cable that can be joined to the backbone by its fallback segment, so at most fallback segments of total length at most restore connectivity. If the cables share no gadget, separation forces this part of the network to bridge gaps of at least 20, so replacing it by fallback segments is cheaper.
We may therefore assume that each connection joins cables at points inside the ball of a single gadget ; § 4.3 gives the formal argument. It is easy to modify them without increasing their length so that they attach only at its ports, as in Figure 3. Of these connections, only the four-port tree at a square beats the fallback cost of joining cables, saving .
Two such trees cannot use squares sharing an element , since both would join to the backbone and create a cycle. Their triples therefore form a matching, saving at most from the fallback cost . This gives a minimum connection cost of at least .
With enough dimensions, placing the gadgets and joining equally labelled ports into separated cables is relatively straightforward. We also keep the cables short, which will be useful later when replacing them by point terminals. The following construction achieves in dimensions, preserving a constant approximation gap.
High-dimensional routing. We work in , assigning each gadget its own unit coordinate vector and each cable its own unit coordinate vector . We draw each gadget in a plane parallel to the -plane, where are the two remaining unit coordinate vectors. For a sufficiently large constant , centre gadget at , with ports and for a square, or for a fallback. The centres of any two distinct gadgets are then at distance .
The hub of is , and each port labelled is joined to it by two segments. The gadget segment extends straight away from the gadget’s centre, within its plane, until it reaches distance from the centre; the hub segment then joins this point to . Gadgets and cables in high dimensions are hard to draw, but we try our best in Figure 5.

Figure 5. The cable joins its ports at two squares and a fallback to the hub , using a gadget segment followed by a hub segment for each port. Gadgets are centred at in planes parallel to the -plane, and dashed arrows mark the orthogonal directions and .
For sufficiently large , the separate coordinate directions and ensure that different cables come close only near a shared gadget, giving separation. There are segments, each of constant length, so the total cable length is .
From cables to point terminals. We now replace the cables by closely spaced point terminals. Connecting the points along each cable adds about to the cost of joining the cables. Since the routing above has , the total cost remains , so the additive gap still gives a constant approximation gap.
For a small parameter , sample each cable segment at spacing , including its endpoints, and let be the resulting set of terminals. The edges between consecutive samples have total length .
A short tree spanning must essentially follow the cables, paying their total length in addition to the cost of connecting them. The bounds for the cable instance therefore carry over up to a small error.
Theorem 7 (Cable reduction). There is an absolute constant such that, for separated cables and every ,
For the upper bound, take the union of the four-port trees at the squares of a maximum matching, the fallback segments for uncovered elements, and all edges between consecutive samples. This gives a connected network spanning of length .
For the lower bound, let be an optimal Steiner tree on . If contains all edges between consecutive samples, they contribute length and the remaining edges connect the cables, so the cable bound applies without an error term. However, need not contain these edges, but a short tree must follow the cables closely. The following lemma recovers a tree along each cable at an additional cost of , allowing us to apply the cable bound up to this error.
Lemma 8 (Cable recovery). Let be a Steiner tree on of length . By adding segments of total length to , we obtain a network containing pairwise disjoint trees , one for each cable . Each spans the sampled terminals on and lies within distance of that cable; together, these trees have total length at least .
The approximation gap. Taking all edges between consecutive samples and all fallback segments shows that has length , since every gadget contributes constant cable length and hence ; so Theorem 8 applies.
Set . Since both and are , choose constants and such that and . If , the upper bound in Theorem 7 gives . If , then
by the lower bound in Theorem 7,
since ,
by the choice of ,
by the choice of .
A -approximation would therefore distinguish the source cases. Since is constant, there are terminals in dimensions, which proves APX-hardness in linear dimension.
Reducing the dimension
We reduce the dimension using the Johnson–Lindenstrauss lemma [29]. For any fixed , the deterministic construction of Engebretsen, Indyk, and O’Donnell [21] maps the terminals in dimensions to in dimensions. After rescaling, they satisfy
This maps the terminals, but to compare the Steiner tree optima on and , we must also map the Steiner points between the two spaces. Following Karthik C. S. [41], Section 4.2, we use Kirszbraun’s extension theorem [31] to extend the terminal maps to all points of the two spaces, including the Steiner points. A tree on then gives a network connecting of no greater length, while a tree on gives a network connecting of length at most times the original length. Applying this to optimal trees gives
Choosing to be a sufficiently small constant therefore preserves the constant approximation gap in dimensions.
No PTAS in dimension . Our reduction maps a 3SAT formula with variables to terminals in dimensions with a constant approximation gap. Following Trevisan [40] for TSP, we increase the number of terminals by adding copies of an existing terminal, leaving the optimum unchanged. With terminals for a small constant , the dimension is , while a PTAS would decide the formula in time . Since can be chosen arbitrarily small, a PTAS would imply , so the lower bound follows from , a weaker assumption than ETH.
Lower bounds in fixed dimension
For the fixed-dimensional lower bounds, we retain separation but allow longer cables. For fixed , we must allow the total cable length to grow faster than the matching instance size . Only the cable routing changes, so we can use the same gadgets and matching argument: YES and NO instances differ by in connection cost, and by at least after dense sampling. Every tree on the samples also pays for the cables, so both optima are of order and their relative gap is , which is subconstant.
This smaller gap suffices if we can route the cables with total length
The relative gap is then , so choosing for a sufficiently small constant distinguishes the YES and NO instances. This gives . For any fixed , an approximation scheme running in time would therefore solve the source matching gap in time , provided that sampling produces polynomially many terminals. By Theorem 4, this would contradict weak ETH. It remains to construct a separated routing of this total length.
Cube wiring. To route the cables without crossings, we use a consequence of the Cube Wiring Theorem of de Berg, Bodlaender, Kisfaludi-Bak, Marx, and van der Zanden [19] (see Theorem 31 [18]). For fixed , every graph with vertices and maximum degree at most , the degree of the integer grid in , can be drawn in polynomial time in the cube with . Vertices map to distinct grid points, and edges follow grid paths that meet only at common endpoints. These paths are edge-disjoint, so their total length is bounded by the number of grid edges in the cube, which is .
From the grid drawing to cables. For each label , construct a tree whose leaves are exactly the gadgets with a port labelled and whose internal vertices have degree three. The union of these trees has vertices and maximum degree four, so the cube-wiring theorem gives a grid drawing in . We turn the drawing of each into a cable by modifying the paths near each gadget to attach to its ports. The resulting cables are separated and have total length
From cables to point terminals. By Theorem 7, the optimum on the sampled terminals equals up to an error of . We choose so that this error is at most half the matching gap , and set . This gives
Since , the relative gap is , so a -approximation with distinguishes the two cases for a sufficiently small constant . Sampling produces terminals, which is polynomial in . Together with , this gives the weak-ETH lower bound above.
Under Gap-ETH, the same reduction would have given a tight lower bound, excluding approximation schemes running in time . The weaker assumption still rules out time for some constant , by Theorem 4.
Lower bounds in the plane
To handle crossings in the plane, we build on the crossover layout of Garey, Graham, and Johnson [25]. Our construction is essentially theirs, but the analysis uses our cable framework, with terminal sampling and cable recovery as before. We show that the optima of YES and NO instances differ by ; since the total cable length is , this yields the relative gap required for .
Gadgets and layout. Fix . We use two types of gadgets: equilateral triangles of side length or , and unit squares (Figure 6(a, b)). A crossover consists of an upper and a lower triangle where a horizontal and a vertical cable meet, with the cables above, below, and , to the left and right at its corners (Figure 6(c, d)).
Figure 6. Gadgets in the plane, with cables in grey and connections in red. (a, b) Shortest networks joining all corners of an equilateral triangle of side and a unit square. (c, d) At an up crossover , the upper triangle joins , , and ; at a down crossover, the lower triangle joins , , and .
The layout (Figure 7) has horizontal levels , where level contains the backbone, and a square below level for each triple. For each element of a triple, a vertical column runs from a corner of its square up to level , crossing the lower levels at crossovers, and the remaining corner of the square is joined to the backbone. The top crossover of each column, on level , is an -crossover, with an upper triangle of side instead of .

Figure 7. Layout for elements 1, …, 6 and three triples, with optimal connections shown in black. The perfect matching corresponds to the columns of and being up and those of being down.
Clean trees and perfect matchings. We first explain how a short tree connecting the cables encodes a matching: up to small errors, such a tree consists of the cables and Steiner trees, each joining all ports of one gadget.
Definition 9. A tree is clean if it contains the cables and connects them only at gadgets, using Steiner trees on their corners (Figure 6(a, b)): whenever it uses a square, it joins all four cables, and whenever it uses a triangle, it joins all three.
At a crossover , the upper triangle joins and to , while the lower joins them to (Figure 6(c, d)). Using both would join to twice and create a cycle. We call up if the upper triangle is chosen, down if the lower one is chosen, and broken if neither is chosen. First consider a clean tree with no broken crossovers, so each crossover uses exactly one triangle. A unit triangle costs and the smaller upper triangle of an -crossover costs , a saving of . Since the cost at a square is , such a tree using squares and having up -crossovers has length , where is the number of crossovers. We show that every such tree has length at least
with equality only when the used squares form a perfect matching.
Every crossover of such a tree joins to , so each level is connected and level 0 contains the backbone. The argument uses the following properties.
(P1) Columns. Within a column, all crossovers below an up crossover are up, and all those above a down crossover are down. Otherwise, an up crossover would lie directly above a down one, leaving the cable between them attached by neither (Figure 8(d)).

Figure 8. Columns for element 3, with the top -crossover circled. (a) The square is unused and all crossovers are down. (b) At a switch, both crossovers attach to the cable between them, joining levels 1 and 2. (c) All crossovers are up, so the top one joins levels 2 and 3. (d) An up crossover directly above a down one leaves the cable between them unattached.
(P2) Squares. If a square is used, the bottom crossover of each of its three columns must be up: a down one would already connect the bottom cable to the backbone through level 0, so using the square would create a cycle. If the square is unused, all three bottom crossovers must be down, since otherwise the bottom cables would be unattached.
(P3) -crossovers. For each element , at most one -crossover on level is up. An up crossover joins levels and by attaching the cable above it, which continues along level ; two such crossovers would join the same levels twice and create a cycle (Figure 8(c)). Hence .
These properties imply that all crossovers in a column of an unused square are down (Figure 8(a)). In a column of a used square, the bottom crossover is up, and the crossovers either remain up throughout (Figure 8(c)) or change once from up to down at a pair of consecutive crossovers. We call this pair a switch (Figure 8(b)); both crossovers attach to the cable between them, joining their levels.
Lower bound. Columns of unused squares are down throughout and join no two levels, while each column of a used square joins exactly one pair of consecutive levels: either at its switch or, if it is up throughout, at its -crossover. All pairs must be joined, and each used square has three columns, so . Together with from (P3), this gives a length of at least , with equality requiring and .
Optimal clean trees. Suppose such a tree has length , so and . Each element then has exactly one up -crossover on level , and these crossovers already connect every pair of consecutive levels. A switch would therefore create a cycle, so no column has one. By (P1), every column is all up or all down, and is all up if and only if its -crossover is up. By (P2), a square is used exactly when all three of its columns are up. If two used squares shared an element , their columns for would give two up -crossovers on level , contrary to (P3); hence the corresponding triples form a (perfect) matching.
Conversely, any perfect matching gives a clean tree of length by choosing the corresponding squares and making all crossovers in their columns up and all remaining crossovers down (Figure 7). Intuitively, the -crossovers make it cheaper to join levels at column tops, discouraging switches that allow overlapping triples.
To prove an approximation gap, we will argue that every tree whose length is close to yields a nearly perfect matching. Since there are no fallbacks, we cannot generally make a tree clean as in higher dimensions. We therefore count broken crossovers, missing discounts, and other ways of connecting the cables. We show that each such deviation costs at least and that a tree with few deviations still yields a large matching.
The cable reduction
This section gives a reduction from three-dimensional matching to Euclidean Steiner Tree that applies to any separated cable routing. § 5 and § 6 construct such routings in growing and fixed dimension.
Recall that the matching instance has three parts of size , total size , and maximum matching size . The construction takes place in , with determined by the cable routing.
Cable instances
Definition 5 (Euclidean Cable Steiner Tree).
Input: a finite collection of pairwise disjoint cables in a Euclidean space, each a connected union of finitely many line segments.
Feasible solutions: finite sets of line segments, possibly meeting at Steiner points, that together with the cables form a connected network.
Objective: minimize the total length of the added segments.
Euclidean Cable Steiner Tree contains the usual Euclidean Steiner Tree problem as the special case where every cable is a single point, and we believe this generalization is of independent interest. It can also be viewed as a completion version of Euclidean Steiner Tree: parts of the network are already built and must be connected at minimum additional length, as when extending road, pipeline, or cable networks. Althaus, Rauterberg, and Ziegler [1] studied exact algorithms for the planar case.
We now give the construction sketched in § 3.1 in full; Figure 2 shows a small example. Our instance has one square gadget for each triple and one fallback gadget for each element; these gadgets are indexed by and have centres . We use the same two orthogonal unit coordinate vectors for every gadget and define the ports, where the cables attach, by the following coordinates and labels.
(a) For the square of a triple , the ports are the four points and . They form a square of side length .
(b) For the fallback of an element , the ports are the points . They are at distance .
We use the elements of and an additional symbol as labels. The shortest networks joining two, three, or four ports of a square have lengths , , and , respectively (Figure 3). Only the four-port network costs less than per joined pair.
For each label , we join the ports labelled by a tree of line segments, the cable , so that different cables are disjoint; we call the backbone. Let be the total cable length and, for each gadget , let be the closed ball of radius centred at . We require the cables to satisfy the following condition, illustrated in Figure 4.
Definition 6. The cables are separated if the following conditions hold.
(S1) Between cables. The balls are pairwise more than 20 apart. Inside each ball , the cables consist exactly of the straight segments extending from the ports of directly away from to the boundary of . Any two points on different cables less than 20 apart lie in a common ball.
(S2) Within a cable. Every cable segment has length at least 1. Non-incident segments of the same cable are at least 1 apart, and incident segments meet at an angle of at least .
Explicitly, the segments in (S1) are for when is a square, and for when is a fallback. The segments leaving distinct ports of a gadget extend in orthogonal or opposite directions and are therefore at least apart. Together with (S1), this shows that points on different cables are at least apart. By (S2), there are at most cable segments, and by (S1), .
For , we form by placing equally spaced terminals along each cable segment of length , including both endpoints. Consecutive terminals along a segment are at distance in , and the edges between them have total length , with .
The main result of this section shows that the optimum on equals the cable length plus the cost of connecting the cables, up to an error of .
Theorem 7 (Cable reduction). There is an absolute constant such that, for separated cables and every ,
Definition 10. A network is clean if it consists of the cables, the four-port Steiner trees at squares whose triples form a matching, and the fallback segments for all elements outside these triples.
A clean network joins every element cable to the backbone and is therefore connected; if it uses squares, its length is
The clean network corresponding to a maximum matching contains , proving the upper bound in Theorem 7. For the lower bound, we will show that every short tree on has length at least that of the clean network of some matching, up to an error of .
Recovering the cables
Suppose for a moment that an optimal tree on contains all edges between consecutive terminals, and hence all cables. Removing the cables leaves subtrees joining distinct cables. We will show that replacing each subtree by fallback segments or a four-port Steiner tree gives a clean network of no greater length, proving the lower bound of Theorem 7 even without the error term . In general, a tree on need not contain the cables, but it cannot stray far from them cheaply. We show that adding a little length suffices to obtain, for each cable, a tree that stays within distance of it.
For each cable segment , choose terminals and at distances between and from its two endpoints, respectively. We call the middle segment of and its two remaining parts the end pieces, each of length at most . Each end piece consists of edges between consecutive terminals. We surround each middle segment by a closed cylinder of radius with flat caps, called its tube Figure 9. These tubes are pairwise disjoint: for segments on different cables or non-incident segments on the same cable, this follows because their distance exceeds . If segments share an endpoint , their angle is at least by (S2), so every point on the middle segment of is at least from and hence at least from . The tube of therefore has distance greater than from , so the two tubes are disjoint.

Figure 9. Sampling and tubes. (a) A sampled cable with tubes around its middle segments. (b) The tube around a sampled segment . (c) Two segments meeting at at an angle of at least . Every point on the middle segment of lies at least from and therefore at least from , so the tubes are disjoint.
Fix a tree of length spanning . Its intersection with a tube may be disconnected, but adding edges between consecutive samples along the cable segment lets us join its components at small cost (Figure 10).

Figure 10. Connecting components inside a tube. Black segments show . The components reach the left cap, the lateral boundary, and the right cap. Three red edges between consecutive samples connect them.
Lemma 11. Let be the tube around a middle segment and the length of inside . We can connect all sampled terminals on that segment within by adding edges between consecutive terminals, with total added length at most .
Proof. Let be the number of components of containing sampled terminals; see Figure 10. We can connect these components using edges between consecutive samples, each of length at most , for a total added length of at most .
If , each such component meets the tube boundary, since is connected. A component meeting the lateral boundary contains a path of length at least from a sample on the cable segment to the side of the tube, so there are at most such components. Assign every other component to an end cap that it meets. For the components assigned to the left cap, choose one sampled terminal from each and order these samples from left to right. The th sample is at distance at least from the cap, so its component contains a path to the cap of at least this length. These paths lie in distinct components and are therefore disjoint. Their lengths sum to at most , giving
It follows that . The same bound holds at the right cap. Consequently , which proves the claimed bound on the added length. If , nothing needs to be added.
We now apply this bound to all tubes to prove the cable-recovery lemma.
Lemma 8 (Cable recovery). Let be a Steiner tree on of length . By adding segments of total length to , we obtain a network containing pairwise disjoint trees , one for each cable . Each spans the sampled terminals on and lies within distance of that cable; together, these trees have total length at least .
Proof. Let be the number of cable segments. For each cable segment , let be the length of inside the tube of . The tubes are disjoint, so . By Theorem 11 and Cauchy–Schwarz, the total length added inside the tubes is at most , since . We also add all edges between consecutive terminals along the end pieces, with total length at most .
After adding these edges, the samples on the middle segment of each cable segment are connected inside its tube. Choose a tree in this network spanning these samples; because it contains and , it is at least as long as the middle segment.
For each cable , let be the union of the trees for its segments and all their end pieces. The tubes are disjoint and meet the end pieces only at and , so each is a tree spanning the sampled terminals on , and the trees are pairwise disjoint. Moreover, lies within distance of and has length at least , so .
Connectors and cleaning
By cable recovery, we can add segments of total length to to obtain a connected network containing the forest , whose length is at least . We choose a spanning tree of this network containing and repeatedly remove leaves outside , which ensures that every leaf of lies in .
Removing decomposes the rest of into connectors: subtrees whose leaves, called attachments, lie on and whose other points lie outside (Figure 11(a)). Every connector has at least two attachments, and it cannot attach twice to the same , since this would create a cycle in .

Figure 11. Connectors at the square for and the fallback of . (a) The recovered trees (black) lie in cable tubes (grey), and connectors (red) attach at the dots. Connector is good at ; is bad: its attachments on and lie outside the gadget balls. (b) The incidence tree of the trees and connectors.
The bipartite graph between the trees and the connectors, with one edge per attachment, is also a tree, which we call the incidence tree (Figure 11(b)). If denotes the number of attachments of connector , this tree has edges and one vertex for each of the trees and each connector. Since a tree has one edge fewer than vertices,
Connectors attach to the trees , so their attachments lie within distance of the cables. An attachment is near a port of a gadget if it lies within distance of the cable segment from to the boundary of , as specified in (S1). We compare connectors joining all cables at a gadget with the shortest network connecting these cables (at the ports, as in Figure 3), and all other connectors with fallback segments.
Definition 12. A connector is
(i) good at the square of a triple if it has exactly four attachments, one near each of the ports ;
(ii) good at the fallback of an element if it has exactly two attachments, one near each of the ports and ;
(iii) bad otherwise.
The following lemma shows that a good connector is at least as long as the shortest network on the ports of its gadget, and a bad connector at least as long as fallbacks, up to small errors.
Lemma 13. Let be a connector with attachments.
(i) If is good at a square, then .
(ii) If is good at a fallback, then .
(iii) If is bad, then .
Proof. Let be the attachments of . They lie within distance of distinct cables, so for each we can choose a point on the corresponding cable with , and if is good at a gadget , we choose it inside . We group the attachments according to where these points lie: and are in the same group if and lie in a common ball , and forms a group on its own if lies in no ball. By (S1), attachments in different groups are at distance at least , and since a ball meets at most four cables, every group has at most four attachments.
If there are groups, then is bad, since a good connector has all its attachments near a single gadget. The balls of radius around one attachment from each group are disjoint, and since is connected and has points outside each of them, it runs from the centre of each ball to its boundary. Hence
which gives (iii).
Otherwise, all points lie in the ball of one gadget . We project onto the square or fallback segment of to obtain a network of no greater length (Figure 12). The projection sends to its port and does not increase distances, so the projected attachment lies within distance of . We then add the segments to obtain a network connecting ports of , of length at most .

Figure 12. Projection onto a square gadget, for three cables. The shaded regions project to the corners, so each cable point projects to its port , and to . The projected network is no longer than , and the dotted segments, each of length at most , join it to the ports.
If is good, we have connected all ports, at a cost of at least for a square or for a fallback, proving (i) and (ii). If is bad, the network connects two or three ports of a square, requiring at least or , respectively (Figure 3). In either case, this is at least , so
where the last inequality uses , proving (iii).
We prove that for every short tree on , there is a clean network of length at most by showing that the triples of the good square connectors form a matching whose clean network satisfies this bound.
Lemma 14. For every tree on with , there is a clean network of length at most , where is an absolute constant.
Proof. Let be the number of good square connectors. If two of their triples shared an element , both connectors would attach to and , creating a cycle in the incidence tree. Their triples therefore form a matching, whose clean network has length , which we will now compare with the length of .
By Theorem 13, each good square connector has and length at least
while every other connector has length at least . Summing over the connectors and using (3) gives
The tree consists precisely of these connectors and the forest , which has length at least . Since we obtained from by adding length and then removing edges,
Thus the clean network of this matching has length at most . Since , this is at most for an absolute constant . □
Proof of the lower bound in Theorem 7. Let be an optimal tree on . The clean network using only fallbacks gives , since . We can therefore apply Theorem 14 to obtain a clean network of length at most . Its squares form a matching, so and its length is at least . Rearranging gives the claimed lower bound. □
No PTAS in high dimensions
We first route the cables in linear dimension, which by Theorem 7 gives a constant approximation gap, and then reduce the dimension to .
Orthogonal routing in linear dimension
By Theorem 7, it suffices to construct a separated cable routing of total length . We reserve a distinct coordinate direction for each gadget and each cable, placing the gadgets far apart on their axes and joining the ports of each cable to a common hub on its axis. Different cables then come close only near a gadget they share.
Concretely, besides the directions , in which the gadgets are drawn, reserve a unit coordinate vector for each gadget and for each label , all mutually orthogonal; this uses dimensions. Set . We place each gadget at , and let the hub of be . Each port labelled has the form , where and for a square or for a fallback. The cable has a gadget segment from this port in direction up to the bend , followed by a hub segment from the bend straight to the hub, which together form the branch
The cable is the union of these branches over all ports labelled ; we call this the orthogonal routing (Figure 5).
Lemma 15. The cables of the orthogonal routing are separated and have total length .
Proof. We first establish two distance bounds, illustrated in Figure 13.

Figure 13. Orthogonal routing near gadgets and . (a) Gadget segments lie within distance of their centre (dashed), keeping segments of distinct gadgets more than 20 apart. (b) Hub segments are at distance at least from every other cable. The cables inside (dotted) therefore consist exactly of the gadget segments of .
(a) The gadget segments of extend radially away from in the directions and end at distance from it. Since gadget centres are apart, segments from distinct gadgets are at least apart.
(b) Every hub segment is at distance at least from every other cable. To see this, write a point on the hub segment from gadget to as
Its -, - and -coordinates are , and . A point on another cable has zero -coordinate. If it does not lie on a branch from , its -coordinate is also zero, so
Otherwise, the branches containing and share the same gadget . Since they belong to different cables, they use different ports of , so the branch containing leaves in a direction orthogonal or opposite to and has nonpositive -coordinate. The - and -coordinates then give
(S1) Since the centres are apart, the balls are more than 20 apart. No hub segment enters any of these balls: the coordinates in (b) give distance at least from the centre of its gadget and at least from every other centre. By (a), gadget segments from other gadgets also stay outside . Thus inside , the cables are exactly the straight segments from the ports of to the boundary. By (a) and (b), two points on different cables less than 20 apart must lie on gadget segments of the same gadget. These segments run in orthogonal or opposite directions from its centre, so both points lie within distance 20 of it.
(S2) Gadget segments have length , and hub segments have length 96. The branches of each cable meet only at its hub, so the cable is a tree. A gadget segment from has -coordinate , whereas all other branches of its cable have -coordinate zero, giving distance at least between them. Every pair of non-incident segments contains such a gadget segment, so their distance is at least . The angles at bends and at hubs satisfy
so both are at least .
Finally, each of the branches has length less than 128, giving total cable length .
Lemma 16. There are constants and such that the following holds. Given an instance of 3DM-3, one can construct in polynomial time terminals and a threshold with
Consequently, Euclidean Steiner Tree is APX-hard already in dimensions.
Proof. Construct the cables of the orthogonal routing. By Theorem 15, they are separated and for a constant . Fix a constant
where is the constant in Theorem 7, and set .
The first implication is the upper bound in Theorem 7. For the second, let . Then
by the lower bound in Theorem 7,
since ,
by the definition of ,
since and ,
by the definition of ,
since .
Since is constant, and .
Reducing to logarithmic dimension
Writing for the gap constant in Theorem 16, we now reduce the dimension of the terminal set constructed there, making no further use of the cables.
The Johnson–Lindenstrauss lemma [29] states that, for every , any points in a Euclidean space can be mapped into dimensions so that, after rescaling, every pairwise distance changes by a factor between and . Using the deterministic construction of Engebretsen, Indyk, and O’Donnell [21], we obtain in polynomial time points , , with
We follow Karthik C. S.’s argument in Woodruff et al. [41 Section 4.2], using Kirszbraun’s theorem to compare optimal Steiner tree lengths. Since these bounds apply only to distances between terminals, we use Kirszbraun’s extension theorem [31] to extend the map to Steiner points. For , a map is -Lipschitz if for all . By Kirszbraun’s theorem, extends to a -Lipschitz map , that is,
In particular, if maps a set of terminals to a lower-dimensional space and stretches distances between terminals by a factor of at most , then the extension maps also every Steiner point to the lower-dimensional space and stretches distances between a terminal and a Steiner point, or between two Steiner points, by at most the same factor. Applying to the vertices of a tree and joining the mapped vertices by straight segments therefore yields a connected network whose length is at most times that of the original tree.
Lemma 17. Let and be finite point sets in Euclidean spaces of possibly different dimensions. If, for some , their pairwise distances satisfy for all , then
Proof. We prove the two inequalities by applying Kirszbraun’s theorem in opposite directions. First, the map is -Lipschitz by the left-hand inequality. Extending this map to the Steiner points of an optimal tree on gives a network on of length at most , so . Conversely, the map is -Lipschitz by the right-hand inequality. Extending this map to the Steiner points of an optimal tree on gives a network on of length at most , so .
Proof of Theorem 1. Apply Theorem 16 to obtain and , and construct as above in dimensions. Combining (4) with Theorem 17 for gives
We may assume . A -approximation distinguishes these cases: in a YES instance, it returns a network of length at most
whereas in a NO instance every network has length at least . Thus the reduction preserves a constant approximation gap in dimensions, proving the theorem.
Padding to doubly logarithmic dimension
Proof of Theorem 2. Let be a terminal set obtained by the reduction in the proof of Theorem 1. As shown there, a -approximation distinguishes the source matching instances. By Theorem 4(iii) and the polynomial size of the reduction, under there is a constant such that no such approximation runs in time .
To pad , set , which is at least for sufficiently large , and add terminals at the position of one original terminal. This leaves the optimum and the approximation gap unchanged. The padded instance has terminals in dimensions, since implies .
Suppose Euclidean Steiner Tree admits a PTAS in dimensions for terminals. Running it on the padded instance with the same accuracy would distinguish the source cases in time , contradicting the lower bound.
Lower bounds in fixed dimension
We prove Theorem 3 for fixed . We use the gadgets and cable reduction (Theorem 7) from § 4, changing only the routing. In , the cables cannot all be short, so we route them along a grid drawing of total length . Choosing keeps the sampling error in Theorem 7 below half the matching gap, so the YES and NO optima remain apart. Since both are , the relative gap is , and hence .
Cable routing by cube wiring
We use the following consequence of the Cube Wiring Theorem of de Berg, Bodlaender, Kisfaludi-Bak, Marx, and van der Zanden [19].
Theorem 18 ([18 Theorem 31]). There exists a constant such that for all , any graph with vertices and maximum degree is the topological minor of the -dimensional grid hypercube of side length .
A graph is a topological minor of the grid precisely when the grid contains a subdivision of . The theorem therefore gives a grid drawing in , where : vertices lie at distinct grid points, and edges follow internally disjoint grid paths. The construction in [18] finds such a drawing in polynomial time.
We construct a graph with a vertex for every gadget. We then compute a grid drawing of using Theorem 18 and modify it to create the actual gadgets and cables connecting their appropriate ports.
The graph. Let be the number of gadgets containing a port labelled . For an element , these are its fallback and the squares for triples containing ; for the backbone label , they are all gadgets. Construct a tree whose leaves are exactly these gadgets and whose internal vertices have degree three. Take the union of these trees, which share only gadget vertices, and subdivide every edge twice to obtain , ensuring that each original edge of a tree follows a path of at least three unit grid edges in the grid drawing. We modify the routing only along the first grid edge of each path leaving a gadget, leaving an unchanged grid edge between any two modified parts of a cable; we use this to prove (S2). In , square gadgets have degree four, fallback gadgets degree two, and all other vertices degree at most three. Since , the total number of vertices is .
The cables. We apply Theorem 18 to compute a grid drawing of and scale it by 100. This assigns each gadget a grid point . Each scaled unit edge is a grid segment of length 100, and grid segments without a common endpoint are at least 100 apart.
We centre each gadget at and modify each drawn tree near the gadgets to attach it to the appropriate ports. The resulting cables form the cable routing (Figure 14).

Figure 14. Wiring a square gadget. (a) Scaled grid drawing around . (b) continue straight from their ports; leaves along and rejoins its grid segment at . Inside the dotted ball , the cables follow the gadget axes, as required by (S1).
For each label of a gadget , the drawn tree leaves along the grid segment , where the are distinct signed coordinate vectors. We draw the gadgets in planes parallel to the -plane, with ports in directions for a square and for a fallback. We assign each label a port and write for its direction from ; the assignment and local modifications are as follows (Figure 14(b)).
If is an available port direction, assign label the port in that direction, so . Replace the grid segment by the straight segment from to ; for example, has in the figure.
Otherwise, assign label one of the remaining ports, so ; for example, has and in the figure. The cable follows from its port to , continues parallel to the grid segment, and joins it at its midpoint:
At each port, the cable begins with a segment in direction of length at least .
Each local modification adds at most 50 to a grid segment of length 100. Since the grid paths are edge-disjoint and the cube contains at most unit grid edges, the total cable length satisfies
The cables can be constructed in polynomial time, and the following lemma shows that they are separated, with its proof deferred to Section A.1.
Lemma 19. For every fixed , the cable routing in consists of separated cables.
For Euclidean Cable Steiner Tree, the minimum connection cost is , independently of (§ 4.2). Thus the cable routing gives a constant approximation gap in fixed dimension.
Corollary 20. For every fixed , Euclidean Cable Steiner Tree is APX-hard in .
Proof. Given an instance of 3DM-3, construct the cables above. They are separated by Theorem 19 and have minimum connection cost . Since , this cost equals if and is at least if . By Theorem 4, approximating it within the constant factor is therefore NP-hard.
This gives a negative answer for to a question of Bartlmae, Jünger, and Langetepe [7]. They gave a planar PTAS for a line and point terminals, and asked whether it extends to segment terminals. It remains open whether Euclidean Cable Steiner Tree is APX-hard in the plane or admits a PTAS.
The gap in fixed dimension
Lemma 21. There are constants and such that, given an instance of 3DM-3, one can compute in polynomial time a set of terminals and a threshold satisfying
Proof. Use the cable routing from § 6.1, which is separated by Theorem 19 and has total cable length . Let be the constant in Theorem 7 and choose
so that , and set and . The YES bound follows from the upper bound in Theorem 7. For the NO bound, set . Then
The threshold satisfies . Since , sampling gives .
**Proof of Theorem 3 for \varepsilon=(a/(4c_d))m^{1/(1-d)} and apply Theorem 21 to the matching instance. The same gap comparison applies, with \varepsilon^{-(d-1)}=\Theta_d(m)=\Theta_d(r) for a fixed would solve the matching gap in time , contradicting Theorem 4.
Under Gap-ETH, the same argument would have ruled out time , since this would yield a -time algorithm for the matching gap, contrary to Theorem 4(i). Under NP SUBEXP, take from Theorem 4(iii). Running time would give a -time algorithm for the matching gap, contradicting this bound. These arguments establish both bounds stated after Theorem 3, with independent of because it depends only on the source matching problem.
Lower bounds in the plane
We now prove Theorem 3 for , using the planar construction outlined in § 3.4. The main step is the following analogue of Theorem 21.
Lemma 22. There are constants and such that, given an instance of 3DM-3, one can compute in polynomial time a set of terminals and a threshold satisfying
The construction
We recall the gadgets and cable connections of § 3.4, illustrated in Figure 7, before giving their geometric placement in the next subsection.
Gadgets. Fix . As in § 4, cables are joined at small gadgets, ending at their corners, called ports. We use two types of gadgets: equilateral triangles of side or , and unit squares, whose connection costs are shown in Figure 15. A crossover has an upper and a lower triangle, as in Figure 6(c, Figure 6d). We call it an -crossover when its upper triangle has side ; all remaining triangles have side .

Figure 15. Shortest networks on ports of a triangle of side (a, b) and of a unit square (c–e), with cables in grey and connections in red. Lengths are shown as multiples of .
Layout. We label the elements of by and write . As in Figure 7, the horizontal levels are numbered from bottom to top, with the backbone on level . Each triple has a square below level and three columns, one for each , while its fourth corner connects to the backbone. The column for runs from to level , with a crossover on each level . Its top crossover is an -crossover, so choosing its upper triangle saves . Each column has at most crossovers, giving a total of crossovers.
Cables. At a crossover , let denote the cables above and below, and those to the left and right (Figure 6(c, Figure 6d)), so for the crossover directly above . Within each column, cables connect the square to the lowest crossover and consecutive crossovers to each other, while along each level they connect adjacent crossovers. A column of element ends on level , and the cable above its top crossover continues along that level; the backbone is part of the leftmost cable of level . There are cables below crossovers and along the levels, for a total of cables. The ports of each gadget lie on distinct cables.
Definition 9. A tree is clean if it contains the cables and connects them only at gadgets, using Steiner trees on their corners (Figure 6(a, b)): whenever it uses a square, it joins all four cables, and whenever it uses a triangle, it joins all three.
Choosing the upper triangle makes a crossover up, and choosing the lower makes it down (Figure 6(c, d)). The possible column patterns, including a switch from up to down, are shown in Figure 8.
First consider a clean tree with no broken crossovers, and let be the number of used squares and the number of up -crossovers. It uses one triangle at each crossover, at a cost of for an up -crossover and otherwise, while each used square costs . Its total length is therefore
The argument in § 3.4 gives , since connecting all levels requires at least squares: each used square has three columns, each joining one pair of consecutive levels. Moreover, at most one -crossover per element can be up, since two would create a cycle, so . Together, these bounds give length at least
Equality requires and . The up -crossovers then already connect all levels, so a switch would create a cycle. The used squares therefore have all their columns up and cover each element exactly once, so their triples form a perfect matching. Conversely, choosing the squares of a perfect matching, making their columns up and all others down, gives a clean tree of length (Figure 7).
Since there are no fallbacks, the cleaning argument of § 4 no longer applies. A tree may connect only some cables at a gadget or join cables at different gadgets, and it may leave crossovers broken or miss discounts. After placing and sampling the cables, we count these deviations and show that each costs at least , while a tree with few deviations still yields a large matching.
Placing and sampling the cables
We place the gadgets far apart on a grid and route the cables along its lines, so that each cable leaves its port radially away from the gadget’s centre. For a gadget centred at , let be the closed ball of radius 20 around . The cables satisfy the following separation properties; the coordinates and proof are given in Section A.2.
Lemma 23. The cables have the following properties.
(i) The balls are pairwise more than 20 apart. Inside each , the cables consist exactly of the radial segments from the ports of to the boundary of . Any two points on different cables at distance less than 20 lie in a common ball .
(ii) Every cable segment has length at least 1; non-incident segments of the same cable are at least 1 apart, and incident segments meet at an angle of at least .
(iii) The cables can be constructed in polynomial time and have total length .
For , sample terminals along the cables as in § 4.1 to obtain . Cable recovery (Theorem 8) applies to every tree of length on , since its proof needs only (S2) and separation greater than between different cables. Here (S2) follows from Theorem 23(ii), and part (i) gives a separation of at least .
Let be an optimal tree on . Since the cables together with Steiner trees at the gadgets form a connected network of length , we have . As in § 4.3, recovery yields a tree of length at most . It consists of disjoint trees , each containing all sampled terminals on , with total length at least , and connectors joining these trees (Figure 11). Each connector has attachments on distinct cables, so with cables in total, the count (3) becomes
Following § 4.3, we distinguish good and bad connectors.
Definition 24. A connector is
(i) good at a triangle with ports if it has exactly three attachments, one within distance of the cable segment inside leaving each port;
(ii) good at a square with ports if it has exactly four attachments, one within distance of the cable segment inside leaving each port;
(iii) bad otherwise.
A bad connector may join only some of the cables at a gadget, for example those at two corners of a triangle, or connect cables at different gadgets. The following analogue of Theorem 13 shows that, up to errors, a good connector has length at least the Steiner optimum on its gadget’s ports, while a bad connector costs more per joined pair of cables.
Lemma 25. Let be a connector with attachments.
(i) If is good at a triangle of side , then .
(ii) If is good at a square, then .
(iii) If is bad, then .
Proof. Let be the attachments of . Choose the points and group the attachments as in the proof of Theorem 13, using the balls of Theorem 23. If there are groups, then is bad, and the same disjoint-ball argument gives
proving (iii).
If there is only one group, all points lie in a single ball . Projecting onto the triangle or square and joining the projected attachments to their ports gives a network on ports of of length at most (Figure 16). When is good, this network joins all ports, at a cost of at least for a triangle of side or for a square (Figure 15(b, Figure 15e)), proving (i) and (ii).

Figure 16. Projection onto a triangle gadget. (a) Each attachment of lies within distance of a cable point . (b) The shaded regions project to the ports, and projection does not increase the length of . The dotted segments, each of length at most , connect the projected network to the ports.
Otherwise, the network joins two ports of a triangle, at cost (Figure 15(a)), or two ports of a square, at cost (Figure 15(c)) or . Joining three ports of a square costs (Figure 15(d)). Thus each cost is at least . Subtracting and using gives (iii). □
Extending the terminology for clean trees, we call a crossover up if it has a good upper triangle connector, down if it has a good lower triangle connector, and broken if it has neither. A crossover cannot be both up and down, since the two good connectors would each join to , creating a cycle.
The upper bound
Recall the threshold from (5),
Lemma 26. If , then .
Proof. Let be a perfect matching, and construct the clean tree using the squares of its triples, with all crossovers in their columns up and all remaining crossovers down (Figure 7). It contains because it includes the edges between consecutive terminals on every cable, and it has length because and . It is connected because each level is connected and the up -crossover for each element joins levels and .
The lower bound
If had the connectors of a clean tree and no broken crossovers, the argument of § 7.1 would apply. In general, we count the following deviations:
, the number of broken crossovers;
, summed over all bad connectors , the number of connections made by bad connectors;
, the number of missing discounts, where is the number of up -crossovers.
Let be the total deviation. If , then has the connectors of a clean tree with all discounts, so its used squares give a perfect matching by § 7.1. We will show that , so each deviation adds length, and that , so few deviations still give a large matching.
For each element , let be the number of up -crossovers in the columns of , so . In a clean tree with no broken crossovers, by (P3) in § 3.4, but broken crossovers can split a level and allow more than one discount for the same element. The next lemma bounds the number of extra discounts in terms of .
Lemma 27. . In particular, .
Proof. Let be the number of broken crossovers on level . Along each level, the good connectors join its cables into subtrees, with a break at each broken crossover. Thus there are subtrees on level and on level . Each of the up -crossovers of element lies on level and links a subtree there to one on level (Figure 17). These links cannot form a cycle, so their number is at most one less than the total number of subtrees, giving . Hence . Summing over counts each at most twice and proves the first statement. The second follows from .

Figure 17. Figure 17: Theorem 27: four up -crossovers of element (circled) link level to the cables of level above them. The good connectors of the crossovers that are not broken chain the cables along each level into subtrees (one colour per subtree). Here and , and the four links join the five subtrees into a tree, so a fifth link would close a cycle.
Lemma 28. There is an absolute constant such that .
Proof. Let be the number of good square connectors. In (6), each good triangle connector contributes 2, each good square connector contributes 3, and the bad connectors contribute in total. There are good triangle connectors, so , giving
The cable trees have total length at least . Summing the bounds of Theorem 25 over the connectors and using gives
Each connector contributes an error of at most , so the total error is at most , since every cable has length at least 1. Recall that . By (7), . Also, Theorem 27 gives : this is immediate if , and otherwise follows from . We obtain
Absorbing the error terms into proves the claim.
To obtain a matching from , call a column good if all of its crossovers are up and its square has a good connector. In a clean tree with no broken crossovers and all discounts, the columns with an up -crossover are exactly the good ones, and the triples of their squares form a perfect matching, as in § 7.1. In general, each deviation affects only a few columns, so few deviations still leave a nearly perfect matching.
Lemma 29. .
Proof. We first show that at most of the columns with an up -crossover are not good. Consider a column with an up -crossover that is not good. If a crossover is not up, the first such crossover is either broken (Figure 18(b)) or down. In the latter case, an up crossover lies directly above a down one, so the cable between them needs a bad connector (Figure 18(c)). If all crossovers are up, the square has no good connector, so the bottom cable needs a bad connector. Broken crossovers occur in at most columns, and each cable below a crossover belongs to just one column. Since a bad connector attaches to at most cables, at most columns have such an attachment. Hence at most of these columns are not good. Hence there are at least good columns. Each of them belongs to the square of one of the good square connectors. If of these squares have three good columns, then the others have at most two, so there are at most good columns. Hence

Figure 18. Columns with an up -crossover (circled). (a) A good column. If a column is not good, it has a broken crossover (b) or a cable requiring a bad connector. In (c), a down crossover lies directly below an up one, so a bad connector must attach to the cable between them.
The triples of these squares almost form a matching. If such a triple contains an element , then its square has a column of , and this column is good, so its -crossover is up. Several of these triples may share an element , but at most of them contain . For every element that lies in several of them, we discard all but one, which discards at most triples by Theorem 27. The remaining triples are disjoint, and hence
The gap
Lemma 30. There are constants and such that, given an instance of DM-3, one can compute in polynomial time a set of terminals and a threshold satisfying
Proof of Theorem 22. Construct the cables of Theorem 23, with . Let be the constant in Theorem 28, fix
so that , and set and .
The first implication is Theorem 26. For the second, let be an optimal tree on and . Then
Moreover, , and , so .
Proof of Theorem 3 for . Replace Theorem 21 by Theorem 22 and by in the proof for .
Discussion and open problems
Lower bounds after the claimed ETH refutations. Our lower bounds in fixed dimension are nearly tight under weak ETH; under Gap-ETH, they would have matched the known dependence on accuracy. It remains open whether Gap-ETH can be replaced by another hypothesis compatible with the claimed ETH refutations, under which no -approximation algorithm runs in time for any fixed .
If the claimed ETH refutations [34, 13] are correct, many optimality questions previously settled under ETH or Gap-ETH become open again. How many of these lower bounds can be recovered, exactly or nearly, under weaker hypotheses? This question also applies to the Gap-ETH bounds for Euclidean TSP and Rectilinear Steiner Tree of Kisfaludi-Bak, Nederlof, and Węgrzycki [32]. Whether weak ETH is a reasonable hypothesis is itself open to debate within the TCS community.
Even if Gap-ETH fails, our reduction suggests that improving the running time of the known PTAS would require highly nontrivial techniques: such a speedup would also give a faster gap-3SAT algorithm, and the claimed ETH refutations rely on sophisticated algebraic tensor methods. These ideas might nevertheless lead to faster geometric approximation schemes, which would be surprising, though so were the claimed refutations of ETH themselves.
The dimension threshold for a PTAS. Under , Theorem 2 excludes a PTAS in dimensions, while Arora’s scheme [4] gives one in up to dimensions. Can this gap in the dimension threshold be closed? The same gap remains for Euclidean TSP: padding Trevisan’s APX-hardness reduction [40] excludes a PTAS in dimensions under the same hypothesis, and Arora’s scheme gives a PTAS in up to dimensions.
AI methodology
We developed the original proof in linear dimension and asked Astra 6 to extend it to logarithmic dimension, initially envisaging a more ad hoc construction. The model worked out proof details and identified the dimension-reduction argument of Karthik C. S. [41]. We subsequently suggested adapting the construction to fixed lower dimensions under Gap-ETH, and it found the connection to the cube-wiring theorem of de Berg, Bodlaender, Kisfaludi-Bak, Marx, and van der Zanden [19]. It also generated a first version of the planar argument, which we then fully rewrote for clarity and simplified using the machinery of the rest of the paper.
We used Astra 6 and Opus 5.5 for literature search, for creating the TikZ figures, for assistance with language formulations, and for working out details based on our insights and general proof strategies. The author verified the correctness and originality of all content, including references.
Omitted proofs
Cable separation in fixed dimension
Proof of Theorem 19. The construction preserves the tree structure of each , so is a tree containing exactly the ports labelled . Each replacement path stays within distance 25 of its original grid segment. Since grid segments with no common endpoint are at least 100 apart, their replacement paths remain at least 50 apart. Grid segments from different trees can share an endpoint only at a gadget centre , as the trees share only gadget vertices.
On the path replacing , every point has the form with . By the port assignment, directions used by different labels are orthogonal or opposite, so points on different such paths satisfy and hence
. The balls are clearly more than 20 apart, and each contains exactly the straight segments from its gadget’s ports to its boundary. If two points on different cables are less than 20 apart, their original grid segments must share a gadget centre , and (8) places both points in .
. All segments have length at least 24, and incident segments meet at angles of or . Segments of one cable arising from grid segments with no common endpoint are at least 50 apart. The double subdivisions ensure that modified grid segments of one cable never share an endpoint, so every remaining non-incident pair lies within a detour of (ii) or between that detour and the next untouched grid segment. In either case, the detour coordinates give a distance of at least 25. ∎
Cable separation in the plane
We specify coordinates for the layout in § 7 and verify Theorem 23. The routing is defined as follows (Figure 19).

Figure 19. Cable routing at (a) a crossover and (b) a square . Cables leave triangle ports radially, with the left and right branches ending at the junctions, and square ports along the diagonals. Inside the dotted balls , the cables consist exactly of these radial segments.
Place level on . For each triple , place its three columns on , , and , and centre at with its diagonals parallel to the coordinate axes.
At a crossover , centre the upper triangle at with a corner pointing up, and the lower triangle at with a corner pointing down. Join the left corners of both triangles to , and the right corners to .
Along a column of element at , join consecutive crossovers by their facing ports. Connect the top port of its highest crossover to on level , and the bottom port of its lowest crossover to the nearest port of its square, with a bend at for either outer column.
Along level , join successive junctions and endpoints of columns for element by horizontal segments, omitting the interval between the two junctions of a crossover. Extend level 0 leftwards to .
Route the backbone from to and then along as far as the last square; connect the bottom port of each square vertically to the backbone.
Proof of Theorem 23. (i) Distinct gadget centres are at least 80 apart, so the balls are more than 20 apart. Inside each , the construction gives exactly the radial segments from the gadget’s ports to the boundary, and any two points on different cables less than 20 apart lie on radial segments of a common gadget. These segments make angles of at least , so points at distances from the centre are at least apart; a distance of less than 20 therefore forces both points into . (ii) The grid spacing ensures that every segment has length at least 60 and that non-incident segments of one cable are at least 60 apart. At junctions, incident segments meet at or , while all other incident angles are .
(iii) The total length of the levels and columns is , with the remaining segments contributing . Since and , we obtain , and the explicit coordinates allow the cables to be computed in polynomial time.
The matching gap lemma
Proof of Theorem 4. Petrank [35], building on Kann’s reduction [30], gave a linear-size reduction from bounded-occurrence 3SAT to 3DM-3 that preserves a constant gap. Satisfiable formulas yield perfect matchings, so the PCP theorem gives NP-hardness with perfect completeness.
For (i), Gap-ETH rules out time for bounded-occurrence gap-3SAT on instances of size [32 Corollary 6.1, full version]. Since Petrank’s reduction gives , a -time algorithm for the matching gap would solve these source instances in time .
For (ii), Dinur’s nearly linear PCP [20], followed by Petrank’s reduction, maps a 3SAT formula of size to a matching gap instance with . For any fixed , a -time algorithm would therefore decide 3SAT in time . Here the polylogarithmic factor is absorbed into , and , contradicting weak ETH.
For (iii), the PCP theorem followed by Petrank’s reduction gives for a constant . Under NP SUBEXP, 3SAT has no -time algorithm for some . Taking , a -time algorithm would decide 3SAT in time , contradicting this bound.
References
- [1]Ernst Althaus, Felix Rauterberg, and Sarah Ziegler. Computing Euclidean Steiner trees over segments. EURO Journal on Computational Optimization, 8(3):309–325, 2020. doi:10.1007/s13675-020-00125-w.DOI
- [2]Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. In FOCS, pages 2–11. IEEE Computer Society, 1996. doi:10.1109/SFCS.1996.548458.
- [3]Sanjeev Arora. Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. In FOCS, pages 554–563. IEEE Computer Society, 1997. doi:10.1109/SFCS.1997.646145.
- [4]Sanjeev Arora. Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM, 45(5):753–782, 1998. doi:10.1145/290179.290180.DOI
- [5]Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In SoCG, volume 34 of LIPIcs, pages 754–767. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. doi:10.4230/LIPIcs.SOCG.2015.754.DOI
- [6]Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme. SIAM J. Comput., 45(4):1563–1581, 2016. doi:10.1137/130913328.DOI
- [7]Simon Bartlmae, Paul J. Jünger, and Elmar Langetepe. NP-hardness and a PTAS for the Euclidean Steiner Line Problem. In WAOA, 2026. To appear. doi:10.48550/arXiv.2412.07046.DOI
- [8]Marshall W. Bern and Paul E. Plassmann. The Steiner Problem with Edge Lengths 1 and 2. Inf. Process. Lett., 32(4):171–176, 1989. doi:10.1016/0020-0190(89)90039-2.DOI
- [9]Marcus Brazil, Ronald L. Graham, Doreen A. Thomas, and Martin Zachariasen. On the history of the Euclidean Steiner tree problem. Arch. Hist. Exact Sci., 68(3):327–354, 2014. doi:10.1007/s00407-013-0127-z.DOI
- [10]Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM, 60(1):6:1–6:33, 2013. doi:10.1145/2432622.2432628.DOI
- [11]T.-H. Hubert Chan, Shuguang Hu, and Shaofeng H.-C. Jiang. A PTAS for the Steiner Forest Problem in Doubling Metrics. SIAM J. Comput., 47(4):1705–1734, 2018. doi:10.1137/16M1107206.
- [12]Miroslav Chlebík and Janka Chlebíková. The Steiner tree problem on graphs: Inapproximability results. Theor. Comput. Sci., 406(3):207–214, 2008. doi:10.1016/j.tcs.2008.06.046.DOI
- [13]Claude. A 2^(n) Time Algorithm for 3-SAT, 2026. Preprint, Anthropic, October 26.
- [14]Vincent Cohen-Addad and Karthik C. S. Inapproximability of Clustering in Lp Metrics. In FOCS, pages 519–539. IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00040.
- [15]Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee. Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in ℓp-metrics. In SODA, pages 1493–1530. SIAM, 2022. doi:10.1137/1.9781611977073.63.
- [16]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP. In FOCS, pages 450–461. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00050.DOI
- [17]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP. SIAM J. Comput., 52(3):740–760, 2023. doi:10.1137/22M1469122.DOI
- [18]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs, 2018. Full version of [19]. arXiv:1803.10633, doi:10.48550/arXiv.1803.10633.DOI
- [19]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs. SIAM J. Comput., 49(6):1291–1331, 2020. doi:10.1137/20M1320870.DOI
- [20]Irit Dinur. The PCP Theorem by Gap Amplification. J. ACM, 54(3):12, 2007. doi:10.1145/1236457.1236459.DOI
- [21]Lars Engebretsen, Piotr Indyk, and Ryan O’Donnell. Derandomized dimensionality reduction with applications. In SODA, pages 705–712. ACM/SIAM, 2002.
- [22]Henry L. Fleischmann, Surya Teja Gavva, and Karthik C. S. On Approximability of Steiner Tree in ℓp-metrics. In SODA, pages 1669–1703. SIAM, 2024. doi:10.1137/1.9781611977912.67.DOI
- [23]Henry L. Fleischmann, Surya Teja Gavva, and Karthik C. S. On Approximability of Steiner Tree in ℓp-metrics. TheoretiCS, 4, 2025. doi:10.46298/theoretics.25.4.DOI
- [24]Henry L. Fleischmann, Guillermo Gamboa Quintero, Karthik C. S., Josef Matějka, and Jakub Petr. On Steiner Trees of the regular simplex. J. Comput. Geom., 16(1):1–34, 2025. doi:10.20382/jocg.v16i1a1.
- [25]M. R. Garey, R. L. Graham, and D. S. Johnson. The Complexity of Computing Steiner Minimal Trees. SIAM J. Appl. Math., 32(4):835–859, 1977. doi:10.1137/0132072.DOI
- [26]M. R. Garey, Ronald L. Graham, and David S. Johnson. Some NP-Complete Geometric Problems. In STOC, pages 10–22. ACM, 1976. doi:10.1145/800113.803626.DOI
- [27]E. N. Gilbert and H. O. Pollak. Steiner Minimal Trees. SIAM J. Appl. Math., 16(1):1–29, 1968. doi:10.1137/0116001.DOI
- [28]Vojtěch Jarník and Miloš Kössler. O minimálních grafech, obsahujících n daných bodů. Časopis pro pěstování matematiky a fysiky, 63(8):223–235, 1934. doi:10.21136/CPMF.1934.122548.
- [29]William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability, volume 26 of Contemp. Math., pages 189–206. Amer. Math. Soc., 1984. doi:10.1090/conm/026/737400.DOI
- [30]Viggo Kann. Maximum Bounded 3-Dimensional Matching is MAX SNP-Complete. Inf. Process. Lett., 37(1):27–35, 1991. doi:10.1016/0020-0190(91)90246-E.DOI
- [31]M. Kirszbraun. Über die zusammenziehende und Lipschitzsche Transformationen. Fund. Math., 22:77–108, 1934. doi:10.4064/fm-22-1-77-108.DOI
- [32]Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A Gap-ETH-Tight Approximation Scheme for Euclidean TSP. J. ACM, 72(6):42:1–42:48, 2025. doi:10.1145/3766548.
- [33]Joseph S. B. Mitchell. Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems. SIAM J. Comput., 28(4):1298–1309, 1999. doi:10.1137/S0097539796309764.DOI
- [34]OpenAI. The Exponential Time Hypothesis is False, 2026. Preprint, revised October 25.hub.valency.io/works/W_h8uqubsk
- [35]Erez Petrank. The Hardness of Approximation: Gap Location. Comput. Complex., 4:133–157, 1994. doi:10.1007/BF01202286.DOI
- [36]Satish Rao and Warren D. Smith. Approximating Geometrical Graphs via "Spanners" and "Banyans". In STOC, pages 540–550. ACM, 1998. doi:10.1145/276698.276688.DOI
- [37]J. Hyam Rubinstein, Doreen A. Thomas, and Nicholas C. Wormald. Steiner Trees for Terminals Constrained to Curves. SIAM J. Discret. Math., 10(1):1–17, 1997. doi:10.1137/S0895480192241190.DOI
- [38]Warren D. Smith. How To Find Steiner Minimal Trees in Euclidean d-Space. Algorithmica, 7(2&3):137–177, 1992. doi:10.1007/BF01758756.DOI
- [39]Luca Trevisan. When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). In STOC, pages 21–29. ACM, 1997. doi:10.1145/258533.258541.DOI
- [40]Luca Trevisan. When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree. SIAM J. Comput., 30(2):475–485, 2000. doi:10.1137/S0097539799352735.DOI
- [41]David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, Mohammad-Hossein Bateni, Simina Brânzei, Michael P. Brenner, Lin Chen, Ying Feng, Lance Fortnow, Gang Fu, Ziyi Guan, Zahra Hadizadeh, Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Adel Javanmard, Karthik C. S., Ken-ichi Kawarabayashi, Ravi Kumar, Silvio Lattanzi, Euiwoong Lee, Yi Li, Ioannis Panageas, Dimitris Paparas, Benjamin Przybocki, Bernardo Subercaseaux, Ola Svensson, Shayan Taherijam, Xuan Wu, Eylon Yogev, Morteza Zadimoghaddam, Samson Zhou, Yossi Matias, James Manyika, and Vahab Mirrokni. Accelerating Scientific Research with Gemini: Case Studies and Common Techniques. CoRR, abs/2602.03837, 2026. doi:10.48550/arXiv.2602.03837.DOI

