betaFeedback

WorksComputer Science

Inapproximability of Euclidean Steiner Tree

Abstract

We consider the Euclidean Steiner Tree problem of connecting nn given points in Rd\mathbb{R}^d 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 O(log⁡n)O(\log n) 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 O(log⁡n)O(\log n) dimensions. Assuming that not all problems in NP can be solved in subexponential time (NP ⊈\not\subseteq SUBEXP), we also rule out a PTAS for Euclidean Steiner Tree in O(log⁡log⁡n)O(\log\log n) dimensions. This dimension bound is tight up to a factor of O(log⁡log⁡log⁡n)O(\log\log\log n), since Arora's scheme is a PTAS in up to log⁡log⁡n/log⁡log⁡log⁡n\log\log n/\log\log\log n dimensions. In fixed dimension, Kisfaludi-Bak, Nederlof, and Węgrzycki [FOCS'21, J. ACM'25] obtained approximation schemes running in time 2Od(ε−(d−1))nlog⁡n2^{O_d(\varepsilon^{-(d-1)})}n\log n 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 2nγ2^{n^γ}-time algorithm on formulas of size nn for any constant γ<1γ<1 (a hypothesis one might call weak ETH). Under this assumption, we prove that no (1+ε)(1+\varepsilon)-approximation algorithm runs in time 2O(ε−γ(d−1))poly(n)2^{O(\varepsilon^{-γ(d-1)})} poly(n) for any such γγ.

Introduction

We consider the Euclidean Steiner Tree problem of connecting nn given points in Rd\mathbb{R}^{d} 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 n(log⁡n)Od(ε−(d−1))n(\log n)^{O_d(\varepsilon^{-(d-1)})} for every fixed dimension dd. 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 O(nlog⁡n)O(n\log n) for fixed dimension and accuracy. For Euclidean Steiner Tree, their bound is Od(2Od(ε−(d−1)log⁡(1/ε))n+nlog⁡n)O_d(2^{O_d(\varepsilon^{-(d-1)}\log(1/\varepsilon))}n+n\log n). 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 Od(2Od(ε−(d−1))nlog⁡n)O_d(2^{O_d(\varepsilon^{-(d-1)})}n\log n) 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 Rd\mathbb{R}^{d} could run in time nO(d/ε)n^{O(d/\varepsilon)}, with an exponent linear in dd. For Euclidean TSP, Trevisan [39, 40] proved APX-hardness in O(log⁡n)O(\log n) dimensions, so such a scheme is unlikely: in these dimensions, it would run in time nO(log⁡n)n^{O(\log n)} for fixed ε\varepsilon, and would thus solve NP-hard problems in quasipolynomial time [4]. Trevisan also proved APX-hardness for Rectilinear Steiner Tree in O(n)O(n) 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 ℓp\ell_p metric and its continuous counterpart in ℓ∞\ell_\infty, and reduced the continuous to the discrete problem in ℓp\ell_p 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 ⊈\not\subseteq 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 O(log⁡n)O(\log n) dimensions unless P = NP, and give conditional lower bounds showing that the exponent ε−(d−1)\varepsilon^{-(d-1)} is nearly optimal in every fixed dimension. First, we establish APX-hardness in logarithmic dimension.

Theorem 1. Euclidean Steiner Tree is APX-hard in O(log⁡n)O(\log n) 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 2no(1)2^{n^{o(1)}} in o(log⁡n/log⁡log⁡n)o(\log n/\log\log n) dimensions, so APX-hardness there would imply NP ⊆\subseteq SUBEXP. Padding the construction also rules out a PTAS in much lower dimension under NP ⊈\not\subseteq SUBEXP.

Theorem 2. Unless NP ⊆\subseteq SUBEXP, Euclidean Steiner Tree admits no PTAS in O(log⁡log⁡n)O(\log\log n) dimensions.

Theorem 2 is tight up to a factor of O(log⁡log⁡log⁡n)O(\log\log\log n) in the dimension. Arora’s scheme [4] runs in time O(n(log⁡n)O(d/ε))d−1O\left(n^{(\log n)^{O(\sqrt{d}/\varepsilon)}}\right)^{d-1}, which remains polynomial for every fixed ε\varepsilon whenever d≤log⁡log⁡n/log⁡log⁡log⁡nd \le\log\log n/\log\log\log n. In this range, dlog⁡d≤log⁡log⁡nd\log d \le\log\log n, so for sufficiently large dd the exponent of log⁡n\log n is at most 234dlog⁡d≤(log⁡n)3/42^{\frac{3}{4}d\log d} \le(\log n)^{3/4}, giving (log⁡n)(log⁡n)3/4=2(log⁡n)3/4log⁡log⁡n=no(1)(\log n)^{(\log n)^{3/4}} = 2^{(\log n)^{3/4}\log\log n} = n^{o(1)}. Thus Euclidean Steiner Tree admits a PTAS in up to log⁡log⁡n/log⁡log⁡log⁡n\log\log n/\log\log\log n dimensions, but, unless NP ⊆\subseteq SUBEXP, not in O(log⁡log⁡n)O(\log\log n) 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). 3SAT3SAT has no truly subexponential-time algorithm, that is, no algorithm running in time 2nγ2^{n^\gamma} on formulas of size nn for any constant γ<1\gamma< 1.

Theorem 3. Under weak ETH, for every fixed d≥2d \ge2 and every constant γ<1\gamma< 1, Euclidean Steiner Tree in Rd\mathbb{R}^d admits no (1+ε)(1+\varepsilon)-approximation algorithm running in time

2O(ε−γ(d−1))poly⁡(n).2^{O(\varepsilon^{-\gamma(d-1)})}\operatorname{poly}(n).

Under Gap-ETH, the same reduction would have ruled out running time 2o(ε−(d−1))poly⁡(n)2^{o(\varepsilon^{-(d-1)})}\operatorname{poly}(n) for every fixed d≥2d \ge2. 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 1/ε1/\varepsilon in the exponent can be made arbitrarily close to d−1d-1, 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 d≥3d \ge3, it rules out running times such as 22d/εpoly⁡(n)2^{2^{d}/\varepsilon}\operatorname{poly}(n), which APX-hardness in O(log⁡n)O(\log n) dimensions does not exclude, as Arora [4] observed. The restriction d≥3d \ge3 in this example is necessary: in the plane, the known scheme already runs in time 2O(1/ε)poly⁡(n)2^{O(1/\varepsilon)}\operatorname{poly}(n).

Even under NP ⊈\not\subseteq SUBEXP, the same reduction rules out running time 2ε−c(d−1)poly⁡(n)2^{\varepsilon^{-c(d-1)}}\operatorname{poly}(n) for some constant c>0c > 0 independent of dd. Thus the power of 1/ε1/\varepsilon 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 R3\mathbb{R}^{3} (Theorem 20), answering a question of Bartlmae, Jünger, and Langetepe [7] negatively for d≥3d \ge3.

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 O(log⁡n)O(\log n) 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 ⊈\not\subseteq SUBEXP.

For fixed d≥3d \ge3, 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 d≥3d \ge3, 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 ln⁡4+ε\ln4+\varepsilon [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 kk-means is APX-hard [5], and Cohen-Addad and Karthik [14], followed by Cohen-Addad, Karthik, and Lee [15], established stronger inapproximability bounds for kk-means and kk-median in ℓp\ell_p metrics.

Preliminaries

In a three-dimensional matching instance H=(U,E)H=(U,E), the element set UU is partitioned into three parts of size rr, and each triple in EE contains one element from each part. A matching consists of pairwise disjoint triples and is perfect if it has size rr. We consider 3DM3DM-33, where each element occurs in at most three triples, implying ∣E∣≤3r|E|\le3r. Write m=∣U∣+∣E∣m=|U|+|E| for the instance size and ν(H)\nu(H) 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 δ>0\delta>0, distinguishing ν(H)=r\nu(H)=r from ν(H)≤(1−δ)r\nu(H)\le(1-\delta)r is NP-hard for instances HH of 3DM3DM-33. Moreover:

(i) Under Gap-ETH, no algorithm distinguishes these cases in time 2o(r)2^{o(r)}.

(ii) Under weak ETH, no algorithm distinguishes these cases in time 2O(rγ)2^{O(r^\gamma)} for any constant γ<1\gamma<1.

(iii) Under NP ⊈\not\subseteq SUBEXP, there is a constant c>0c>0 such that no algorithm distinguishes these cases in time 22rc2^{2^{rc}}.

We may assume that every element occurs in at least one triple, since otherwise HH has no perfect matching. This gives r≤∣E∣≤3rr\le|E|\le3r and hence 4r≤m≤6r4r\le m\le6r.

Coordinates. We use irrational coordinates for convenience; rounding them to polynomial bit length preserves our bounds, since moving each of nn terminals by at most some very small ε>0\varepsilon>0 changes the optimum by at most nεn\varepsilon.

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 rr admits a perfect matching or has no matching larger than (1−δ)r(1-\delta)r.

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 HH, our goal is to construct a cable instance with minimum connection cost 43∣U∣−Δν(H)\frac{4}{3}|U|-\Delta\nu(H), where Δ=4−2−6>0\Delta=4-\sqrt{2}-\sqrt{6}>0. Equivalently, HH has a matching of size at least kk if and only if the cables can be connected at cost at most 43∣U∣−Δk\frac{4}{3}|U|-\Delta k.

This identity yields a constant hardness gap for Euclidean Cable Steiner Tree, since each missing matching triple increases the connection cost by Δ\Delta. With ∣U∣=3r|U|=3r, the minimum connection cost is 4r−Δν(H)4r-\Delta\nu(H), so

ν(H)=r⇒cost⁡=4r−Δr=(4−Δ)r,\nu(H)=r \quad\Rightarrow\quad\operatorname{cost}=4r-\Delta r=(4-\Delta)r,
ν(H)≤(1−δ)r⇒cost⁡≥4r−Δ(1−δ)r=(4−Δ)r+Δδr.\nu(H)\leq(1-\delta)r \quad\Rightarrow\quad\operatorname{cost}\geq4r-\Delta(1-\delta)r=(4-\Delta)r+\Delta\delta r.

The ratio between these bounds is the constant 1+Δδ/(4−Δ)1+\Delta\delta/(4-\Delta).

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.

Cable instance with element cables, backbone cable, and three square gadgets

Figure 2. A cable instance with r=2r=2 and the triples e1={u1,v1,w1}e_1=\{u_1,v_1,w_1\} (left), e3={u2,v1,w2}e_3=\{u_2,v_1,w_2\} (middle), and e2={u1,v2,w2}e_2=\{u_1,v_2,w_2\} (right), so ν(H)=1\nu(H)=1. 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 (4−Δ)+3⋅43=8−Δ(4-\Delta)+3\cdot\frac{4}{3}=8-\Delta.

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 {u,v,w}∈E\{u,v,w\}\in E, draw a square gadget of side 2\sqrt{2} with corners labelled 00, uu, vv, ww. For each element u∈Uu\in U, draw a fallback gadget consisting of two points at distance 4/34/3, labelled 00 and uu. We call these labelled points ports. For each label i∈U∪{0}i\in U\cup\{0\}, a single cable Γi\Gamma_i connects all ports labelled ii outside the gadgets. We call Γ0\Gamma_0 the backbone. Thus Γu\Gamma_u contains the corner labelled uu of each square gadget for a triple containing uu and the point labelled uu of its fallback gadget, while the backbone contains the port labelled 00 of every gadget.

Connection costs at the gadgets

Figure 3. Connection costs at the gadgets, with cables in grey and added connections in red. A square for a triple {u,v,w}\{u,v,w\} can join Γ0,Γu,Γv,Γw\Gamma_0,\Gamma_u,\Gamma_v,\Gamma_w, while the fallback for uu joins Γu\Gamma_u to the backbone Γ0\Gamma_0. Only the four-port Steiner tree improves on the baseline of 4/34/3 per connection, saving exactly Δ\Delta.

For the forward implication, let MM be a matching of size kk. For each triple in MM, join its three element cables to the backbone using the four-port Steiner tree in its square (Figure 3(c)), of length 2+6=4−Δ\sqrt{2}+\sqrt{6}=4-\Delta. Since the triples in MM are disjoint, this connects 3k3k element cables; join each of the remaining ∣U∣−3k|U|-3k cables to the backbone by its fallback segment, of length 4/34/3. The resulting network is connected and has total cost (4−Δ)k+43(∣U∣−3k)=43∣U∣−Δk(4-\Delta)k+\frac{4}{3}(|U|-3k)=\frac{4}{3}|U|-\Delta k.

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 ss, let zsz_s be its centre and BsB_s the closed ball of radius 20 around zsz_s.

Definition 6. The cables are separated if the following conditions hold.

(S1) Between cables. The balls BsB_s are pairwise more than 20 apart. Inside each ball BsB_s, the cables consist exactly of the straight segments extending from the ports of ss directly away from zsz_s to the boundary of BsB_s. 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 45∘45^\circ.

Figure 4 illustrates these conditions.

Separated cables

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 rr cables leaves at most rr 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 r−1r-1 fallback segments of total length at most 43(r−1)\frac{4}{3}(r-1) 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 BsB_s of a single gadget ss; § 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 43(r−1)\frac{4}{3}(r-1) of joining rr cables, saving Δ\Delta.

Two such trees cannot use squares sharing an element uu, since both would join Γu\Gamma_u to the backbone and create a cycle. Their triples therefore form a matching, saving at most Δν(H)\Delta\nu(H) from the fallback cost 43∣U∣\frac{4}{3}|U|. This gives a minimum connection cost of at least 43∣U∣−Δν(H)\frac{4}{3}|U|-\Delta\nu(H).

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 L=O(m)L=O(m) in O(m)O(m) dimensions, preserving a constant approximation gap.

High-dimensional routing. We work in Rm+∣U∣+3\mathbb{R}^{m+|U|+3}, assigning each gadget ss its own unit coordinate vector ese_s and each cable Γi\Gamma_i its own unit coordinate vector fif_i. We draw each gadget in a plane parallel to the b1b2b_1b_2-plane, where b1,b2b_1,b_2 are the two remaining unit coordinate vectors. For a sufficiently large constant RR, centre gadget ss at ResRe_s, with ports Res±b1Re_s\pm b_1 and Res±b2Re_s\pm b_2 for a square, or Res±12b1Re_s\pm\frac{1}{2}b_1 for a fallback. The centres of any two distinct gadgets are then at distance R2R\sqrt{2}.

The hub of Γi\Gamma_i is RfiRf_i, and each port labelled ii 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 R/2R/2 from the centre; the hub segment then joins this point to RfiRf_i. Gadgets and cables in high dimensions are hard to draw, but we try our best in Figure 5.

High-dimensional routing of gadgets and cables

Figure 5. The cable Γu\Gamma_u joins its ports at two squares and a fallback to the hub RfuRf_u, using a gadget segment followed by a hub segment for each port. Gadgets are centred at ResRe_s in planes parallel to the b1b2b_1b_2-plane, and dashed arrows mark the orthogonal directions ese_s and fuf_u.

For sufficiently large RR, the separate coordinate directions ese_s and fif_i ensure that different cables come close only near a shared gadget, giving separation. There are O(m)O(m) segments, each of constant length, so the total cable length is L=O(m)L=O(m).

From cables to point terminals. We now replace the cables by closely spaced point terminals. Connecting the points along each cable adds about LL to the cost of joining the cables. Since the routing above has L=O(m)=O(r)L=O(m)=O(r), the total cost remains O(r)O(r), so the additive gap Δδr\Delta\delta r still gives a constant approximation gap.

For a small parameter ρ>0\rho>0, sample each cable segment at spacing Θ(ρ2)\Theta(\rho^2), including its endpoints, and let PρP_\rho be the resulting set of terminals. The edges between consecutive samples have total length LL.

A short tree spanning PρP_\rho must essentially follow the cables, paying their total length LL 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 C2C_2 such that, for separated cables and every 0<ρ≤1/1000 < \rho\le1/100,

L+43∣U∣−Δν(H)−C2ρL≤OPT⁡(Pρ)≤L+43∣U∣−Δν(H).(1)L + \frac{4}{3}|U| - \Delta_\nu(H) - C_2\rho L \le\operatorname{OPT}(P_\rho) \le L + \frac{4}{3}|U| - \Delta_\nu(H). \tag*{(1)}

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 PρP_\rho of length L+43∣U∣−Δν(H)L + \frac{4}{3}|U| - \Delta_\nu(H).

For the lower bound, let TT be an optimal Steiner tree on PρP_\rho. If TT contains all edges between consecutive samples, they contribute length LL and the remaining edges connect the cables, so the cable bound applies without an error term. However, TT 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 O(ρL)O(\rho L), allowing us to apply the cable bound up to this error.

Lemma 8 (Cable recovery). Let TT be a Steiner tree on PρP_\rho of length O(L)O(L). By adding segments of total length O(ρL)O(\rho L) to TT, we obtain a network containing pairwise disjoint trees TiT_i, one for each cable Γi\Gamma_i. Each TiT_i spans the sampled terminals on Γi\Gamma_i and lies within distance ρ\rho of that cable; together, these trees have total length at least LL.

The approximation gap. Taking all edges between consecutive samples and all fallback segments shows that TT has length O(L)O(L), since every gadget contributes constant cable length and hence ∣U∣=O(L)|U| = O(L); so Theorem 8 applies.

Set τ=L+43∣U∣−Δr\tau= L + \frac{4}{3}|U| - \Delta r. Since both LL and τ\tau are O(m)=O(r)O(m) = O(r), choose constants 0<ρ≤11000 < \rho\le\frac{1}{100} and β>0\beta> 0 such that C2ρL≤Δδ2rC_2\rho L \le\frac{\Delta\delta}{2}r and βτ≤Δδ2r\beta\tau\le\frac{\Delta\delta}{2}r. If ν(H)=r\nu(H) = r, the upper bound in Theorem 7 gives OPT⁡(Pρ)≤τ\operatorname{OPT}(P_\rho) \le\tau. If ν(H)≤(1−δ)r\nu(H) \le(1-\delta)r, then

OPT⁡(Pρ)≥L+43∣U∣−Δν(H)−C2ρL\operatorname{OPT}(P_\rho) \ge L + \frac{4}{3}|U| - \Delta\nu(H) - C_2\rho L

by the lower bound in Theorem 7,

≥τ+Δδr−C2ρL\ge\tau+ \Delta\delta r - C_2\rho L

since ν(H)≤(1−δ)r\nu(H) \le(1-\delta)r,

≥τ+Δδ2r\ge\tau+ \frac{\Delta\delta}{2}r

by the choice of ρ\rho,

≥(1+β)τ\ge(1+\beta)\tau

by the choice of β\beta.

A (1+β2)(1+\frac{\beta}{2})-approximation would therefore distinguish the source cases. Since ρ\rho is constant, there are n=Θ(m)n = \Theta(m) terminals in O(m)=O(n)O(m) = O(n) dimensions, which proves APX-hardness in linear dimension.

Reducing the dimension

We reduce the dimension using the Johnson–Lindenstrauss lemma [29]. For any fixed η>0\eta> 0, the deterministic construction of Engebretsen, Indyk, and O’Donnell [21] maps the terminals P={p1,…,pn}P = \{p_1,\ldots,p_n\} in O(n)O(n) dimensions to Q={q1,…,qn}Q = \{q_1,\ldots,q_n\} in O(log⁡n)O(\log n) dimensions. After rescaling, they satisfy

∥pi−pj∥≤∥qi−qj∥≤(1+η)∥pi−pj∥for all i,j.\lVert p_i-p_j\rVert\le\lVert q_i-q_j\rVert\le(1+\eta)\lVert p_i-p_j\rVert\qquad\text{for all } i,j.

This maps the terminals, but to compare the Steiner tree optima on PP and QQ, 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 QQ then gives a network connecting PP of no greater length, while a tree on PP gives a network connecting QQ of length at most 1+η1+\eta times the original length. Applying this to optimal trees gives

OPT⁡(P)≤OPT⁡(Q)≤(1+η)OPT⁡(P).\operatorname{OPT}(P) \le\operatorname{OPT}(Q) \le(1+\eta)\operatorname{OPT}(P).

Choosing η>0\eta>0 to be a sufficiently small constant therefore preserves the constant approximation gap in O(log⁡n)O(\log n) dimensions.

No PTAS in dimension O(log⁡log⁡n)O(\log\log n). Our reduction maps a 3SAT formula with ss variables to n=sO(1)n=s^{O(1)} terminals in O(log⁡n)O(\log n) 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 N=2nγN=2^{n^\gamma} terminals for a small constant γ>0\gamma>0, the dimension is O(log⁡n)=O(log⁡log⁡N)O(\log n)=O(\log\log N), while a PTAS would decide the formula in time NO(1)=2sO(γ)N^{O(1)}=2^{s^{O(\gamma)}}. Since γ\gamma can be chosen arbitrarily small, a PTAS would imply NP⊆SUBEXP\mathrm{NP}\subseteq\mathrm{SUBEXP}, so the lower bound follows from NP⊈SUBEXP\mathrm{NP}\not\subseteq\mathrm{SUBEXP}, 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 d≥3d\ge3, we must allow the total cable length LL to grow faster than the matching instance size mm. Only the cable routing changes, so we can use the same gadgets and matching argument: YES and NO instances differ by Δδr\Delta\delta r in connection cost, and by at least Δδr/2\Delta\delta r/2 after dense sampling. Every tree on the samples also pays for the cables, so both optima are of order LL and their relative gap is Θ(m/L)\Theta(m/L), which is subconstant.

This smaller gap suffices if we can route the cables with total length

L=Od(md/(d−1)).L=O_d\left(m^{d/(d-1)}\right).

The relative gap is then Ωd(m−1/(d−1))\Omega_d(m^{-1/(d-1)}), so choosing ε=cdm−1/(d−1)\varepsilon=c_d m^{-1/(d-1)} for a sufficiently small constant cd>0c_d>0 distinguishes the YES and NO instances. This gives ε−(d−1)=Θd(m)\varepsilon^{-(d-1)}=\Theta_d(m). For any fixed 0<γ<10<\gamma<1, an approximation scheme running in time 2O(ε−γ(d−1))poly⁡(n)2^{O(\varepsilon^{-\gamma(d-1)})}\operatorname{poly}(n) would therefore solve the source matching gap in time 2O(mγ)2^{O(m^\gamma)}, 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 d≥3d\ge3, every graph with nn vertices and maximum degree at most 2d2d, the degree of the integer grid in Rd\mathbb{R}^d, can be drawn in polynomial time in the cube {0,…,S}d⊆Rd\{0,\ldots,S\}^d\subseteq\mathbb{R}^d with S=O(n1/(d−1))S=O(n^{1/(d-1)}). 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 Od(nd/(d−1))O_d(n^{d/(d-1)}).

From the grid drawing to cables. For each label ii, construct a tree TiT_i whose leaves are exactly the gadgets with a port labelled ii and whose internal vertices have degree three. The union of these trees has O(m)O(m) vertices and maximum degree four, so the cube-wiring theorem gives a grid drawing in Rd\mathbb{R}^d. We turn the drawing of each TiT_i into a cable Γi\Gamma_i by modifying the paths near each gadget to attach to its ports. The resulting cables are separated and have total length L=Od(md/(d−1)).L=O_d(m^{d/(d-1)}).

From cables to point terminals. By Theorem 7, the optimum on the sampled terminals equals L+43∣U∣−Δν(H)L + \frac{4}{3}|U| - \Delta\nu(H) up to an error of O(ρL)O(\rho L). We choose ρ=Θ(m/L)\rho= \Theta(m/L) so that this error is at most half the matching gap Δδr\Delta\delta r, and set τ=L+(4−Δ)r=Od(md/(d−1))\tau= L + (4 - \Delta)r = O_d(m^{d/(d-1)}). This gives

YES: ν(H)=r⟹OPT≤τ,NO: ν(H)≤(1−δ)r⟹OPT≥τ+Δδ2r=(1+Δδr2τ)τ.\begin{aligned} \text{YES: } \nu(H) = r &\quad\Longrightarrow\quad\mathrm{OPT} \le\tau,\\ \text{NO: } \nu(H) \le(1-\delta)r &\quad\Longrightarrow\quad\mathrm{OPT} \ge\tau+ \frac{\Delta\delta}{2}r = \left(1+\frac{\Delta\delta r}{2\tau}\right)\tau. \end{aligned}

Since r=Θ(m)r = \Theta(m), the relative gap Δδr/(2τ)\Delta\delta r/(2\tau) is Ωd(m1/(1−d))\Omega_d(m^{1/(1-d)}), so a (1+ε)(1+\varepsilon)-approximation with ε=cdm1/(1−d)\varepsilon= c_d m^{1/(1-d)} distinguishes the two cases for a sufficiently small constant cd>0c_d > 0. Sampling produces n=O(L3/m2)n = O(L^3/m^2) terminals, which is polynomial in mm. Together with ε−(d−1)=Θd(m)\varepsilon^{-(d-1)} = \Theta_d(m), 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 2o(ε−(d−1))poly⁡(n)2^{o(\varepsilon^{-(d-1)})}\operatorname{poly}(n). The weaker assumption NP⊈SUBEXP\mathrm{NP} \not\subseteq\mathrm{SUBEXP} still rules out time 2o(ε−c(d−1))poly⁡(n)2^{o(\varepsilon^{-c(d-1)})}\operatorname{poly}(n) for some constant c>0c > 0, 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 Ω(r)\Omega(r); since the total cable length is O(r2)O(r^2), this yields the relative gap Ω(1/r)\Omega(1/r) required for d=2d = 2.

Gadgets and layout. Fix ω=1/100\omega= 1/100. We use two types of gadgets: equilateral triangles of side length 11 or 1−ω1-\omega, and unit squares (Figure 6(a, b)). A crossover xx consists of an upper and a lower triangle where a horizontal and a vertical cable meet, with the cables UxU_x above, DxD_x below, and LxL_x, RxR_x 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 ℓ\ell and a unit square. (c, d) At an up crossover xx, the upper triangle joins UxU_x, LxL_x, and RxR_x; at a down crossover, the lower triangle joins DxD_x, LxL_x, and RxR_x.

The layout (Figure 7) has horizontal levels 0,…,3r0,\ldots,3r, where level 00 contains the backbone, and a square below level 00 for each triple. For each element jj of a triple, a vertical column runs from a corner of its square up to level jj, 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 j−1j-1, is an ω\omega-crossover, with an upper triangle of side 1−ω1-\omega instead of 11.

Layout for elements 1, …, 6 and three triples, with optimal connections shown in black

Figure 7. Layout for elements 1, …, 6 and three triples, with optimal connections shown in black. The perfect matching {e1,e2}\{e_1,e_2\} corresponds to the columns of e1e_1 and e2e_2 being up and those of e3e_3 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 xx, the upper triangle joins LxL_x and RxR_x to UxU_x, while the lower joins them to DxD_x (Figure 6(c, d)). Using both would join LxL_x to RxR_x twice and create a cycle. We call xx 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 3\sqrt{3} and the smaller upper triangle of an ω\omega-crossover costs 3(1−ω)\sqrt{3}(1-\omega), a saving of 3ω\sqrt{3}\omega. Since the cost at a square is 1+31+\sqrt{3}, such a tree using qq squares and having CωC_\omega up ω\omega-crossovers has length L+3C+(1+3)q−3ωCωL+\sqrt{3}C+(1+\sqrt{3})q-\sqrt{3}\omega C_\omega, where CC is the number of crossovers. We show that every such tree has length at least

τ=L+3C+(1+3)r−33ωr,\tau= L+\sqrt{3}C+(1+\sqrt{3})r-3\sqrt{3}\omega r,

with equality only when the used squares form a perfect matching.

Every crossover of such a tree joins LxL_x to RxR_x, 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)).

Columns for element 3, with four crossover configurations: all down, a switch, all up, and up above down

Figure 8. Columns for element 3, with the top ω\omega-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) ω\omega-crossovers. For each element jj, at most one ω\omega-crossover on level j−1j-1 is up. An up crossover joins levels j−1j-1 and jj by attaching the cable above it, which continues along level jj; two such crossovers would join the same levels twice and create a cycle (Figure 8(c)). Hence Cω≤3rC_\omega\le3r.

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 ω\omega-crossover. All 3r3r pairs must be joined, and each used square has three columns, so q≥rq \ge r. Together with Cω≤3rC_\omega\le3r from (P3), this gives a length of at least τ\tau, with equality requiring q=rq = r and Cω=3rC_\omega= 3r.

Optimal clean trees. Suppose such a tree has length τ\tau, so q=rq = r and Cω=3rC_\omega= 3r. Each element jj then has exactly one up ω\omega-crossover on level j−1j-1, 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 ω\omega-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 jj, their columns for jj would give two up ω\omega-crossovers on level j−1j-1, contrary to (P3); hence the corresponding triples form a (perfect) matching.

Conversely, any perfect matching gives a clean tree of length τ\tau by choosing the corresponding squares and making all crossovers in their columns up and all remaining crossovers down (Figure 7). Intuitively, the ω\omega-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 τ\tau 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 3 ω\sqrt{3}\,\omega 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 H=(U,E)H=(U,E) has three parts of size rr, total size m=∣U∣+∣E∣m=|U|+|E|, and maximum matching size ν(H)\nu(H). The construction takes place in RD\mathbb{R}^{D}, with DD 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 mm gadgets are indexed by s=1,…,ms=1,\ldots,m and have centres zs∈RDz_s\in\mathbb{R}^{D}. We use the same two orthogonal unit coordinate vectors b1,b2b_1,b_2 for every gadget and define the ports, where the cables attach, by the following coordinates and labels.

  • (a) For the square of a triple {u,v,w}\{u,v,w\}, the ports ps,0,ps,u,ps,v,ps,wp_{s,0},p_{s,u},p_{s,v},p_{s,w} are the four points zs±b1z_s\pm b_1 and zs±b2z_s\pm b_2. They form a square of side length 2\sqrt{2}.

  • (b) For the fallback of an element uu, the ports ps,0,ps,up_{s,0},p_{s,u} are the points zs±23b1z_s\pm\frac{2}{3}b_1. They are at distance 43\frac{4}{3}.

We use the elements of UU and an additional symbol 00 as labels. The shortest networks joining two, three, or four ports of a square have lengths 2\sqrt{2}, 1+31+\sqrt{3}, and 2+6=4−Δ\sqrt{2}+\sqrt{6}=4-\Delta, respectively (Figure 3). Only the four-port network costs less than 43\frac{4}{3} per joined pair.

For each label ii, we join the ports labelled ii by a tree of line segments, the cable Γi\Gamma_i, so that different cables are disjoint; we call Γ0\Gamma_0 the backbone. Let LL be the total cable length and, for each gadget ss, let BsB_s be the closed ball of radius 2020 centred at zsz_s. 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 BsB_s are pairwise more than 20 apart. Inside each ball BsB_s, the cables consist exactly of the straight segments extending from the ports of ss directly away from zsz_s to the boundary of BsB_s. 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 45∘45^\circ.

Explicitly, the segments in (S1) are (zs+b,zs+20b)(z_s+b,z_s+20b) for b∈{±b1,±b2}b\in\{\pm b_1,\pm b_2\} when ss is a square, and (zs+23b,zs+20b)(z_s+\frac{2}{3}b,z_s+20b) for b∈{±b1}b\in\{\pm b_1\} when ss is a fallback. The segments leaving distinct ports of a gadget extend in orthogonal or opposite directions and are therefore at least 43\frac{4}{3} apart. Together with (S1), this shows that points on different cables are at least 43\frac{4}{3} apart. By (S2), there are at most LL cable segments, and by (S1), ∣U∣<L|U|<L.

For 0<ρ≤1/1000<\rho\leq1/100, we form PρP_\rho by placing ⌈t/ρ2⌉+1\lceil t/\rho^2\rceil+1 equally spaced terminals along each cable segment of length tt, including both endpoints. Consecutive terminals along a segment are at distance in [ρ2/2,ρ2][\rho^2/2,\rho^2], and the edges between them have total length LL, with ∣Pρ∣=Θ(L/ρ2)|P_\rho|=\Theta(L/\rho^2).

The main result of this section shows that the optimum on PρP_\rho equals the cable length LL plus the cost of connecting the cables, up to an error of O(ρL)O(\rho L).

Theorem 7 (Cable reduction). There is an absolute constant C2C_2 such that, for separated cables and every 0<ρ≤1/1000<\rho\leq1/100,

L+43∣U∣−Δν(H)−C2ρL≤OPT⁡(Pρ)≤L+43∣U∣−Δν(H).(2)L+\frac{4}{3}|U|-\Delta_\nu(H)-C_2\rho L\leq\operatorname{OPT}(P_\rho)\leq L+\frac{4}{3}|U|-\Delta_\nu(H). \tag*{(2)}

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 qq squares, its length is

L+43(∣U∣−3q)+(4−Δ)q=L+43∣U∣−Δq.L+\frac{4}{3}(|U|-3q)+(4-\Delta)q=L+\frac{4}{3}|U|-\Delta q.

The clean network corresponding to a maximum matching contains PρP_\rho, proving the upper bound in Theorem 7. For the lower bound, we will show that every short tree on PρP_\rho has length at least that of the clean network of some matching, up to an error of O(ρL)O(\rho L).

Recovering the cables

Suppose for a moment that an optimal tree on PρP_\rho 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 C2ρLC_2\rho L. In general, a tree on PρP_\rho 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 ρ\rho of it.

For each cable segment ee, choose terminals aea_e and beb_e at distances between 10ρ10\rho and 10ρ+ρ210\rho+\rho^2 from its two endpoints, respectively. We call (ae,be)(a_e,b_e) the middle segment of ee and its two remaining parts the end pieces, each of length at most 10ρ+ρ210\rho+\rho^2. Each end piece consists of edges between consecutive terminals. We surround each middle segment by a closed cylinder of radius ρ\rho 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 2ρ2\rho. If segments e,e′e,e' share an endpoint pp, their angle is at least 45∘45^\circ by (S2), so every point on the middle segment of e′e' is at least 10ρ10\rho from pp and hence at least 10ρsin⁡45∘>7ρ10\rho\sin45^\circ> 7\rho from ee. The tube of e′e' therefore has distance greater than 6ρ6\rho from ee, so the two tubes are disjoint.

Sampling and tubes

Figure 9. Sampling and tubes. (a) A sampled cable with tubes around its middle segments. (b) The tube around a sampled segment ee. (c) Two segments meeting at pp at an angle of at least 45∘45^\circ. Every point on the middle segment of e′e' lies at least 10ρ10\rho from pp and therefore at least 10ρ/210\rho/\sqrt{2} from ee, so the tubes are disjoint.

Fix a tree TT of length O(L)O(L) spanning PρP_\rho. 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).

Connecting components inside a tube

Figure 10. Connecting components inside a tube. Black segments show T∩ZT \cap Z. The components C1,C2C_1,C_2 reach the left cap, C3C_3 the lateral boundary, and C4C_4 the right cap. Three red edges between consecutive samples connect them.

Lemma 11. Let ZZ be the tube around a middle segment and ww the length of TT inside ZZ. We can connect all sampled terminals on that segment within ZZ by adding edges between consecutive terminals, with total added length at most ρw+2ρ2+4ρw\rho w + 2\rho^2 + 4\rho\sqrt{w}.

Proof. Let kk be the number of components of T∩ZT \cap Z containing sampled terminals; see Figure 10. We can connect these kk components using k−1k-1 edges between consecutive samples, each of length at most ρ2\rho^2, for a total added length of at most ρ2(k−1)\rho^2(k-1).

If k>1k>1, each such component meets the tube boundary, since TT is connected. A component meeting the lateral boundary contains a path of length at least ρ\rho from a sample on the cable segment to the side of the tube, so there are at most w/ρw/\rho such components. Assign every other component to an end cap that it meets. For the klk_l components assigned to the left cap, choose one sampled terminal from each and order these samples from left to right. The jjth sample is at distance at least (j−1)ρ2/2(j-1)\rho^2/2 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 ww, giving

w≥∑j=1kl(j−1)ρ22=ρ2kl(kl−1)4.w \ge\sum_{j=1}^{k_l} \frac{(j-1)\rho^2}{2} = \frac{\rho^2 k_l(k_l-1)}{4}.

It follows that kl≤1+2w/ρk_l \le1 + 2\sqrt{w}/\rho. The same bound holds at the right cap. Consequently k≤w/ρ+2+4w/ρk \le w/\rho+ 2 + 4\sqrt{w}/\rho, which proves the claimed bound on the added length. If k=1k = 1, nothing needs to be added.

We now apply this bound to all tubes to prove the cable-recovery lemma.

Lemma 8 (Cable recovery). Let TT be a Steiner tree on PρP_\rho of length O(L)O(L). By adding segments of total length O(ρL)O(\rho L) to TT, we obtain a network containing pairwise disjoint trees TiT_i, one for each cable Γi\Gamma_i. Each TiT_i spans the sampled terminals on Γi\Gamma_i and lies within distance ρ\rho of that cable; together, these trees have total length at least LL.

Proof. Let nseg≤Ln_{\mathrm{seg}} \le L be the number of cable segments. For each cable segment ee, let wew_e be the length of TT inside the tube of ee. The tubes are disjoint, so ∑ewe≤len⁡(T)\sum_e w_e \le\operatorname{len}(T). By Theorem 11 and Cauchy–Schwarz, the total length added inside the tubes is at most ρlen⁡(T)+2nsegρ2+4ρnseglen⁡(T)=O(ρL)\rho\operatorname{len}(T) + 2n_{\mathrm{seg}}\rho^2 + 4\rho\sqrt{n_{\mathrm{seg}}\operatorname{len}(T)} = O(\rho L), since len⁡(T)=O(L)\operatorname{len}(T) = O(L). We also add all edges between consecutive terminals along the end pieces, with total length at most (20ρ+2ρ)nseg≤21ρL(20\rho+ 2\rho)n_{\mathrm{seg}} \le21\rho L.

After adding these edges, the samples on the middle segment of each cable segment ee are connected inside its tube. Choose a tree JeJ_e in this network spanning these samples; because it contains aea_e and beb_e, it is at least as long as the middle segment.

For each cable Γi\Gamma_i, let TiT_i be the union of the trees JeJ_e for its segments and all their end pieces. The tubes are disjoint and meet the end pieces only at aea_e and beb_e, so each TiT_i is a tree spanning the sampled terminals on Γi\Gamma_i, and the trees TiT_i are pairwise disjoint. Moreover, TiT_i lies within distance ρ\rho of Γi\Gamma_i and has length at least len⁡(Γi)\operatorname{len}(\Gamma_i), so ∑ilen⁡(Ti)≥L\sum_i \operatorname{len}(T_i) \ge L.

Connectors and cleaning

By cable recovery, we can add segments of total length O(ρL)O(\rho L) to TT to obtain a connected network containing the forest F=⋃iTiF = \bigcup_i T_i, whose length is at least LL. We choose a spanning tree T^\widehat{T} of this network containing FF and repeatedly remove leaves outside FF, which ensures that every leaf of T^\widehat{T} lies in FF.

Removing FF decomposes the rest of T^\widehat{T} into connectors: subtrees whose leaves, called attachments, lie on FF and whose other points lie outside FF (Figure 11(a)). Every connector has at least two attachments, and it cannot attach twice to the same TiT_i, since this would create a cycle in T^\widehat{T}.

Connectors and incidence tree

Figure 11. Connectors at the square ss for {u,v,w}\{u,v,w\} and the fallback of xx. (a) The recovered trees TiT_i (black) lie in cable tubes (grey), and connectors (red) attach at the dots. Connector S1S_1 is good at ss; S2S_2 is bad: its attachments on TvT_v and TxT_x lie outside the gadget balls. (b) The incidence tree of the trees TiT_i and connectors.

The bipartite graph between the trees TiT_i and the connectors, with one edge per attachment, is also a tree, which we call the incidence tree (Figure 11(b)). If rSr_S denotes the number of attachments of connector SS, this tree has ∑SrS\sum_S r_S edges and one vertex for each of the ∣U∣+1|U|+1 trees TiT_i and each connector. Since a tree has one edge fewer than vertices,

∑S(rS−1)=∣U∣.(3)\sum_S (r_S-1)=|U|. \tag*{(3)}

Connectors attach to the trees TiT_i, so their attachments lie within distance ρ\rho of the cables. An attachment is near a port pp of a gadget ss if it lies within distance ρ\rho of the cable segment from pp to the boundary of BsB_s, 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 ss of a triple {u,v,w}\{u,v,w\} if it has exactly four attachments, one near each of the ports ps,0,ps,u,ps,v,ps,wp_{s,0},p_{s,u},p_{s,v},p_{s,w};

(ii) good at the fallback ss of an element uu if it has exactly two attachments, one near each of the ports ps,0p_{s,0} and ps,up_{s,u};

(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 rS−1r_S-1 fallbacks, up to small errors.

Lemma 13. Let SS be a connector with rr attachments.

(i) If SS is good at a square, then len⁡(S)≥4−Δ−4ρ\operatorname{len}(S) \ge4-\Delta-4\rho.

(ii) If SS is good at a fallback, then len⁡(S)≥43−2ρ\operatorname{len}(S) \ge\frac{4}{3}-2\rho.

(iii) If SS is bad, then len⁡(S)≥(43−2ρ)(r−1)\operatorname{len}(S) \ge\left(\frac{4}{3}-2\rho\right)(r-1).

Proof. Let x1,…,xrx_1,\ldots,x_r be the attachments of SS. They lie within distance ρ\rho of distinct cables, so for each jj we can choose a point xˉj\bar{x}_j on the corresponding cable with ∥xj−xˉj∥≤ρ\lVert x_j-\bar{x}_j\rVert\le\rho, and if SS is good at a gadget ss, we choose it inside BsB_s. We group the attachments according to where these points lie: xjx_j and xkx_k are in the same group if xˉj\bar{x}_j and xˉk\bar{x}_k lie in a common ball BsB_s, and xjx_j forms a group on its own if xˉj\bar{x}_j lies in no ball. By (S1), attachments in different groups are at distance at least 20−2ρ>1820-2\rho>18, and since a ball meets at most four cables, every group has at most four attachments.

If there are g≥2g\ge2 groups, then SS is bad, since a good connector has all its attachments near a single gadget. The balls of radius 99 around one attachment from each group are disjoint, and since SS is connected and has points outside each of them, it runs from the centre of each ball to its boundary. Hence

len⁡(S)≥9g≥43(4g−1)≥43(r−1).\operatorname{len}(S)\ge9g\ge\frac{4}{3}(4g-1)\ge\frac{4}{3}(r-1).

which gives (iii).

Otherwise, all points xˉj\bar{x}_j lie in the ball BsB_s of one gadget ss. We project SS onto the square or fallback segment of ss to obtain a network S′S' of no greater length (Figure 12). The projection sends xˉj\bar{x}_j to its port pjp_j and does not increase distances, so the projected attachment xj′∈S′x'_j\in S' lies within distance ρ\rho of pjp_j. We then add the segments (xj′,pj)(x'_j,p_j) to obtain a network connecting rr ports of ss, of length at most len⁡(S)+rρ\operatorname{len}(S)+r\rho.

Projection onto a square gadget, for three cables

Figure 12. Projection onto a square gadget, for three cables. The shaded regions project to the corners, so each cable point xˉj\bar{x}_j projects to its port pjp_j, and xjx_j to xj′x'_j. The projected network S′S' is no longer than SS, and the dotted segments, each of length at most ρ\rho, join it to the ports.

If SS is good, we have connected all ports, at a cost of at least 4−Δ4-\Delta for a square or 43\frac{4}{3} for a fallback, proving (i) and (ii). If SS is bad, the network connects two or three ports of a square, requiring at least 2\sqrt{2} or 1+31+\sqrt{3}, respectively (Figure 3). In either case, this is at least 43(r−1)\frac{4}{3}(r-1), so

len⁡(S)≥43(r−1)−rρ≥(43−2ρ)(r−1),\operatorname{len}(S)\ge\frac{4}{3}(r-1)-r\rho\ge\left(\frac{4}{3}-2\rho\right)(r-1),

where the last inequality uses r≤2(r−1)r\le2(r-1), proving (iii). □\square

We prove that for every short tree TT on PρP_\rho, there is a clean network of length at most len⁡(T)+O(ρL)\operatorname{len}(T)+O(\rho L) by showing that the triples of the good square connectors form a matching whose clean network satisfies this bound.

Lemma 14. For every tree TT on PρP_\rho with len⁡(T)≤73L\operatorname{len}(T) \le\frac{7}{3}L, there is a clean network of length at most len⁡(T)+C2ρL\operatorname{len}(T) + C_2\rho L, where C2C_2 is an absolute constant.

Proof. Let qq be the number of good square connectors. If two of their triples shared an element uu, both connectors would attach to TuT_u and T0T_0, creating a cycle in the incidence tree. Their triples therefore form a matching, whose clean network has length L+43∣U∣−ΔqL + \frac{4}{3}|U| - \Delta q, which we will now compare with the length of TT.

By Theorem 13, each good square connector has rS−1=3r_S - 1 = 3 and length at least

4−Δ−4ρ≥(43−2ρ)(rS−1)−Δ,4 - \Delta- 4\rho\ge\left(\frac{4}{3} - 2\rho\right)(r_S - 1) - \Delta,

while every other connector has length at least (43−2ρ)(rS−1)\left(\frac{4}{3} - 2\rho\right)(r_S - 1). Summing over the connectors and using (3) gives

∑Slen⁡(S)≥(43−2ρ)∣U∣−Δq.\sum_S \operatorname{len}(S) \ge\left(\frac{4}{3} - 2\rho\right)|U| - \Delta q.

The tree T^\widehat{T} consists precisely of these connectors and the forest FF, which has length at least LL. Since we obtained T^\widehat{T} from TT by adding length O(ρL)O(\rho L) and then removing edges,

len⁡(T)+O(ρL)≥len⁡(T^)≥L+43∣U∣−Δq−2ρ∣U∣.\operatorname{len}(T) + O(\rho L) \ge\operatorname{len}(\widehat{T}) \ge L + \frac{4}{3}|U| - \Delta q - 2\rho|U|.

Thus the clean network of this matching has length at most len⁡(T)+O(ρL)+2ρ∣U∣\operatorname{len}(T) + O(\rho L) + 2\rho|U|. Since ∣U∣<L|U| < L, this is at most len⁡(T)+C2ρL\operatorname{len}(T) + C_2\rho L for an absolute constant C2C_2. □

Proof of the lower bound in Theorem 7. Let TT be an optimal tree on PρP_\rho. The clean network using only fallbacks gives len⁡(T)≤L+43∣U∣≤73L\operatorname{len}(T) \le L + \frac{4}{3}|U| \le\frac{7}{3}L, since ∣U∣<L|U| < L. We can therefore apply Theorem 14 to obtain a clean network of length at most OPT⁡(Pρ)+C2ρL\operatorname{OPT}(P_\rho) + C_2\rho L. Its qq squares form a matching, so q≤ν(H)q \le\nu(H) and its length is at least L+43∣U∣−Δν(H)L + \frac{4}{3}|U| - \Delta\nu(H). 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 O(log⁡n)O(\log n).

Orthogonal routing in linear dimension

By Theorem 7, it suffices to construct a separated cable routing of total length O(m)O(m). 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 b1b_1, b2b_2 in which the gadgets are drawn, reserve a unit coordinate vector ese_s for each gadget ss and fif_i for each label i∈U∪{0}i \in U \cup\{0\}, all mutually orthogonal; this uses D=m+∣U∣+3D = m + |U| + 3 dimensions. Set R=64R = 64. We place each gadget ss at zs=Resz_s = R e_s, and let the hub of Γi\Gamma_i be RfiR f_i. Each port labelled ii has the form ps,i=Res+αvp_{s,i} = R e_s + \alpha v, where v∈{±b1,±b2}v \in\{\pm b_1, \pm b_2\} and α=1\alpha= 1 for a square or α=2/3\alpha= 2/3 for a fallback. The cable has a gadget segment from this port in direction vv up to the bend Res+R2vR e_s + \frac{R}{2}v, followed by a hub segment from the bend straight to the hub, which together form the branch

Res+αv⟶Res+R2v⟶Rfi.R e_s + \alpha v \longrightarrow R e_s + \frac{R}{2}v \longrightarrow R f_i.

The cable Γi\Gamma_i is the union of these branches over all ports labelled ii; we call this the orthogonal routing (Figure 5).

Lemma 15. The cables of the orthogonal routing are separated and have total length L=O(m)L=O(m).

Proof. We first establish two distance bounds, illustrated in Figure 13.

Orthogonal routing near gadgets s and s′

Figure 13. Orthogonal routing near gadgets ss and s′s'. (a) Gadget segments lie within distance R/2R/2 of their centre (dashed), keeping segments of distinct gadgets more than 20 apart. (b) Hub segments are at distance at least R/3>20R/3>20 from every other cable. The cables inside BsB_s (dotted) therefore consist exactly of the gadget segments of ss.

(a) The gadget segments of ss extend radially away from zsz_s in the directions ±b1,±b2\pm b_1,\pm b_2 and end at distance R/2R/2 from it. Since gadget centres are R2R\sqrt{2} apart, segments from distinct gadgets are at least R2−R>20R\sqrt{2}-R>20 apart.

(b) Every hub segment is at distance at least R/3>20R/3>20 from every other cable. To see this, write a point on the hub segment from gadget ss to RfiR f_i as

x=(1−t)(Res+R2v)+tRfi,0≤t≤1.x=(1-t)\left(R e_s+\frac{R}{2}v\right)+tR f_i,\qquad0\le t\le1.

Its ese_s-, fif_i- and vv-coordinates are (1−t)R(1-t)R, tRtR and (1−t)R/2(1-t)R/2. A point yy on another cable has zero fif_i-coordinate. If it does not lie on a branch from ss, its ese_s-coordinate is also zero, so

∥x−y∥≥∥((1−t)R,tR)∥≥R/2.\lVert x-y\rVert\ge\lVert((1-t)R,tR)\rVert\ge R/\sqrt{2}.

Otherwise, the branches containing xx and yy share the same gadget ss. Since they belong to different cables, they use different ports of ss, so the branch containing yy leaves in a direction orthogonal or opposite to vv and has nonpositive vv-coordinate. The fif_i- and vv-coordinates then give

∥x−y∥≥max⁡{tR,(1−t)R2}≥R/3.\lVert x-y\rVert\ge\max\left\{tR,(1-t)\frac{R}{2}\right\}\ge R/3.

(S1) Since the centres are R2>60R\sqrt{2}>60 apart, the balls BsB_s are more than 20 apart. No hub segment enters any of these balls: the coordinates in (b) give distance at least R/3>20R/3>20 from the centre of its gadget and at least RR from every other centre. By (a), gadget segments from other gadgets also stay outside BsB_s. Thus inside BsB_s, the cables are exactly the straight segments from the ports of ss 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 R/2−α≥31R/2-\alpha\ge31, 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 ss has ese_s-coordinate RR, whereas all other branches of its cable have ese_s-coordinate zero, giving distance at least RR between them. Every pair of non-incident segments contains such a gadget segment, so their distance is at least RR. The angles φ\varphi at bends and φ′\varphi' at hubs satisfy

cos⁡φ=3296,cos⁡φ′=322⟨v,v′⟩+642962≤59.\cos\varphi=\frac{32}{96},\qquad\cos\varphi'=\frac{32^{2}\langle v,v'\rangle+64^{2}}{96^{2}}\le\frac{5}{9}.

so both are at least 45∘45^\circ.

Finally, each of the 4∣E∣+2∣U∣4|E|+2|U| branches has length less than 128, giving total cable length L=O(m)L=O(m).

Lemma 16. There are constants β>0\beta>0 and ρ>0\rho>0 such that the following holds. Given an instance HH of 3DM-3, one can construct in polynomial time n=Θ(m)n=\Theta(m) terminals Pρ⊆RO(n)P_\rho\subseteq\mathbb{R}^{O(n)} and a threshold τ\tau with

ν(H)=r ⟹ OPT⁡(Pρ)≤τ,ν(H)≤(1−δ)r ⟹ OPT⁡(Pρ)≥(1+β)τ.\nu(H)=r\ \Longrightarrow\ \operatorname{OPT}(P_\rho)\le\tau,\qquad\nu(H)\le(1-\delta)r\ \Longrightarrow\ \operatorname{OPT}(P_\rho)\ge(1+\beta)\tau.

Consequently, Euclidean Steiner Tree is APX-hard already in O(n)O(n) dimensions.

Proof. Construct the cables of the orthogonal routing. By Theorem 15, they are separated and L≤C1mL\le C_1m for a constant C1C_1. Fix a constant

ρ≤min⁡{1100,Δδ12C1C2}.\rho\le\min\left\{\frac{1}{100},\frac{\Delta\delta}{12C_1C_2}\right\}.

where C2C_2 is the constant in Theorem 7, and set τ=L+43∣U∣−Δr\tau=L+\frac{4}{3}|U|-\Delta r.

The first implication is the upper bound in Theorem 7. For the second, let β=Δδ2(6C1+4)\beta=\frac{\Delta\delta}{2(6C_1+4)}. Then

OPT⁡(Pρ)≥L+43∣U∣−Δν(H)−C2ρL\operatorname{OPT}(P_\rho)\ge L+\frac{4}{3}|U|-\Delta\nu(H)-C_2\rho L

by the lower bound in Theorem 7,

≥L+43∣U∣−Δr+Δδr−C2ρL\ge L+\frac{4}{3}|U|-\Delta r+\Delta\delta r-C_2\rho L

since ν(H)≤(1−δ)r\nu(H)\le(1-\delta)r,

=τ+Δδr−C2ρL=\tau+\Delta\delta r-C_2\rho L

by the definition of τ\tau,

≥τ+Δδ2r\ge\tau+\frac{\Delta\delta}{2}r

since L≤C1m≤6C1rL\le C_1m\le6C_1r and ρ≤Δδ12C1C2\rho\le\frac{\Delta\delta}{12C_1C_2},

=τ+β(6C1+4)r=\tau+\beta(6C_1+4)r

by the definition of β\beta,

≥(1+β)τ\ge(1+\beta)\tau

since τ≤L+43∣U∣≤(6C1+4)r\tau\le L+\frac{4}{3}|U|\le(6C_1+4)r.

Since ρ\rho is constant, n=Θ(L/ρ2)=Θ(m)n=\Theta(L/\rho^2)=\Theta(m) and D=m+∣U∣+3=O(n)D=m+|U|+3=O(n).

Reducing to logarithmic dimension

Writing β\beta for the gap constant in Theorem 16, we now reduce the dimension of the terminal set Pρ={p1,…,pn}P_\rho= \{p_1,\ldots,p_n\} constructed there, making no further use of the cables.

The Johnson–Lindenstrauss lemma [29] states that, for every 0<η<10 < \eta< 1, any nn points in a Euclidean space can be mapped into O(η−2log⁡n)O(\eta^{-2}\log n) dimensions so that, after rescaling, every pairwise distance changes by a factor between 11 and 1+η1+\eta. Using the deterministic construction of Engebretsen, Indyk, and O’Donnell [21], we obtain in polynomial time points q1,…,qn∈Rkq_1,\ldots,q_n \in\mathbb{R}^k, k=O(β−2log⁡n)=O(log⁡n)k = O(\beta^{-2}\log n) = O(\log n), with

∥pi−pj∥≤∥qi−qj∥≤(1+β2)∥pi−pj∥for all i,j.(4)\lVert p_i-p_j\rVert\le\lVert q_i-q_j\rVert\le\left(1+\frac{\beta}{2}\right)\lVert p_i-p_j\rVert\qquad\text{for all }i,j. \tag*{(4)}

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⊆RDA \subseteq\mathbb{R}^{D}, a map f:A→RD′f:A\to\mathbb{R}^{D'} is λ\lambda-Lipschitz if ∥f(x)−f(y)∥≤λ∥x−y∥\lVert f(x)-f(y)\rVert\le\lambda\lVert x-y\rVert for all x,y∈Ax,y\in A. By Kirszbraun’s theorem, ff extends to a λ\lambda-Lipschitz map F:RD→RD′F:\mathbb{R}^{D}\to\mathbb{R}^{D'}, that is,

F(a)=f(a)for all a∈A,∥F(x)−F(y)∥≤λ∥x−y∥for all x,y∈RD.F(a)=f(a)\quad\text{for all }a\in A,\qquad\lVert F(x)-F(y)\rVert\le\lambda\lVert x-y\rVert\quad\text{for all }x,y\in\mathbb{R}^{D}.

In particular, if ff maps a set AA of terminals to a lower-dimensional space and stretches distances between terminals by a factor of at most λ\lambda, then the extension FF 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 FF to the vertices of a tree and joining the mapped vertices by straight segments therefore yields a connected network whose length is at most λ\lambda times that of the original tree.

Lemma 17. Let P={p1,…,pn}P=\{p_1,\ldots,p_n\} and Q={q1,…,qn}Q=\{q_1,\ldots,q_n\} be finite point sets in Euclidean spaces of possibly different dimensions. If, for some λ≥1\lambda\ge1, their pairwise distances satisfy ∥pi−pj∥≤∥qi−qj∥≤λ∥pi−pj∥\lVert p_i-p_j\rVert\le\lVert q_i-q_j\rVert\le\lambda\lVert p_i-p_j\rVert for all i,ji,j, then

OPT⁡(P)≤OPT⁡(Q)≤λOPT⁡(P).\operatorname{OPT}(P)\le\operatorname{OPT}(Q)\le\lambda\operatorname{OPT}(P).

Proof. We prove the two inequalities by applying Kirszbraun’s theorem in opposite directions. First, the map qi↦piq_i\mapsto p_i is 11-Lipschitz by the left-hand inequality. Extending this map to the Steiner points of an optimal tree on QQ gives a network on PP of length at most OPT⁡(Q)\operatorname{OPT}(Q), so OPT⁡(P)≤OPT⁡(Q)\operatorname{OPT}(P)\le\operatorname{OPT}(Q). Conversely, the map pi↦qip_i\mapsto q_i is λ\lambda-Lipschitz by the right-hand inequality. Extending this map to the Steiner points of an optimal tree on PP gives a network on QQ of length at most λOPT⁡(P)\lambda\operatorname{OPT}(P), so OPT⁡(Q)≤λOPT⁡(P)\operatorname{OPT}(Q)\le\lambda\operatorname{OPT}(P).

Proof of Theorem 1. Apply Theorem 16 to obtain PρP_\rho and τ\tau, and construct QQ as above in O(log⁡n)O(\log n) dimensions. Combining (4) with Theorem 17 for λ=1+β/2\lambda=1+\beta/2 gives

YES:OPT⁡(Q)≤(1+β2)τ,NO:OPT⁡(Q)≥(1+β)τ.\mathrm{YES:}\quad\operatorname{OPT}(Q)\le\left(1+\frac{\beta}{2}\right)\tau,\qquad\mathrm{NO:}\quad\operatorname{OPT}(Q)\ge(1+\beta)\tau.

We may assume 0<β≤10<\beta\le1. A (1+β/4)(1+\beta/4)-approximation distinguishes these cases: in a YES instance, it returns a network of length at most

(1+β4)(1+β2)τ<(1+β)τ,\left(1+\frac{\beta}{4}\right)\left(1+\frac{\beta}{2}\right)\tau< (1+\beta)\tau,

whereas in a NO instance every network has length at least (1+β)τ(1+\beta)\tau. Thus the reduction preserves a constant approximation gap in O(log⁡n)O(\log n) dimensions, proving the theorem.

Padding to doubly logarithmic dimension

Proof of Theorem 2. Let Q={q1,…,qn}Q = \{q_1,\ldots,q_n\} be a terminal set obtained by the reduction in the proof of Theorem 1. As shown there, a (1+β/4)(1+\beta/4)-approximation distinguishes the source matching instances. By Theorem 4(iii) and the polynomial size of the reduction, under NP⊈SUBEXP\mathrm{NP} \not\subseteq\mathrm{SUBEXP} there is a constant c>0c > 0 such that no such approximation runs in time 2nc2^{n^c}.

To pad QQ, set N=2⌈nc/2⌉N = 2^{\lceil n^{c/2}\rceil}, which is at least nn for sufficiently large nn, and add N−nN-n terminals at the position of one original terminal. This leaves the optimum and the approximation gap unchanged. The padded instance has NN terminals in O(log⁡n)=O(log⁡log⁡N)O(\log n) = O(\log\log N) dimensions, since log⁡N≥nc/2\log N \ge n^{c/2} implies log⁡n≤2clog⁡log⁡N\log n \le\frac{2}{c}\log\log N.

Suppose Euclidean Steiner Tree admits a PTAS in O(log⁡log⁡N)O(\log\log N) dimensions for NN terminals. Running it on the padded instance with the same accuracy would distinguish the source cases in time NO(1)=2O(nc/2)N^{O(1)} = 2^{O(n^{c/2})}, contradicting the 2nc2^{n^c} lower bound.

Lower bounds in fixed dimension d≥3d \ge3

We prove Theorem 3 for fixed d≥3d \ge3. We use the gadgets and cable reduction (Theorem 7) from § 4, changing only the routing. In Rd\mathbb{R}^d, the cables cannot all be short, so we route them along a grid drawing of total length L=Od(md/(d−1))L = O_d(m^{d/(d-1)}). Choosing ρ=Θ(m/L)\rho= \Theta(m/L) keeps the sampling error O(ρL)O(\rho L) in Theorem 7 below half the matching gap, so the YES and NO optima remain Ω(m)\Omega(m) apart. Since both are Θ(L)\Theta(L), the relative gap is Ω(m/L)\Omega(m/L), and hence Ωd(m1/(1−d))\Omega_d(m^{1/(1-d)}).

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 cc such that for all d≥3d \ge3, any graph with nn vertices and maximum degree 2d2d is the topological minor of the dd-dimensional grid hypercube of side length cn1/(d−1)cn^{1/(d-1)}.

A graph GG is a topological minor of the grid precisely when the grid contains a subdivision of GG. The theorem therefore gives a grid drawing in {0,…,S}d\{0,\ldots,S\}^d, where S=⌈cn1/(d−1)⌉S = \lceil cn^{1/(d-1)}\rceil: 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 GG with a vertex for every gadget. We then compute a grid drawing of GG using Theorem 18 and modify it to create the actual gadgets and cables connecting their appropriate ports.

The graph. Let ki≥2k_i \ge2 be the number of gadgets containing a port labelled ii. For an element uu, these are its fallback and the squares for triples containing uu; for the backbone label 00, they are all gadgets. Construct a tree TiT_i 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 GG, ensuring that each original edge of a tree TiT_i 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 GG, square gadgets have degree four, fallback gadgets degree two, and all other vertices degree at most three. Since ∑iki=4∣E∣+2∣U∣\sum_i k_i = 4|E| + 2|U|, the total number of vertices is n=O(m)n = O(m).

The cables. We apply Theorem 18 to compute a grid drawing of GG and scale it by 100. This assigns each gadget ss a grid point zsz_s. 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 ss at zsz_s and modify each drawn tree TiT_i near the gadgets to attach it to the appropriate ports. The resulting cables Γi\Gamma_i form the cable routing (Figure 14).

Wiring a square gadget

Figure 14. Wiring a square gadget. (a) Scaled grid drawing around zsz_s. (b) Γu,Γw,Γ0\Gamma_u,\Gamma_w,\Gamma_0 continue straight from their ports; Γv\Gamma_v leaves along b1b_1 and rejoins its grid segment at zs+50δvz_s+50\delta_v. Inside the dotted ball BsB_s, the cables follow the gadget axes, as required by (S1).

For each label ii of a gadget ss, the drawn tree TiT_i leaves zsz_s along the grid segment (zs,zs+100δi)(z_s,z_s+100\delta_i), where the δi\delta_i are distinct signed coordinate vectors. We draw the gadgets in planes parallel to the b1b2b_1b_2-plane, with ports in directions ±b1,±b2\pm b_1,\pm b_2 for a square and ±b1\pm b_1 for a fallback. We assign each label ii a port ps,ip_{s,i} and write c^i∈{±b1,±b2}\hat{c}_i\in\{\pm b_1,\pm b_2\} for its direction from zsz_s; the assignment and local modifications are as follows (Figure 14(b)).

  1. If δi\delta_i is an available port direction, assign label ii the port in that direction, so c^i=δi\hat{c}_i=\delta_i. Replace the grid segment by the straight segment from ps,ip_{s,i} to zs+100δiz_s+100\delta_i; for example, Γu\Gamma_u has δu=c^u=−b1\delta_u=\hat{c}_u=-b_1 in the figure.

  1. Otherwise, assign label ii one of the remaining ports, so c^i⊥δi\hat{c}_i\perp\delta_i; for example, Γv\Gamma_v has δv=−e3\delta_v=-e_3 and c^v=b1\hat{c}_v=b_1 in the figure. The cable follows c^i\hat{c}_i from its port to zs+25c^iz_s+25\hat{c}_i, continues parallel to the grid segment, and joins it at its midpoint:

ps,i⟶zs+25c^i⟶zs+25c^i+50δi⟶zs+50δi⟶zs+100δi.p_{s,i}\longrightarrow z_s+25\hat{c}_i\longrightarrow z_s+25\hat{c}_i+50\delta_i\longrightarrow z_s+50\delta_i\longrightarrow z_s+100\delta_i.

At each port, the cable begins with a segment in direction c^i\hat{c}_i of length at least 24>2024>20.

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 d(S+1)dd(S+1)^d unit grid edges, the total cable length satisfies

L≤150d(S+1)d=Od(md/(d−1)).L\le150d(S+1)^d=O_d\left(m^{d/(d-1)}\right).

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 d≥3d \ge3, the cable routing in Rd\mathbb{R}^{d} consists of separated cables.

For Euclidean Cable Steiner Tree, the minimum connection cost is 43∣U∣−Δν(H)\frac{4}{3}|U|-\Delta\nu(H), independently of LL (§ 4.2). Thus the cable routing gives a constant approximation gap in fixed dimension.

Corollary 20. For every fixed d≥3d \ge3, Euclidean Cable Steiner Tree is APX-hard in Rd\mathbb{R}^{d}.

Proof. Given an instance HH of 3DM-3, construct the cables above. They are separated by Theorem 19 and have minimum connection cost 43∣U∣−Δν(H)\frac{4}{3}|U|-\Delta\nu(H). Since ∣U∣=3r|U|=3r, this cost equals (4−Δ)r(4-\Delta)r if ν(H)=r\nu(H)=r and is at least (4−Δ+Δδ)r(4-\Delta+\Delta\delta)r if ν(H)≤(1−δ)r\nu(H)\le(1-\delta)r. By Theorem 4, approximating it within the constant factor 1+Δδ/(4−Δ)1+\Delta\delta/(4-\Delta) is therefore NP-hard.

This gives a negative answer for d≥3d\ge3 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 a>0a>0 and cd>0c_d>0 such that, given an instance HH of 3DM-3, one can compute in polynomial time a set P⊆RdP\subseteq\mathbb{R}^{d} of Od(m(d+2)/(d−1))O_d(m^{(d+2)/(d-1)}) terminals and a threshold τ≤cdmd/(d−1)\tau\le c_d m^{d/(d-1)} satisfying

ν(H)=r ⟹ OPT⁡(P)≤τ,ν(H)≤(1−δ)r ⟹ OPT⁡(P)≥τ+am.\nu(H)=r\ \Longrightarrow\ \operatorname{OPT}(P)\le\tau,\qquad\nu(H)\le(1-\delta)r\ \Longrightarrow\ \operatorname{OPT}(P)\ge\tau+am.

Proof. Use the cable routing from § 6.1, which is separated by Theorem 19 and has total cable length L≤Cdmd/(d−1)L\le C_d m^{d/(d-1)}. Let C2C_2 be the constant in Theorem 7 and choose

ρ=min⁡{1100,Δδm12C2L}.\rho=\min\left\{\frac{1}{100},\frac{\Delta\delta m}{12C_2L}\right\}.

so that C2ρL≤Δδ12mC_2\rho L\le\frac{\Delta\delta}{12}m, and set P=PρP=P_\rho and τ=L+43∣U∣−Δr\tau=L+\frac{4}{3}|U|-\Delta r. The YES bound follows from the upper bound in Theorem 7. For the NO bound, set a=Δδ12a=\frac{\Delta\delta}{12}. Then

\begin{aligned} \operatorname{OPT}(P)&\ge L+\frac{4}{3}|U|-\Delta\nu(H)-C_2\rho L &&\text{by the lower bound in {xref}`Theorem 7`,\\ &\ge L+\frac{4}{3}|U|-\Delta r+\Delta\delta r-C_2\rho L &&\text{since }\nu(H)\le(1-\delta)r,\\ &\ge\tau+\frac{\Delta\delta}{6}m-C_2\rho L &&\text{since }m\le6r,\\ &\ge\tau+am &&\text{since }C_2\rho L\le\frac{\Delta\delta}{12}m. \end{aligned}}

The threshold satisfies τ≤L+43m≤cdmd/(d−1)\tau\le L+\frac{4}{3}m\le c_d m^{d/(d-1)}. Since 1/ρ=Od(L/m+1)=Od(m1/(d−1))1/\rho=O_d(L/m+1)=O_d(m^{1/(d-1)}), sampling gives ∣P∣=O(L/ρ2)=Od(m(d+2)/(d−1))|P|=O(L/\rho^2)=O_d(m^{(d+2)/(d-1)}).

**Proof of Theorem 3 for d≥3.∗∗Choosed\ge3.** Choose\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)and polynomially many terminals. Under weak ETH, running time 2O(ε−γ(d−1))poly⁡(n)\text{and polynomially many terminals. Under weak ETH, running time }2^{O(\varepsilon^{-\gamma(d-1)})}\operatorname{poly}(n) for a fixed 0<γ<10<\gamma<1 would solve the matching gap in time 2O(rγ)2^{O(r^\gamma)}, contradicting Theorem 4.

Under Gap-ETH, the same argument would have ruled out time 2o(ε−(d−1))poly⁡(n)2^{o(\varepsilon^{-(d-1)})}\operatorname{poly}(n), since this would yield a 2o(r)2^{o(r)}-time algorithm for the matching gap, contrary to Theorem 4(i). Under NP ⊈\not\subseteq SUBEXP, take c>0c>0 from Theorem 4(iii). Running time 2O(ε−cd(d−1))poly⁡(n)2^{O(\varepsilon^{-cd(d-1)})}\operatorname{poly}(n) would give a 2O(rc)2^{O(r^c)}-time algorithm for the matching gap, contradicting this bound. These arguments establish both bounds stated after Theorem 3, with cc independent of dd because it depends only on the source matching problem.

Lower bounds in the plane

We now prove Theorem 3 for d=2d=2, using the planar construction outlined in § 3.4. The main step is the following analogue of Theorem 21.

Lemma 22. There are constants a>0a>0 and cc such that, given an instance HH of 3DM-3, one can compute in polynomial time a set P⊆R2P\subseteq\mathbb{R}^{2} of O(m4)O(m^{4}) terminals and a threshold τ≤cm2\tau\leq cm^{2} satisfying

ν(H)=r ⟹ OPT⁡(P)≤τ,ν(H)≤(1−δ)r ⟹ OPT⁡(P)≥τ+am.\nu(H)=r\ \Longrightarrow\ \operatorname{OPT}(P)\leq\tau,\qquad\nu(H)\leq(1-\delta)r\ \Longrightarrow\ \operatorname{OPT}(P)\geq\tau+am.

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 ω=1/100\omega=1/100. 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 11 or 1−ω1-\omega, 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 ω\omega-crossover when its upper triangle has side 1−ω1-\omega; all remaining triangles have side 11.

Shortest networks on triangles and a unit square

Figure 15. Shortest networks on k≥2k\geq2 ports of a triangle of side ℓ\ell (a, b) and of a unit square (c–e), with cables in grey and connections in red. Lengths are shown as multiples of k−1k-1.

Layout. We label the elements of HH by 1,…,3r1,\ldots,3r and write E={e1,…,e∣E∣}E=\{e_{1},\ldots,e_{\lvert E\rvert}\}. As in Figure 7, the horizontal levels 0,…,3r0,\ldots,3r are numbered from bottom to top, with the backbone on level 00. Each triple ee has a square QeQ_{e} below level 00 and three columns, one for each j∈ej\in e, while its fourth corner connects to the backbone. The column for jj runs from QeQ_{e} to level jj, with a crossover on each level 0,…,j−10,\ldots,j-1. Its top crossover is an ω\omega-crossover, so choosing its upper triangle saves 3ω\sqrt{3}\omega. Each column has at most 3r3r crossovers, giving a total of C≤9r∣E∣C\leq9r\lvert E\rvert crossovers.

Cables. At a crossover xx, let Ux,DxU_{x},D_{x} denote the cables above and below, and Lx,RxL_{x},R_{x} those to the left and right (Figure 6(c, Figure 6d)), so Ux=DyU_{x}=D_{y} for the crossover yy directly above xx. 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 jj ends on level jj, and the cable above its top crossover continues along that level; the backbone is part of the leftmost cable of level 00. There are CC cables below crossovers and C+3r+1C+3r+1 along the levels, for a total of 2C+3r+12C+3r+1 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 qq be the number of used squares and CωC_{\omega} the number of up ω\omega-crossovers. It uses one triangle at each crossover, at a cost of 3(1−ω)\sqrt{3}(1-\omega) for an up ω\omega-crossover and 3\sqrt{3} otherwise, while each used square costs 1+31+\sqrt{3}. Its total length is therefore

L+3C+(1+3)q−3ωCω.L+\sqrt{3}C+(1+\sqrt{3})q-\sqrt{3}\omega C_{\omega}.

The argument in § 3.4 gives q≥rq\ge r, since connecting all levels requires at least rr squares: each used square has three columns, each joining one pair of consecutive levels. Moreover, at most one ω\omega-crossover per element can be up, since two would create a cycle, so Cω≤3rC_{\omega}\le3r. Together, these bounds give length at least

τ=L+3C+(1+3)r−33ωr.(5)\tau=L+\sqrt{3}C+(1+\sqrt{3})r-3\sqrt{3}\omega r. \tag*{(5)}

Equality requires q=rq=r and Cω=3rC_{\omega}=3r. The up ω\omega-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 τ\tau (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 3 ω\sqrt{3}\,\omega, 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 ss centred at zsz_s, let BsB_s be the closed ball of radius 20 around zsz_s. 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 BsB_s are pairwise more than 20 apart. Inside each BsB_s, the cables consist exactly of the radial segments from the ports of ss to the boundary of BsB_s. Any two points on different cables at distance less than 20 lie in a common ball BsB_s.

(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 45∘45^\circ.

(iii) The cables can be constructed in polynomial time and have total length L=O(r2)L=O(r^2).

For 0<ρ≤1/1000<\rho\le1/100, sample terminals along the cables as in § 4.1 to obtain PρP_{\rho}. Cable recovery (Theorem 8) applies to every tree of length O(L)O(L) on PρP_{\rho}, since its proof needs only (S2) and separation greater than 2ρ2\rho between different cables. Here (S2) follows from Theorem 23(ii), and part (i) gives a separation of at least 1−ω>2ρ1-\omega>2\rho.

Let TT be an optimal tree on PρP_\rho. Since the cables together with Steiner trees at the gadgets form a connected network of length O(L)O(L), we have len⁡(T)=O(L)\operatorname{len}(T)=O(L). As in § 4.3, recovery yields a tree T^\widehat{T} of length at most len⁡(T)+O(ρL)\operatorname{len}(T)+O(\rho L). It consists of disjoint trees TiT_i, each containing all sampled terminals on Γi\Gamma_i, with total length at least LL, and connectors joining these trees (Figure 11). Each connector SS has rSr_S attachments on rSr_S distinct cables, so with 2C+3r+12C+3r+1 cables in total, the count (3) becomes

∑S(rS−1)=(2C+3r+1)−1=2C+3r.(6)\sum_S (r_S-1)=(2C+3r+1)-1=2C+3r. \tag*{(6)}

Following § 4.3, we distinguish good and bad connectors.

Definition 24. A connector is

  • (i) good at a triangle ss with ports ps,1,ps,2,ps,3p_{s,1},p_{s,2},p_{s,3} if it has exactly three attachments, one within distance ρ\rho of the cable segment inside BsB_s leaving each port;

  • (ii) good at a square ss with ports ps,1,…,ps,4p_{s,1},\ldots,p_{s,4} if it has exactly four attachments, one within distance ρ\rho of the cable segment inside BsB_s 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 O(ρ)O(\rho) 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 SS be a connector with rr attachments.

  • (i) If SS is good at a triangle of side ℓ\ell, then len⁡(S)≥3ℓ−3ρ\operatorname{len}(S)\ge\sqrt{3}\ell-3\rho.

  • (ii) If SS is good at a square, then len⁡(S)≥1+3−4ρ\operatorname{len}(S)\ge1+\sqrt{3}-4\rho.

  • (iii) If SS is bad, then len⁡(S)≥(1+322−2ρ)(r−1)\operatorname{len}(S)\ge\left(\frac{1+\sqrt{3}}{2\sqrt{2}}-2\rho\right)(r-1).

Proof. Let x1,…,xrx_1,\ldots,x_r be the attachments of SS. Choose the points xˉj\bar{x}_j and group the attachments as in the proof of Theorem 13, using the balls BsB_s of Theorem 23. If there are g≥2g\ge2 groups, then SS is bad, and the same disjoint-ball argument gives

len⁡(S)≥9g≥2(4g−1)≥2(r−1),\operatorname{len}(S)\ge9g\ge2(4g-1)\ge2(r-1),

proving (iii).

If there is only one group, all points xˉj\bar{x}_j lie in a single ball BsB_s. Projecting SS onto the triangle or square and joining the projected attachments to their ports gives a network on rr ports of ss of length at most len⁡(S)+rρ\operatorname{len}(S)+r\rho (Figure 16). When SS is good, this network joins all ports, at a cost of at least 3ℓ\sqrt{3}\ell for a triangle of side ℓ\ell or 1+31+\sqrt{3} for a square (Figure 15(b, Figure 15e)), proving (i) and (ii).

Projection onto a triangle gadget

Figure 16. Projection onto a triangle gadget. (a) Each attachment xjx_j of SS lies within distance ρ\rho of a cable point xˉj\bar{x}_j. (b) The shaded regions project to the ports, and projection does not increase the length of SS. The dotted segments, each of length at most ρ\rho, connect the projected network S′S' to the ports.

Otherwise, the network joins two ports of a triangle, at cost ℓ≥1−ω>1+322\ell\ge1-\omega>\frac{1+\sqrt{3}}{2\sqrt{2}} (Figure 15(a)), or two ports of a square, at cost 1>1+3221>\frac{1+\sqrt{3}}{2\sqrt{2}} (Figure 15(c)) or 2>1+322\sqrt{2}>\frac{1+\sqrt{3}}{2\sqrt{2}}. Joining three ports of a square costs 1+32=2⋅1+322\frac{1+\sqrt{3}}{\sqrt{2}}=2\cdot\frac{1+\sqrt{3}}{2\sqrt{2}} (Figure 15(d)). Thus each cost is at least 1+322(r−1)\frac{1+\sqrt{3}}{2\sqrt{2}}(r-1). Subtracting rρr\rho and using r≤2(r−1)r\le2(r-1) gives (iii). □

Extending the terminology for clean trees, we call a crossover xx 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 LxL_x to RxR_x, creating a cycle.

The upper bound

Recall the threshold from (5),

τ=L+3C+(1+3)r−33ωr.\tau= L + \sqrt{3}C + (1+\sqrt{3})r - 3\sqrt{3}\omega r.

Lemma 26. If ν(H)=r\nu(H)=r, then OPT⁡(Pρ)≤τ\operatorname{OPT}(P_\rho) \le\tau.

Proof. Let MM 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 PρP_\rho because it includes the edges between consecutive terminals on every cable, and it has length τ\tau because q=rq=r and Cω=3rC_\omega=3r. It is connected because each level is connected and the up ω\omega-crossover for each element jj joins levels j−1j-1 and jj.

The lower bound

If T^\hat{T} 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:

  • DbrD_{\mathrm{br}}, the number of broken crossovers;

  • Dbad=∑S(rS−1)D_{\mathrm{bad}}=\sum_S(r_S-1), summed over all bad connectors SS, the number of connections made by bad connectors;

  • Dω=max⁡{3r−Cω,0}D_\omega=\max\{3r-C_\omega,0\}, the number of missing discounts, where CωC_\omega is the number of up ω\omega-crossovers.

Let D=Dbr+Dbad+DωD=D_{\mathrm{br}}+D_{\mathrm{bad}}+D_\omega be the total deviation. If D=0D=0, then T^\hat{T} has the connectors of a clean tree with all 3r3r discounts, so its used squares give a perfect matching by § 7.1. We will show that len⁡(T)≥τ+3ωD−O(ρL)\operatorname{len}(T)\ge\tau+\sqrt{3}\omega D-O(\rho L), so each deviation adds length, and that ν(H)≥r−5D\nu(H)\ge r-5D, so few deviations still give a large matching.

For each element jj, let Cω,jC_{\omega,j} be the number of up ω\omega-crossovers in the columns of jj, so Cω=∑jCω,jC_\omega=\sum_j C_{\omega,j}. In a clean tree with no broken crossovers, Cω,j≤1C_{\omega,j}\le1 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 DbrD_{\mathrm{br}}.

Lemma 27. ∑j=13rmax⁡{Cω,j−1,0}≤2Dbr\sum_{j=1}^{3r}\max\{C_{\omega,j}-1,0\}\le2D_{\mathrm{br}}. In particular, Cω≤3r+2DbrC_{\omega}\le3r+2D_{\mathrm{br}}.

Proof. Let Dbr,iD_{\mathrm{br},i} be the number of broken crossovers on level ii. Along each level, the good connectors join its cables into subtrees, with a break at each broken crossover. Thus there are 1+Dbr,i−11+D_{\mathrm{br},i-1} subtrees on level i−1i-1 and 1+Dbr,i1+D_{\mathrm{br},i} on level ii. Each of the Cω,iC_{\omega,i} up ω\omega-crossovers of element ii lies on level i−1i-1 and links a subtree there to one on level ii (Figure 17). These links cannot form a cycle, so their number is at most one less than the total number of subtrees, giving Cω,i≤1+Dbr,i−1+Dbr,iC_{\omega,i}\le1+D_{\mathrm{br},i-1}+D_{\mathrm{br},i}. Hence max⁡{Cω,i−1,0}≤Dbr,i−1+Dbr,i\max\{C_{\omega,i}-1,0\}\le D_{\mathrm{br},i-1}+D_{\mathrm{br},i}. Summing over ii counts each Dbr,iD_{\mathrm{br},i} at most twice and proves the first statement. The second follows from Cω≤3r+∑imax⁡{Cω,i−1,0}C_{\omega}\le3r+\sum_i\max\{C_{\omega,i}-1,0\}.

Four up $\omega$-crossovers linking levels

Figure 17. Figure 17: Theorem 27: four up ω\omega-crossovers of element ii (circled) link level i−1i-1 to the cables of level ii 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 Dbr,i−1=2D_{\mathrm{br},i-1}=2 and Dbr,i=1D_{\mathrm{br},i}=1, 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 C3C_3 such that len⁡(T)≥τ+3ωD−C3ρL\operatorname{len}(T)\ge\tau+\sqrt{3}\omega D-C_3\rho L.

Proof. Let qq 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 DbadD_{\mathrm{bad}} in total. There are C−DbrC-D_{\mathrm{br}} good triangle connectors, so 2(C−Dbr)+3q+Dbad=2C+3r2(C-D_{\mathrm{br}})+3q+D_{\mathrm{bad}}=2C+3r, giving

3q+Dbad=3r+2Dbr.(7)3q+D_{\mathrm{bad}}=3r+2D_{\mathrm{br}}. \tag*{(7)}

The cable trees TiT_i have total length at least LL. Summing the bounds of Theorem 25 over the connectors and using len⁡(T^)≤len⁡(T)+O(ρL)\operatorname{len}(\widehat{T})\le\operatorname{len}(T)+O(\rho L) gives

len⁡(T)+O(ρL)≥len⁡(T^)≥L+(1−ω)3Cω+3(C−Dbr−Cω)+(1+3)q+1+322Dbad−2ρL.\operatorname{len}(T)+O(\rho L)\ge\operatorname{len}(\widehat{T})\ge L+(1-\omega)\sqrt{3}C_{\omega}+\sqrt{3}(C-D_{\mathrm{br}}-C_{\omega})+(1+\sqrt{3})q+\frac{1+\sqrt{3}}{2\sqrt{2}}D_{\mathrm{bad}}-2\rho L.

Each connector SS contributes an error of at most 2ρ(rS−1)2\rho(r_S-1), so the total error is at most 2ρ∑S(rS−1)=2ρ(2C+3r)≤2ρL2\rho\sum_S(r_S-1)=2\rho(2C+3r)\le2\rho L, since every cable has length at least 1. Recall that τ=L+3C+(1+3)r−33ωr\tau=L+\sqrt{3}C+(1+\sqrt{3})r-3\sqrt{3}\omega r. By (7), q=r+2Dbr−Dbad3q=r+\frac{2D_{\mathrm{br}}-D_{\mathrm{bad}}}{3}. Also, Theorem 27 gives 3r−Cω≥Dω−2Dbr3r-C_{\omega}\ge D_{\omega}-2D_{\mathrm{br}}: this is immediate if Cω≤3rC_{\omega}\le3r, and otherwise follows from Cω≤3r+2DbrC_{\omega}\le3r+2D_{\mathrm{br}}. We obtain

len⁡(T)+O(ρL)≥L+3C−3ωCω−3Dbr+(1+3)(r+2Dbr−Dbad3)+1+322Dbad−2ρLsubstituting q,=τ+3ω(3r−Cω)+2−33Dbr+(1+322−1+33)Dbad−2ρLby definition of τ,≥τ+3ω(3r−Cω)+0.089Dbr+0.055Dbad−2ρLrounding down,≥τ+3ωDω+(0.089−23ω)Dbr+0.055Dbad−2ρLby xref‘Theorem 27‘,≥τ+3ωDω+3ωDbr+3ωDbad−2ρLsince ω=1/100,=τ+3ωD−2ρLby definition of D.\begin{aligned} \operatorname{len}(T) + O(\rho L) &\ge L + \sqrt{3}C - \sqrt{3}\omega C_\omega- \sqrt{3}D_{\mathrm{br}} \\ &\quad+ (1+\sqrt{3})\left(r+\frac{2D_{\mathrm{br}}-D_{\mathrm{bad}}}{3}\right)+\frac{1+\sqrt{3}}{2\sqrt{2}}D_{\mathrm{bad}}-2\rho L && \text{substituting }q,\\ &= \tau+\sqrt{3}\omega(3r-C_\omega)+\frac{2-\sqrt{3}}{3}D_{\mathrm{br}} \\ &\quad+\left(\frac{1+\sqrt{3}}{2\sqrt{2}}-\frac{1+\sqrt{3}}{3}\right)D_{\mathrm{bad}}-2\rho L && \text{by definition of }\tau,\\ &\ge\tau+\sqrt{3}\omega(3r-C_\omega)+0.089D_{\mathrm{br}}+0.055D_{\mathrm{bad}}-2\rho L && \text{rounding down},\\ &\ge\tau+\sqrt{3}\omega D_\omega+(0.089-2\sqrt{3}\omega)D_{\mathrm{br}}+0.055D_{\mathrm{bad}}-2\rho L && \text{by {xref}`Theorem 27`},\\ &\ge\tau+\sqrt{3}\omega D_\omega+\sqrt{3}\omega D_{\mathrm{br}}+\sqrt{3}\omega D_{\mathrm{bad}}-2\rho L && \text{since }\omega=1/100,\\ &= \tau+\sqrt{3}\omega D-2\rho L && \text{by definition of }D. \end{aligned}

Absorbing the error terms into C3ρLC_3\rho L proves the claim.

To obtain a matching from T^\widehat{T}, 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 3r3r discounts, the columns with an up ω\omega-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. ν(H)≥r−5D\nu(H) \ge r-5D.

Proof. We first show that at most Dbr+2DbadD_{\mathrm{br}}+2D_{\mathrm{bad}} of the CωC_\omega columns with an up ω\omega-crossover are not good. Consider a column with an up ω\omega-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 DbrD_{\mathrm{br}} columns, and each cable below a crossover belongs to just one column. Since a bad connector SS attaches to at most rS≤2(rS−1)r_S\le2(r_S-1) cables, at most 2Dbad2D_{\mathrm{bad}} columns have such an attachment. Hence at most Dbr+2DbadD_{\mathrm{br}}+2D_{\mathrm{bad}} of these columns are not good. Hence there are at least Cω−Dbr−2DbadC_\omega-D_{\mathrm{br}}-2D_{\mathrm{bad}} good columns. Each of them belongs to the square of one of the qq good square connectors. If q3q_3 of these squares have three good columns, then the others have at most two, so there are at most 3q3+2(q−q3)=q3+2q3q_3+2(q-q_3)=q_3+2q good columns. Hence

Three column diagrams showing a good column, a broken crossover, and a down crossover below an up crossover

Figure 18. Columns with an up ω\omega-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.

q3≥Cω−Dbr−2Dbad−2q≥Cω−2r−73Dbr−2Dbadas q≤r+23Dbr by xref‘(6)‘.\begin{aligned} q_3 \ge C_\omega-D_{\mathrm{br}}-2D_{\mathrm{bad}}-2q \\ &\ge C_\omega-2r-\frac{7}{3}D_{\mathrm{br}}-2D_{\mathrm{bad}} \qquad\text{as }q\le r+\frac{2}{3}D_{\mathrm{br}}\text{ by }{xref}`(6)`. \end{aligned}

The triples of these q3q_3 squares almost form a matching. If such a triple contains an element jj, then its square has a column of jj, and this column is good, so its ω\omega-crossover is up. Several of these triples may share an element jj, but at most Cω,jC_{\omega,j} of them contain jj. For every element that lies in several of them, we discard all but one, which discards at most ∑jmax⁡{Cω,j−1,0}≤2Dbr\sum_j\max\{C_{\omega,j}-1,0\}\le2D_{\mathrm{br}} triples by Theorem 27. The remaining triples are disjoint, and hence

ν(H)≥q3−2Dbr≥Cω−2r−133Dbr−2Dbadas q3≥Cω−2r−73Dbr−2Dbad,≥r−5Das 3r−Cω≤Dω.\begin{aligned} \nu(H)\ge q_3-2D_{\mathrm{br}} \\ &\ge C_\omega-2r-\frac{13}{3}D_{\mathrm{br}}-2D_{\mathrm{bad}} \qquad\text{as }q_3\ge C_\omega-2r-\frac{7}{3}D_{\mathrm{br}}-2D_{\mathrm{bad}}, \\ &\ge r-5D \qquad\text{as }3r-C_\omega\le D_\omega. \end{aligned}

The gap

Lemma 30. There are constants a>0a>0 and cc such that, given an instance HH of 33DM-3, one can compute in polynomial time a set P⊆R2P\subseteq\mathbb{R}^2 of O(m4)O(m^4) terminals and a threshold τ≤cm2\tau\le cm^2 satisfying

ν(H)=r⇒OPT⁡(P)≤τ,ν(H)≤(1−δ)r⇒OPT⁡(P)≥τ+am.\nu(H)=r\Rightarrow\operatorname{OPT}(P)\le\tau,\qquad \nu(H)\le(1-\delta)r\Rightarrow\operatorname{OPT}(P)\ge\tau+am.

Proof of Theorem 22. Construct the cables of Theorem 23, with L≤C4m2L\le C_4m^2. Let C3C_3 be the constant in Theorem 28, fix

ρ=min⁡{1100,ω3δm60C3L},\rho=\min\left\{\frac{1}{100},\frac{\omega\sqrt{3}\delta m}{60C_3L}\right\},

so that C3ρL≤ω3δ60mC_3\rho L\le\frac{\omega\sqrt{3}\delta}{60}m, and set P=PρP=P_\rho and τ=L+3C+(1+3)r−33ωr\tau=L+\sqrt{3}C+(1+\sqrt{3})r-3\sqrt{3}\omega r.

The first implication is Theorem 26. For the second, let TT be an optimal tree on PP and a=ω3δ60a=\frac{\omega\sqrt{3}\delta}{60}. Then

OPT⁡(P)=len⁡(T)≥τ+3ωD−C3ρLby xref‘Theorem 28‘,≥τ+3ω5(r−ν(H))−C3ρLby xref‘Theorem 29‘,≥τ+ω3δ30m−C3ρLsince ν(H)≤(1−δ)r and m≤6r,≥τ+amsince C3ρL≤ω3δ60m.\begin{aligned} \operatorname{OPT}(P)=\operatorname{len}(T)\ge\tau+\sqrt{3}\omega D-C_3\rho L \qquad\text{by {xref}`Theorem 28`,} \\ &\ge\tau+\frac{\sqrt{3}\omega}{5}(r-\nu(H))-C_3\rho L \qquad\text{by {xref}`Theorem 29`,} \\ &\ge\tau+\frac{\omega\sqrt{3}\delta}{30}m-C_3\rho L \qquad\text{since }\nu(H)\le(1-\delta)r\text{ and }m\le6r, \\ &\ge\tau+am \qquad\text{since }C_3\rho L\le\frac{\omega\sqrt{3}\delta}{60}m. \end{aligned}

Moreover, τ≤L+3C+(1+3)r=O(m2)\tau\le L+\sqrt{3}C+(1+\sqrt{3})r=O(m^2), and 1/ρ=O(L/m+1)=O(m)1/\rho=O(L/m+1)=O(m), so ∣P∣=O(L/ρ2)=O(m4)|P|=O(L/\rho^2)=O(m^4).

Proof of Theorem 3 for d=2d=2. Replace Theorem 21 by Theorem 22 and cdc_d by cc in the proof for d≥3d\ge3.

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 (1+ε)(1+\varepsilon)-approximation algorithm runs in time 2o(ε−(d−1))poly⁡(n)2^{o(\varepsilon^{-(d-1)})}\operatorname{poly}(n) for any fixed d≥2d \ge2.

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 NP⊈SUBEXP\mathrm{NP} \not\subseteq\mathrm{SUBEXP}, Theorem 2 excludes a PTAS in O(log⁡log⁡n)O(\log\log n) dimensions, while Arora’s scheme [4] gives one in up to log⁡log⁡n/log⁡log⁡log⁡n\log\log n/\log\log\log n dimensions. Can this O(log⁡log⁡log⁡n)O(\log\log\log n) 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 O(log⁡log⁡n)O(\log\log n) dimensions under the same hypothesis, and Arora’s scheme gives a PTAS in up to log⁡log⁡n/log⁡log⁡log⁡n\log\log n/\log\log\log n 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 d≥3d \ge3

Proof of Theorem 19. The construction preserves the tree structure of each TiT_i, so Γi\Gamma_i is a tree containing exactly the ports labelled ii. 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 zsz_s, as the trees share only gadget vertices.

On the path replacing (zs,zs+100δi)(z_s,z_s+100\delta_i), every point has the form y=zs+ac^i+bδiy=z_s+a\hat{c}_i+b\delta_i with a,b≥0a,b\ge0. By the port assignment, directions used by different labels are orthogonal or opposite, so points y,y′y,y' on different such paths satisfy ⟨y−zs,y′−zs⟩≤0\langle y-z_s,y'-z_s\rangle\le0 and hence

∥y−y′∥≥max⁡{∥y−zs∥,∥y′−zs∥}.(8)\lVert y-y'\rVert\ge\max\{\lVert y-z_s\rVert,\lVert y'-z_s\rVert\}. \tag*{(8)}

(S1)(S1). The balls BsB_s 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 zsz_s, and (8) places both points in BsB_s.

(S2)(S2). All segments have length at least 24, and incident segments meet at angles of 90∘90^\circ or 180∘180^\circ. 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).

Cable routing at a crossover and a square

Figure 19. Cable routing at (a) a crossover (X,Y)(X,Y) and (b) a square QeQ_e. 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 BsB_s, the cables consist exactly of these radial segments.

  • Place level ii on y=200iy = 200i. For each triple eke_k, place its three columns on x=800kx = 800k, x=800k+200x = 800k + 200, and x=800k+400x = 800k + 400, and centre QekQ_{e_k} at (800k+200,−200)(800k + 200, -200) with its diagonals parallel to the coordinate axes.

  • At a crossover (X,Y)(X,Y), centre the upper triangle at (X,Y+40)(X,Y+40) with a corner pointing up, and the lower triangle at (X,Y−40)(X,Y-40) with a corner pointing down. Join the left corners of both triangles to (X−403,Y)(X-40\sqrt{3},Y), and the right corners to (X+403,Y)(X+40\sqrt{3},Y).

  • Along a column of element jj at x=Xx = X, join consecutive crossovers by their facing ports. Connect the top port of its highest crossover to (X,200j)(X,200j) on level jj, and the bottom port of its lowest crossover to the nearest port of its square, with a bend at (X,−200)(X,-200) for either outer column.

  • Along level ii, join successive junctions and endpoints of columns for element ii by horizontal segments, omitting the interval between the two junctions of a crossover. Extend level 0 leftwards to (0,0)(0,0).

  • Route the backbone from (0,0)(0,0) to (0,−400)(0,-400) and then along y=−400y=-400 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 BsB_s are more than 20 apart. Inside each BsB_s, 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 90∘90^\circ, so points at distances t,t′t,t' from the centre are at least max⁡{t,t′}\max\{t,t'\} apart; a distance of less than 20 therefore forces both points into BsB_s. (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 60∘60^\circ or 150∘150^\circ, while all other incident angles are 90∘90^\circ.

(iii) The total length of the 3r+13r+1 levels and 3∣E∣3|E| columns is O(r∣E∣)O(r|E|), with the remaining segments contributing O(C+∣E∣)O(C+|E|). Since ∣E∣≤3r|E| \le3r and C≤9r∣E∣C \le9r|E|, we obtain L=O(r2)L = O(r^2), 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 2o(t)2^{o(t)} for bounded-occurrence gap-3SAT on instances of size tt [32 Corollary 6.1, full version]. Since Petrank’s reduction gives r=O(t)r = O(t), a 2o(r)2^{o(r)}-time algorithm for the matching gap would solve these source instances in time 2o(t)2^{o(t)}.

For (ii), Dinur’s nearly linear PCP [20], followed by Petrank’s reduction, maps a 3SAT formula of size ss to a matching gap instance with r=O(spolylog⁡(s))r = O(s\operatorname{polylog}(s)). For any fixed 0<γ<10 < \gamma< 1, a 2O(rγ)2^{O(r^\gamma)}-time algorithm would therefore decide 3SAT in time 2O(sγpolylog⁡(s))≤2O(s(1+γ)/2)2^{O(s^\gamma\operatorname{polylog}(s))} \le2^{O(s^{(1+\gamma)/2})}. Here the polylogarithmic factor is absorbed into s(1−γ)/2s^{(1-\gamma)/2}, and (1+γ)/2<1(1+\gamma)/2 < 1, contradicting weak ETH.

For (iii), the PCP theorem followed by Petrank’s reduction gives r≤skr \le s^k for a constant kk. Under NP ⊈\not\subseteq SUBEXP, 3SAT has no 2sc′2^{s^{c'}}-time algorithm for some c′>0c' > 0. Taking c=c′/(2k)c = c'/(2k), a 2rc2^{r^c}-time algorithm would decide 3SAT in time 2sc′/2+poly⁡(s)2^{s^{c'/2}} + \operatorname{poly}(s), contradicting this bound.

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [13]Claude. A 2^(n) Time Algorithm for 3-SAT, 2026. Preprint, Anthropic, October 26.
  14. [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. [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. [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. [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. [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. [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. [20]Irit Dinur. The PCP Theorem by Gap Amplification. J. ACM, 54(3):12, 2007. doi:10.1145/1236457.1236459.DOI
  21. [21]Lars Engebretsen, Piotr Indyk, and Ryan O’Donnell. Derandomized dimensionality reduction with applications. In SODA, pages 705–712. ACM/SIAM, 2002.
  22. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [34]OpenAI. The Exponential Time Hypothesis is False, 2026. Preprint, revised October 25.hub.valency.io/works/W_h8uqubsk
  35. [35]Erez Petrank. The Hardness of Approximation: Gap Location. Comput. Complex., 4:133–157, 1994. doi:10.1007/BF01202286.DOI
  36. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_xsy8e8wz
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents