through $s^{\prime}$ as in Lemma 6.5 in order to reestablish (P1) and ensure
that this change does not increase $\|s-s^{\prime}\|_{\infty}$, thereby not
increasing the cost of the tree. Note that this relies on our assumption that,
for all $i$ such that $|s_{i}|=1/2+\varepsilon$, there exists $t\in P(s)$ such
that $\operatorname{sgn}(t_{i})=\operatorname{sgn}(s_{i})$. Afterward, we may
apply the modifications outlined in Lemma 6.5 to re-establish (P1) and (P2)
since they will not increase the magnitude of coordinates of Steiner leaves.

Now, if we still have $\|s\|_{\infty}=1/2+\varepsilon^{\prime}>1/2$, there
exists some coordinate $i$ such that $|s_{i}|=\|s\|_{\infty}$ and for all
$t\in P(s)$, $t_{i}=0$. Now, for coordinates $j$ such that $s_{j}>1/2$, set
$s_{j}=1/2$ and, likewise, if $s_{j}<-1/2,$ set $s_{j}=-1/2$. Then, for all
$t\in P(s)$, $\|s-t\|_{\infty}$ decreases by $\varepsilon^{\prime}$ and
$\|s-s^{\prime}\|_{\infty}$ increases by at most $\varepsilon^{\prime}$. Since
$|P(s)|\geq 2$, this actually decreases the cost of the tree, contradicting
minimality. Hence, this case cannot occur.

It remains to show that, for each coordinate $i$ such that there exists $t\in
P(s)$ with $t_{i}\neq 0$, $|s_{i}|=1/2$. Call such coordinates corresponding
coordinates of $s$ (with the terminal $t\in P(s)$ corresponding to such a
coordinate referred to as a corresponding terminal). Let $i$ be a
corresponding coordinate of $s$ such that $|s_{i}|$ is minimal; say
$|s_{i}|=1/2-\varepsilon$. By (P2),
$\operatorname{sgn}(s_{i})=\operatorname{sgn}(t_{i})$ for corresponding
terminal $t.$ By the above, $\|s\|_{\infty}\leq 1/2$. Now, increasing the
magnitude of all corresponding coordinates of $s$ (while retaining their sign)
will decrease the distance to $t$ by $\varepsilon$ and increase the distance
from $s$ to $s^{\prime}$ by at most $\varepsilon$. Hence, repeating this
operation does not increase the cost of the Steiner tree while ensuring
Property (P5). If (P1) or (P2) are ever violated, they be restored by the
processes described in Lemma 6.5 without violating (P5). Properties (P3) and
(P4) are unaffected by the modifications outlined above. ∎

The language introduced in Lemma 6.10 will be useful in the following lemmas.
For $s$ a Steiner point, call $C(s)=\\{i\,:\,t\in P(s),t_{i}\neq 0\\}$ the set
of corresponding coordinates of $s$. We observe an implication of Lemma 6.10.

######  Lemma 6.11.

There exists a optimal Steiner $T(\widetilde{P}\cup X,E)$ satisfying (P1),
(P2), (P3), (P4), (P5), and the following additional property:

  1. (P6)

Steiner leaf independence: Let $s$ be a Steiner leaf. Then, if
$s^{\prime\prime}$ is a Steiner point adjacent to $s$, then $C(s)\cap
C(s^{\prime\prime})=\emptyset$. Moreover, for all other Steiner leaves
$s^{\prime}$ adjacent to $s^{\prime\prime}$, $C(s)\cap
C(s^{\prime})=\emptyset$.

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be a Steiner tree satisfying (P1), (P2), (P3),
(P4), and (P5). Let $s$ be a Steiner leaf and $s^{\prime\prime}$ be a Steiner
point neighboring $s$. First, suppose that $i\in C(s)\cap
C(s^{\prime\prime})$. Then, $s_{i}=1/2$ (using (P5)). Note that
$s^{\prime\prime}_{i}<0$ by (P2). Then, dropping the edge
$(s,s^{\prime\prime})$ and adding the edge $(s,\mathbf{0})$ maintains the
connectivity of the tree while decreasing its cost, contradicting optimality
of $T$.

Now, let $s^{\prime}$ be a second Steiner leaf neighboring $s^{\prime\prime}$
and let $i\in C(s)\cap C(s^{\prime})$. Without loss of generality assume
$s_{i}=1/2$ and $s_{i}^{\prime}=-1/2$. Then, clearly either
$\|s^{\prime\prime}-s\|_{\infty}\geq 1/2$ or
$\|s^{\prime\prime}-s^{\prime}\|_{\infty}\geq 1/2$. Assume that
$\|s^{\prime\prime}-s\|_{\infty}\geq 1/2$. Removing edge
$(s,s^{\prime\prime})$ and adding edge $(s,\mathbf{0})$ then removes this pair
of Steiner points violating (P6) while keeping the tree connected and not
increasing its cost. The fact that the cost does not increase follows from
(P5). This modification may affect (P1), (P4), (P5), but following the
algorithms described in Lemmas 6.5, and 6.9 and 6.10 can re-establish these
properties without increasing the number of pairs of Steiner leaves violating
(P6). Repeating this process then yields the result. ∎

We are now ready to prove the final and most important structural property of
optimal Steiner trees: there exist optimal Steiner trees with no edges between
Steiner points.

######  Lemma 6.12.

There exists a optimal Steiner $T(\widetilde{P}\cup X,E)$ satisfying (P1),
(P2), (P3), (P4), (P5), (P6), and the following additional property:

  1. (P7)

Steiner adjacency: There are no edges between Steiner points in $T.$

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree satisfying (P1),
(P2), (P3), (P4), (P5), and (P6). To prove this result, we begin with an
important claim.

######  Claim 6.12.1.

We may assume that, for all non-leaf $s\in X$, $s$ is adjacent (in $T$) to
$\mathbf{0}$ and at least one other non-leaf Steiner point or at least two
non-leaf Steiner points.

###### Proof.

Suppose some non-leaf Steiner point $s$ in $T$ does not have this property.
Since $s$ is not a Steiner leaf, it must be adjacent to at least two points
that are not nonzero terminals. Hence, it is adjacent to at least one Steiner
leaf $s^{\prime}$. By (P6), we have $C(s)\cap C(s^{\prime})=\emptyset$ and,
for any two Steiner leaves $s^{\prime}$ and $s^{\prime\prime}$ adjacent to
$s$, $s^{\prime}$ and $s^{\prime\prime}$, $C(s^{\prime})\cap
C(s^{\prime\prime})=\emptyset$.

Note that by (P1), all coordinates in $C(s^{\prime})$ behave the same in the
following sense. Upon rooting the tree at $s^{\prime}$ and directly all edges
away from $s^{\prime}$, these coordinates decrease maximally in magnitude
until reaching $0$. So, until they reach $0$, they all have the same
magnitude. Now, fix a Steiner leaf $s^{\prime}$ adjacent to $s$. Remove all
edges from $s$ to its neighboring nonzero terminals, add edges from those
nonzero terminals to $s^{\prime}$, and treat each coordinate previously in
$C(s)$ like the coordinates previously in $C(s^{\prime})$ (setting them to
have the same magnitudes and appropriate signs), propagating through the tree
until the coordinates reach $0$. This does not increase the cost of the tree
since $s^{\prime}$ is a Steiner leaf, the tree satisfies property (P1), and we
had $C(s)\cap C(s^{\prime})=\emptyset$.

Do the same process outlined above for all other Steiner leaves adjacent to
$s$ (replace their edges to nonzero terminals with edges from those terminals
to $s^{\prime}$ and have their corresponding coordinates emulate the
coordinates of other nonzero terminals adjacent to $s^{\prime}$). Also drop
those Steiner leaf Steiner points.

After this process, $s$ has degree $2$, so, by the triangle inequality, it can
be removed and an edge can be added directly between its two neighbors. We can
repeat this process until $s^{\prime}$ is either adjacent to $\mathbf{0}$ or a
non-leaf Steiner point satisfying the desired property. At some points, we may
need to restore (P6), but we can do so by following the algorithm described in
Lemma 6.12.

Repeating for all non-leaf Steiner points without this property then ensures
the property holds in the resultant tree. After each step, we can restore
properties (P1) and (P2) by applying the algorithm described in Lemma 6.5. The
other properties are unaffected by these modifications. ∎

Given the claim, consider removing non-root terminals and Steiner leaf nodes
from $T$. By the claim, all remaining Steiner points are degree at least two.
But then, by (P3), the only possible leaf node in the resultant graph is
$\mathbf{0}$. The only tree with only one leaf node is a singleton vertex,
implying all Steiner points in $T$ are Steiner leaves. Hence, we have (P7). ∎

Lemma 6.9 in fact show that there exist optimal Steiner trees with exactly the
structure of the completeness case. This is formalized in Lemma 6.13

######  Lemma 6.13.

There exists an optimal Steiner tree in which the length of each edge is $1/2$
and the number of Steiner points is exactly $\chi(G)$.

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree satisfying
properties (P1), (P2), (P3), (P4), (P5), (P6), and (P7).

By (P3), (P7), (P2), and (P4), each terminal is either connected to a Steiner
point by an edge of length $1/2$ or connected to $\mathbf{0}$ by an edge of
length $1$. Each edge from a Steiner point to $\mathbf{0}$ is length $1/2$.

For each edge of length $1$ from a terminal, we can add an intermediate
Steiner point halfway along that edge (corresponding to the terminal) such
that the edge is split into two edges of length $1/2$. Then, the cost is fixed
and each edge is of length $1/2$.

Now, by Corollary 6.7, for each Steiner point $s$, $P(s)$ corresponds to an
independent set in $G$. Since each edge in the graph is length $1/2$, the cost
of the tree is $(n+|X|)/2$, where $X$ is the set of Steiner points in the
tree. Since each nonzero terminal is adjacent to a Steiner point, by Corollary
6.7, $T$ must have at least $\chi(G)$ Steiner points. But, the construction in
the completeness case shows a tree with $\chi(G)$ Steiner points and this
structure is possible (adding the intermediate Steiner points for edges
directly to $\mathbf{0}$), implying the result. ∎

This completes the proof of the soundness case of Theorem 6.1.

## Acknowledgement

We would like to thank Fabrizio Grandoni for discussion about $\mathsf{DST}$.

## References

  * [ABC+21] Amir Abboud, Mohammad Hossein Bateni, Vincent Cohen-Addad, Karthik C. S., and Saeed Seddighin.  On complexity of 1-center in various metrics.  CoRR, abs/2112.03222, 2021.
  * [ANSW20] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and Euclidean k-median by primal-dual algorithms.  SIAM J. Comput., 49(4), 2020.
  * [Aro98] Sanjeev Arora.  Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.  Journal of the ACM, 45(5):753–782, Sep 1998.
  * [BG21] Yair Bartal and Lee-Ad Gottlieb.  Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, page 1028–1041, Virtual Italy, Jun 2021. ACM.
  * [BGRS13] Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità.  Steiner tree approximation via iterative randomized rounding.  Journal of the ACM (JACM), 60(1):1–33, 2013.
  * [BGTZ14] Marcus Brazil, Ronald L. Graham, Doreen A. Thomas, and Martin Zachariasen.  On the history of the Euclidean Steiner tree problem.  Archive for history of exact sciences, 68(3):327–354, 2014.
  * [BPR+17] Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh.  An improved approximation for k-median and positive correlation in budgeted optimization.  ACM Transactions on Algorithms (TALG), 13(2):1–31, 2017.
  * [BRK+12] Christina Backes, Alexander Rurainski, Gunnar W. Klau, Oliver Müller, Daniel Stöckel, Andreas Gerasch, Jan Küntzer, Daniela Maisel, Nicole Ludwig, Matthias Hein, et al.  An integer linear programming approach for finding deregulated subgraphs in regulatory networks.  Nucleic acids research, 40(6):e43–e43, 2012.
  * [CC06] Miroslav Chlebík and Janka Chlebíková.  Complexity of approximating bounded variants of optimization problems.  Theoretical Computer Science, 354(3):320–338, 2006.
  * [CC08] Miroslav Chlebík and Janka Chlebíková.  The Steiner tree problem on graphs: Inapproximability results.  Theoretical Computer Science, 406(3):207–214, 2008.
  * [CD13] Xiuzhen Cheng and Ding-Zhu Du.  Steiner trees in industry, volume 11.  Springer Science & Business Media, 2013.
  * [CDV11] Deeparnab Chakrabarty, Nikhil R. Devanur, and Vijay V. Vazirani.  New geometry-inspired relaxations and algorithms for the metric steiner tree problem.  Mathematical Programming, 130(1):1–32, Nov 2011.
  * [CFF+08] Márcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Carlos A. J. Martinhon, Fábio Protti, and Bruce Reed.  Partition into cliques for cubic graphs: Planar case, complexity and approximation.  Discrete Applied Mathematics, 156(12):2270–2278, 2008.
  * [CG76] Fan R. K. Chung and Edgar N. Gilbert.  Steiner trees for the regular simplex.  Steiner Trees for the Regular Simplex, 4(2):313–325, 1976.
  * [CG85] F. R. K. Chung and R. L. Graham.  A new bound for Euclidean Steiner minimal trees.  Annals of the New York Academy of Sciences, 440(1 Discrete Geom):328–346, May 1985.
  * [Cho01] Jun-Dong Cho.  Steiner tree problems in VLSI layout designs.  In Steiner Trees in Industry, pages 101–173. Springer, 2001.
  * [CK19] Vincent Cohen-Addad and Karthik C. S.  Inapproximability of clustering in Lp metrics.  In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 519–539. IEEE Computer Society, 2019.
  * [CKL21] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  On approximability of clustering problems without candidate centers.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 2635–2648. SIAM, 2021.
  * [CKL22] Vincent Cohen-Addad, Karthik C. S., and Euiwoong Lee.  Johnson coverage hypothesis: Inapproximability of k-means and k-median in $\ell_{p}$-metrics.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1493–1530. SIAM, 2022.
  * [CNS22] Deeparnab Chakrabarty, Maryam Negahbani, and Ankita Sarkar.  Approximation algorithms for continuous clustering and facility location problems.  In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, volume 244 of LIPIcs, pages 33:1–33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [DJS86] William H. E. Day, David S. Johnson, and David Sankoff.  The computational complexity of inferring rooted phylogenies by parsimony.  Mathematical Biosciences, 81(1):33–42, 1986.
  * [DS96] Ding-Zhu Du and Warren D. Smith.  Disproofs of Generalized Gilbert–Pollak Conjecture on the Steiner Ratio in Three or More Dimensions.  Journal of Combinatorial Theory, Series A, 74(1):115–130, 1996\.
  * [DWLX11] Hai Du, Weili Wu, Zaixin Lu, and Yinfeng Xu.  On the steiner ratio in $\mathcal{R}_{n}$.  Discrete Mathematics, Algorithms and Applications, 03(04):473–489, Dec 2011.
  * [FG82] Les R. Foulds and Ronald L. Graham.  The Steiner problem in phylogeny is NP-complete.  Advances in Applied mathematics, 3(1):43–49, 1982.
  * [GGJ77] Michael R. Garey, Ronald L. Graham, and David S. Johnson.  The complexity of computing Steiner minimal trees.  SIAM Journal on Applied Mathematics, 32(4):835–859, 1977.
  * [GJ77] Michael R. Garey and David S. Johnson.  The rectilinear Steiner tree problem is $np$-complete.  SIAM Journal on Applied Mathematics, 32(4):826–834, 1977.
  * [GP68] Edgar N. Gilbert and Henry O. Pollak.  Steiner minimal trees.  SIAM Journal on Applied Mathematics, 16(1):1–29, 1968.
  * [GS96] Arnaldo Garcia and Henning Stichtenoth.  On the asymptotic behaviour of some towers of function fields over finite fields.  Journal of Number Theory, 61(2):248–273, Dec 1996.
  * [Han66] Maurice Hanan.  On Steiner’s problem with rectilinear distance.  SIAM Journal on Applied Mathematics, 14(2):255–265, 1966.
  * [HR92] Frank K. Hwang and Dana S. Richards.  Steiner tree problems.  Networks, 22(1):55–89, 1992.
  * [IOSS02] Trey Ideker, Owen Ozier, Benno Schwikowski, and Andrew F Siegel.  Discovering regulatory and signalling circuits in molecular interaction networks.  Bioinformatics, 18(suppl_1):S233–S240, 2002.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-SAT.  J. Comput. Syst. Sci., 62(2):367–375, 2001.
  * [IPZ01] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.
  * [IT12] Alexandr O Ivanov and Alexey A Tuzhilin.  The steiner ratio gilbert–pollak conjecture is still open: Clarification statement.  Algorithmica, 62:630–632, 2012.
  * [Kar72] Richard M. Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.
  * [KZ97] Marek Karpinski and Alexander Zelikovsky.  New approximation algorithms for the Steiner tree problems.  Journal of Combinatorial Optimization, 1(1):47–65, 1997.
  * [Len12] Thomas Lengauer.  Combinatorial algorithms for integrated circuit layout.  Springer Science & Business Media, 2012.
  * [Lju21] Ivana Ljubić.  Solving Steiner trees: Recent advances, challenges, and perspectives.  Networks, 77(2):177–204, 2021.
  * [Mit99] 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.
  * [NRRK17] Mohammad Noormohammadpour, Cauligi S. Raghavendra, Sriram Rao, and Srikanth Kandula.  DCCast: Efficient point to multipoint transfers across datacenters.  In 9th USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 17), 2017.
  * [Pet94] Erez Petrank.  The hardness of approximation: Gap location.  Computational Complexity, 4(2):133–157, 1994.
  * [PS00] Hans Jürgen Prömel and Angelika Steger.  A new approximation algorithm for the Steiner tree problem with performance ratio 5/3.  Journal of Algorithms, 36(1):89–101, 2000.
  * [R0̈6] Harald Räcke.  Lecture 12 of Theory of Metric Embeddings.  https://home.ttic.edu/~harry/teaching/pdf/lecture12.pdf, Feb 2006\.
  * [RN10] Olga Russakovsky and Andrew Y. Ng.  A Steiner tree approach to efficient object detection.  In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1070–1077. IEEE, 2010.
  * [RP08] Mauricio G. C. Resende and Panos M. Pardalos.  Handbook of optimization in telecommunications.  Springer Science & Business Media, 2008.
  * [RS98] Satish Rao and Warren D. Smith.  Approximating geometrical graphs via “spanners” and “banyans”.  In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 540–550. ACM, 1998.
  * [Rub18] Aviad Rubinstein.  Hardness of approximate nearest neighbor search.  In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1260–1268. ACM, 2018.
  * [RZ05] Gabriel Robins and Alexander Zelikovsky.  Tighter bounds for graph Steiner tree approximation.  SIAM Journal on Discrete Mathematics, 19(1):122–134, 2005.
  * [SAK+01] K.W. Shum, I. Aleshnikov, P.V. Kumar, H. Stichtenoth, and V. Deolalikar.  A low-complexity algorithm for the construction of algebraic-geometric codes better than the gilbert-varshamov bound.  IEEE Transactions on Information Theory, 47(6):2225–2241, Sep 2001\.
  * [She12] Naveed A. Sherwani.  Algorithms for VLSI physical design automation.  Springer Science & Business Media, 2012.
  * [TGK+16] Nurcan Tuncbag, Sara J. C. Gosline, Amanda Kedaigle, Anthony R. Soltis, Anthony Gitter, and Ernest Fraenkel.  Network-based interpretation of diverse high-throughput datasets through the omics integrator software package.  PLoS computational biology, 12(4):e1004879, 2016.
  * [Tre00] Luca Trevisan.  When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree.  SIAM J. Comput., 30(2):475–485, 2000.
  * [Vaz01] Vijay V. Vazirani.  Approximation algorithms.  Springer, Berlin; New York, 2001.
  * [War95] H. Todd Wareham.  A Simplified Proof of the NP- and MAX SNP-Hardness of Multiple Sequence Tree Alignment.  Journal of Computational Biology, 2(4):509–514, 1995.
  * [Zel93] Alexander Z. Zelikovsky.  An 11/6-approximation algorithm for the network Steiner problem.  Algorithmica, 9(5):463–470, 1993.

##  Appendix A Explicit Gaps for $\mathsf{DST}$ in Specific $\ell_{p}$-metrics

In this section, we compute explicit hardness of approximation constants by
plugging in the best inapproximability results known for $\mathsf{SP_{3}}$ and
$\mathsf{VC}$ in literature.

###  A.1 Hardness of Approximation Bounds for Euclidean $\mathsf{DST}$

As the Euclidean metric is of particular importance, we explicitly state our
resultant hardness factor for $p=2$. In this special case, we can make do with
a somewhat weaker completeness case for $\mathsf{SP_{3}}$ than that in
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$. Instead we consider the decision
problem $(a,b)$-Gap $\mathsf{SP_{3}}$

######  Definition A.1 ($(a,b)$-Gap $\mathsf{SP_{3}}$).

Given a set system $([n],\mathcal{S})$ where for all $S\in\mathcal{S}$, we
have $|S|=3$, and $|\mathcal{S}|=m$, the $(a,b)$-Gap $\mathsf{SP_{3}}$ is the
problem of deciding which of the following cases hold.

  * •

Completeness: There exists a subcollection of $\mathcal{S}$ which are pairwise
disjoint and cover at least $(1-a)n$ elements in $[n]$.

  * •

Soundness: Any subcollection of pairwise disjoint sets of $\mathcal{S}$ cover
at most $(1-b)n$ elements in $[n]$.

Observe that $(\varepsilon,\varepsilon/2)$-$\mathsf{SP_{3}}$ is actually
$(1,1-\varepsilon)$-Gap $\mathsf{SP_{3}}$ since $\delta$ is unnecessary in
this formulation. Then, we have the following.

######  Corollary A.1.

Let $\varepsilon>0$. If $(1,1-\varepsilon)$-Gap $\mathsf{SP_{3}}$ is
$\mathsf{NP}$-hard then Euclidean $\mathsf{DST}$ is $\mathsf{NP}$-hard to
approximate within a factor of

$1+\frac{\varepsilon(9\sqrt{3}-15)}{15}\geq 1+0.039\varepsilon.$

More generally, if $(a,b)$-Gap $\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard, then
Euclidean $\mathsf{DST}$ is $\mathsf{NP}$-hard to approximate within a factor
of

$\frac{b(5\sqrt{3}/9-1)+1}{a(5\sqrt{3}/9-1)+1}.$

###### Proof.

For $p=2$, setting $\theta_{2}=1/6$ turns out to yield the maximum hardness of
approximation for embeddings of this kind (this can be verified graphically).
Note that $\theta_{2}=1/6$ satisfies the requirements of Theorem 5.2: the
first requirement is clear and the second follows from
$3\sqrt{3}/2+\sqrt{3}/6=\sqrt{3}(5/3)<3$. Then, substitute into Theorem 5.2
and observe that

$1<\beta_{\text{in}}+\alpha_{\text{X}}/2=\sqrt{3}/2+\sqrt{3}/12=7\sqrt{3}/12,$

as noted in Remark 5.2. This yields hardness of approximation within a factor
of

$1-\varepsilon+\frac{\varepsilon}{\sqrt{3}/2+\sqrt{3}/18}=1+\frac{9\sqrt{3}-15}{15}\cdot\varepsilon,$

proving the first part of the result.

The second part of the proof follows almost identically. We repeat almost the
same reduction as in Theorem 4.2. The soundness case is exactly identical and
the resultant Steiner tree then has cost at least

$b(\sqrt{3}/2+\sqrt{3}/18)+1-b=b(5\sqrt{3}/9-1)+1.$

In the completeness case, we no longer have that the sets partition the
universe. Let $C$ be a maximum packing of sets. For each $\\{i,j,k\\}\in C$,
connect $\mathbf{e_{i}}$, $\mathbf{e_{j}}$, and $\mathbf{e_{k}}$ to
$s=\Gamma^{-1}(\\{i,j,k\\})$ (following the notation of Section 4). Then
connect $s$ to $\mathbf{0}$. For the terminals corresponding to universe
elements that are not covered by the sets in $C$, we connect those terminals
directly to $\mathbf{0}$. This incurs costs $a(5\sqrt{3}/9-1)+1$. Taking the
ratio in the two cases then yields the desired result. ∎

The below hardness of $(a,b)$-$\mathsf{SP_{3}}$ is known.

######  Theorem A.2 ([CC06]).

We have $(0.979,0.969)$-Gap $\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard.

In [CC06], they prove the hardness of the Max Independent Set problem on
$3$-regular graphs, a special case of $\mathsf{SP_{3}}$. The fact that this is
a special case is clear by considering the set of incident edges to each
vertex as a set in the set-system and the set of all edges in the graph as the
universe of elements.666The explicit bounds here comes from a combination of
places in [CC06]: we use Theorem 16 for the bound on $\mu_{3,k}$, the
assumption at the beginning of Theorem 17 for bounding $M(H)/k$ by
$\mu_{3,k}+o(1)$, the $\mathsf{NP}$-hard decision problem formulation of Max
Independent Set stated in the proof of Theorem 17 for our two cases, and the
property $|V(H)|=2M(H)$ used to prove Corollary 18 to apply the bound on
$M(H)/k$ . Applying this to Corollary A.1 we have the following.

######  Corollary A.3.

Euclidean $\mathsf{DST}$ is $\mathsf{NP}$-hard to approximate within a factor
of 1.00039.

###  A.2 Hardness of Approximation Bounds for Hamming and Rectilinear
$\mathsf{DST}$

The general embedding described in Section 5.1 notably fails for $p=1$.
However, a simple reduction from $\mathsf{VC}$ yields reasonable hardness of
approximation bounds. We simultaneously get the same hardness for Hamming
($\ell_{0}$) $\mathsf{DST}$.

We will make use of the following theorem.

######  Theorem A.4 ([CC06]).

$(0.52025,0.53036)$-$\mathsf{VC}$ is $\mathsf{NP}$-hard on $4$-regular graphs.

We show the following.

######  Theorem A.5.

Suppose that $(a,b)$-$\mathsf{VC}$ is $\mathsf{NP}$-hard on max degree
$\Delta$ graphs. Then $\mathsf{DST}$ in both the $\ell_{0}$ and $\ell_{1}$
metrics is $\mathsf{NP}$-hard to approximate within a factor of
$\frac{\Delta/2+b}{\Delta/2+a}$.

###### Proof.

The proof is exactly the same as the reduction from Set Cover to
$\mathsf{DST}$ given in Section 1.2. Interpret the instance of $\mathsf{VC}$
as an instance of Set Cover with universe elements being edges and sets being
the sets of incident edges to vertices. We can embed the graph used in the
reduction in $\mathbb{R}^{n}$ under the $\ell_{0}$ and $\ell_{1}$ metrics by
mapping the “additional vertex” to $\mathbf{0}$, the edges to their
characteristic vectors (of Hamming weight 2), and each set of edges incident
to a vertex to the characteristic vector of that vertex (of Hamming weight 1).
∎

Then, using Theorem A.4, we have the following result.

######  Theorem A.6.

We have that $\mathsf{DST}$ in both the $\ell_{0}$ and $\ell_{1}$ metrics is
$\mathsf{NP}$-hard to approximate within a factor of 1.004.

##  Appendix B String Metrics

In this section, we show how $\mathsf{APX}$-hardness of $\mathsf{DST}$ in the
Hamming metric implies $\mathsf{APX}$-hardness of $\mathsf{DST}$ in the Ulam
and edit metrics, using known near-isometric embeddings. Let $\Sigma$ be an
alphabet and $\Sigma^{*}$ be the set of strings over the alphabet $\Sigma$.
Then let $\operatorname{ED}:\Sigma^{*}\times\Sigma^{*}\to\mathbb{R}$, the edit
distance between strings. That is, the minimum number of single character
deletions, insertions, and substitutions required to modify one string into
the other. The Ulam metric $\operatorname{UD}$ is the same edit distance
except with input strings restricted to those without repeated characters.

###  B.1 Ulam Metric

In [ABC+21], they show that there exists an embedding of $n$-dimensional
Hamming space into the set of permutations of $[n]$ under the Ulam metric such
that all pairwise distances are exactly scaled by a factor of $2$.

######  Lemma B.1 (Lemma 4.5 of [ABC+21]).

Let $\Pi_{n}$ denote the set of permutations of $[n]$. There is a function
$\eta:\\{0,1\\}^{n}\to\Pi_{n}$, such that, for all $x,y\in\\{0,1\\}^{n}$, we
have

$\operatorname{ed}(\eta(x),\eta(y))=2\left\lVert x-y\right\rVert_{0}.$

Moreover, for all $x\in\\{0,1\\}^{n}$, $\eta(x)$ can be computed in $O(n)$
time.

Then, given a hard instance $(P,X)$ of Hamming $\mathsf{DST}$, consider
$(\eta(P),\eta(X))$ as an instance of $\mathsf{DST}$ in the Ulam metric. In
particular, there is a one-to-one correspondence between Steiner trees in the
two instances and their costs are exactly scaled by $2$. So, hardness is
exactly scaled by $2$ (using that $\eta(x)$ can be computed in $O(n)$ time).
Hence, we have the following.

######  Corollary B.2.

$\mathsf{DST}$ in the Ulam metric is $\mathsf{APX}$-hard.

###  B.2 Edit Metric

In [Rub18], Rubinstein shows a near-isometric embedding of Hamming space into
the space of binary strings under the edit metric. We use an explicit
formulation given in Lemma A.1 of [CK19].

######  Lemma B.3 ([Rub18]).

For large enough $d$, there exists a function
$\eta:\\{0,1\\}^{d}\to\\{0,1\\}^{d^{\prime}}$, where $d^{\prime}=O(d\log d)$
such that for all $a,b\in\\{0,1\\}^{d}$, we have

$|\operatorname{ED}(\eta(a),\eta(b))-c\cdot\log d\cdot\left\lVert
a-b\right\rVert_{0}|=o(d^{\prime}),$

for some constant $c$. Moreover, for any $a\in\\{0,1\\}^{d}$, $\eta(a)$ can be
computed in $2^{o(d)}$ time.

First, we use the fact that Hamming $\mathsf{DST}$ is $\mathsf{APX}$-hard in
$O(\log n)$ dimensions. This follows from Theorem C.1 in Section C. Then,
given an instance $(P,X)$ of Hamming $\mathsf{DST}$ in $O(\log n)$ dimensions,
for $n$ large enough, consider instance $(\eta(P),\eta(X))$ of
$\operatorname{ED}$ $\mathsf{DST}$ (with $\eta$ the function from Lemma B.3).
This is computable in $\operatorname{poly}(n)$ time by Lemma B.3.

Now, observe that the cost of optimal Steiner trees must be $\Omega(n)$ in
both the completeness and soundness cases of Hamming $\mathsf{DST}$ (since the
minimum distance between any two points is $1$). Now, let $T$ be a Steiner
tree of $(P,X)$. By Lemma B.3, the corresponding Steiner tree of
$(\eta(P),\eta(X))$ costs at most $c\cdot\log\log
n\cdot\operatorname{\mathsf{cost}}_{0}(T)+o(\log n\log\log n)$ and at least
$c\cdot\log\log n\cdot\operatorname{\mathsf{cost}}_{0}(T)-o(\log n\log\log
n)$. Then, since $\operatorname{\mathsf{cost}}_{0}(T)=\Omega(n)$ the ratio of
the bounds on the costs of optimal trees in the soundness and completeness
cases of the $\operatorname{ED}$ $\mathsf{DST}$ are preserved for sufficiently
large $n$ since the $\Omega(n)$ term dominates the $o(\log n\log\log n)$ term.
Hence, since there is a constant gap for Hamming $\mathsf{DST}$, there is a
constant gap for $\operatorname{ED}$ $\mathsf{DST}$. We have the following.

######  Corollary B.4.

$\mathsf{DST}$ in the edit metric is $\mathsf{APX}$-hard.

##  Appendix C Inapproximability in Low Dimensions

In Section 5.1, we describe gap-preserving reduction from
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ to $\mathsf{DST}$ in $n$-dimensional
$\ell_{p}$-metric spaces. In this section, we show that this reduction can be
extended to a configuration of $n$ points in an $O(\log n)$-dimensional
$\ell_{p}$-metric space (for constant $p$) via a near-isometric embedding from
[CK19, CKL22]. For the dimensionality reduction for $p=\infty$, refer to
[CK19]. This will show that $\mathsf{DST}$ in the $\ell_{p}$-metric is
$\mathsf{APX}$-hard even in $O(\log n)$-dimensions (and essentially preserve
the hardness of approximation). In the below, let $\operatorname{supp}(x)$ be
the set of nonzero coordinates of $x$ (the support of $x$).

######  Theorem C.1 (Essentially [CK19, CKL22]).

Let $\varepsilon>0$, $B,C\in\mathbb{Z}^{+}$, and $p\in\mathbb{R}_{\geq 1}$.
Let $P\subset\mathbb{R}^{n}$ such that $|P|=n$ and, for all $x\in P$,
$\operatorname{supp}(x)\subseteq[n]$ with $|\operatorname{supp}(x)|\leq C$ and
$\left\lVert x\right\rVert_{\infty}\leq B$. Then, there exists
$\alpha=O_{C,B,\varepsilon}(1/\log n)$ and
$\sigma:\mathbb{R}^{n}\to\mathbb{R}^{O_{C,B,\varepsilon}(\log n)}$ such that,
for all $x,y\in P$,

$(1-\varepsilon)\left\lVert
x-y\right\rVert_{p}^{p}\leq\alpha\left\lVert\sigma(x)-\sigma(y)\right\rVert_{p}^{p}\leq(1+\varepsilon)\left\lVert
x-y\right\rVert_{p}^{p}.$

Additionally, for all $x\in P$, $\sigma(x)$ is computable in
$\operatorname{poly}(n)$ time.

Note that all points in instances of $\mathsf{DST}$ in Section 5.1 have
support of size at most $3$. Hence, Theorem C.1 applies. Hence, for a fixed
$p$ and any $\varepsilon>0$, there exists an instance of $\mathsf{DST}$ in the
$\ell_{p}$-metric in $O(\log n)$ dimensions with all pairwise distances within
an arbitrarily small factor of the original distances in $n$ dimensions (after
scaling the configuration by $\alpha^{1/p}$). Therefore, the cost of the trees
in the completeness and soundness cases change by at most that factor and we
get hardness of approximation within an arbitrarily small factor of the
original hardness.

To prove Theorem C.1, we use the existence of codes from algebraic geometry.

######  Theorem C.2 (Existence of AG codes, [GS96, SAK+01]).

Let $q$ be a prime squared at least $49$. Then, there exists a linear map
$\mathcal{C}:\mathbb{F}_{q}^{\log_{q}n}\to\mathbb{F}_{q}^{c\log_{q}n}$ for
some constant $c$, such that for all $x,y\in\mathbb{F}_{q}^{\log_{q}n}$ we
have

$\|\mathcal{C}(x)-\mathcal{C}(y)\|_{0}\geq(1-3/\sqrt{q})(c\log_{q}n).$

To define the map $\sigma:\mathbb{R}^{n}\to\mathbb{R}^{O(\log n)}$ for Theorem
C.1, we first describe the map on $\\{0,1\\}^{n}_{1}\subset\mathbb{R}^{n}$,
the set of vectors of Hamming weight $1$ (the standard basis vectors). Let $q$
be a squared prime at least $49$ (we will specify $q$ appropriately later).
Given $i\in n$, map it bijectively to an element
$x\in\mathbb{F}_{q}^{\log_{q}n}$ (by enumerating the elements of
$\mathbb{F}_{q}^{\log_{q}n})$. Call this map $f_{1}$. Let $\mathcal{C}$ be the
linear map existing from Theorem C.2. Then, apply $\mathcal{C}$ to $x$ to
yield an element of $\mathbb{F}_{q}^{c\log_{q}n}$. Finally, enumerate the
elements of $\mathbb{F}_{q}$ from $1$ to $q$ and map $\mathcal{C}(f_{1}(x))$
to $\\{0,1\\}^{qc\log_{q}n}$ by interpreting $\mathcal{C}(f_{1}(x))$ as
$c\log_{q}n$ blocks of $q$ zeroes and ones, $q-1$ of which being $0$ and the
$1$ indicating the number of the element from $\mathbb{F}_{q}$. Call this map
$f_{2}$. For example, $(3,1,2)\in\mathbb{F}_{5}^{3}$ would be mapped to the
bitstring $000100100000100\in\\{0,1\\}^{15}$. We interpret this bitstring in
$\\{0,1\\}^{qc\log_{q}n}$ as a vector in $\mathbb{R}^{qc\log_{q}n}$ by the
natural inclusion map. Call this map $f_{3}$. Formally, $\sigma=f_{3}\circ
f_{2}\circ\mathcal{C}\circ f_{1}$ for inputs in $\\{0,1\\}^{n}_{1}$. To extend
$\sigma$ to the rest of $\mathbb{R}^{n}$, we define

$\sigma\left(\sum_{i=1}^{n}a_{i}\mathbf{e}_{i}\right)=\sum_{j=1}^{qc\log_{q}n}\begin{cases}a_{i}\cdot\mathbf{e}_{j}&\text{if
}|\\{i\in[n]\,:\,a_{i}\sigma(\mathbf{e}_{i})_{j}\neq 0\\}|=1,\\\
0&\text{otherwise}.\end{cases}$

Intuitively, given the large minimum distance between codewords from Theorem
C.2 and the bounded support of point configurations in Theorem C.1, for most
$j\in[qc\log_{q}n]$,
$|\\{i\in[n]\,:\,\sigma(\mathbf{e}_{i})_{j}=1\\}|\in\\{0,1\\}$.

Now, let $\varepsilon,C$, $B$, $p$, and $P$ be as in Theorem C.1. Fix $x,y\in
P$. Let $x=\sum_{i\in I_{1}}x_{i}\mathbf{e}_{i}$ and $y=\sum_{i\in
I_{2}}y_{i}\mathbf{e}_{i}$, where $|I_{1}|,|I_{2}|\leq C$. Fix $i\in I_{1}$.
Consider the set of nonzero coordinates on which $\sigma(\mathbf{e}_{i})$ does
not overlap with $\sigma(\mathbf{e}_{j})$ for $i\neq j\in I_{1}\cup I_{2}$.
The contribution of each such coordinate $k$ to
$\left\lVert\sigma(x)-\sigma(y)\right\rVert_{p}^{p}$ is exactly
$|x_{i}-y_{i}|^{p}$.

By Theorem C.2,
$\left\lVert\mathcal{C}(f_{1}(\mathbf{e}_{i}))-\mathcal{C}(f_{1}(\mathbf{e}_{j}))\right\rVert_{0}\geq(1-3/\sqrt{q})c\log_{q}n$
for each $i\neq j\in[n]$. Then, since the map $f_{2}$ exactly doubles Hamming
distance and $f_{3}$ preserves Hamming distance,
$\left\lVert\sigma(\mathbf{e}_{i})-\sigma(\mathbf{e}_{j})\right\rVert_{0}\geq(1-3/\sqrt{q})2c\log_{q}n$.
In particular, since $\left\lVert\sigma(\mathbf{e}_{i})\right\rVert_{0}$ is
exactly $c\log_{q}n$, this implies that $\sigma(\mathbf{e}_{i})$ and
$\sigma(\mathbf{e}_{j})$ can overlap on at most $(3/\sqrt{q})c\log_{q}n$
nonzero coordinates. Moreover, $\sigma(\mathbf{e}_{i})$ can overlap on at most
$(6C/\sqrt{q})c\log_{q}n$ total nonzero coordinates with
$\sigma(\mathbf{e}_{j})$ for $i\neq j\in I$. The maximum contribution of these
overlapping coordinates is $B^{p}$ (if, for example, $\sigma(e_{i})$ overlaps
with $\sigma(e_{i^{\prime}})$ for $i^{\prime}\in I_{1}$ but doesn’t overlap
with any mapped standard basis vector from $I_{2}$ and $a_{i}=B$). The minimum
contribution is $0$. Then, we have

$(1-6C/\sqrt{q})c\log_{q}n\left\lVert
x-y\right\rVert_{p}^{p}\leq\left\lVert\sigma(x)-\sigma(y)\right\rVert_{p}^{p}\leq
c\log_{q}n\left\lVert x-y\right\rVert_{p}^{p}+(6C/\sqrt{q})B^{p}c\log_{q}n.$

Setting $q$ sufficiently large then yields Theorem C.1.