# On Approximability of Steiner Tree in $\ell_{p}$-metrics

Henry Fleischmann111This work was supported by NSF grant CNS-2150186.
University of Michigan  Surya Teja Gavva
Rutgers University  Karthik C. S.222This work was supported by Rutgers
University’s Research Council Individual Fulcrum Award (#AWD00010234) and a
grant from the Simons Foundation, Grant Number 825876, Awardee Thu D. Nguyen.
Rutgers University

###### Abstract

In the Continuous Steiner Tree problem ($\mathsf{CST}$), we are given as input
a set of points (called _terminals_) in a metric space and ask for the
minimum-cost tree connecting them. Additional points (called _Steiner points_)
from the metric space can be introduced as nodes in the solution. In the
Discrete Steiner Tree problem ($\mathsf{DST}$), we are given in addition to
the terminals, a set of facilities, and any solution tree connecting the
terminals can only contain the Steiner points from this set of facilities.

Trevisan [SICOMP’00] showed that $\mathsf{CST}$ and $\mathsf{DST}$ are
$\mathsf{APX}$-hard when the input lies in the $\ell_{1}$-metric (and Hamming
metric). Chlebík and Chlebíková [TCS’08] showed that $\mathsf{DST}$ is
$\mathsf{NP}$-hard to approximate to factor of $96/95\approx 1.01$ in the
graph metric (and consequently $\ell_{\infty}$-metric). Prior to this work, it
was unclear if $\mathsf{CST}$ and $\mathsf{DST}$ are $\mathsf{APX}$-hard in
essentially every other popular metric!

In this work, we prove that $\mathsf{DST}$ is $\mathsf{APX}$-hard in every
$\ell_{p}$-metric. We also prove that $\mathsf{CST}$ is $\mathsf{APX}$-hard in
the $\ell_{\infty}$-metric. Finally, we relate $\mathsf{CST}$ and
$\mathsf{DST}$, showing a general reduction from $\mathsf{CST}$ to
$\mathsf{DST}$ in $\ell_{p}$-metrics. As an immediate consequence, this yields
a $1.39$-approximation polynomial time algorithm for $\mathsf{CST}$ in
$\ell_{p}$-metrics.

It is known that the $\mathsf{APX}$-hardness of $\mathsf{DST}$ in
$\ell_{0},\ell_{1}$, and $\ell_{\infty}$-metrics can be obtained from the
$\mathsf{APX}$-hardness of covering problems (with additional structure). Our
main conceptual insight is that for certain ranges of $p$ (such as $p=2$), the
soundness guarantees of covering problems might be insufficient to show that
$\mathsf{DST}$ in the $\ell_{p}$-metric is $\mathsf{APX}$-hard, but the
soundness guarantees of a packing problem (with requisite additional
structure) is enough. Equipped with this insight, we are then able to embed
set systems into every $\ell_{p}$-metric, and, depending on the value of $p$,
our soundness analysis of the corresponding $\mathsf{DST}$ instance in the
$\ell_{p}$-metric will use either the packing property or the covering
property (or both) of the set system in the soundness case.

Due to the discrete structure of the Hamming space, the
$\mathsf{APX}$-hardness of $\mathsf{CST}$ in the $\ell_{0}$ and $\ell_{1}$
metrics follow from similar methods. However, these techniques do not extend
to $\mathsf{CST}$ in other $\ell_{p}$-metrics. To show $\mathsf{APX}$-hardness
of $\mathsf{CST}$ in the $\ell_{\infty}$-metric, we instead rely on the robust
hardness guarantees of graph coloring problems. Concretely, we present a
reduction from a graph $G$ on $n$ vertices to a point-set $P$ in the
$\ell_{\infty}$-metric space, where the cost of the optimal Steiner tree of
$P$ is exactly $\frac{n+\chi(G)}{2}$, where $\chi(G)$ is the chromatic number
of $G$.

##  1 Introduction

Given a set of points (called _terminals_) in a metric space, a _Steiner tree_
is defined to be a minimum length tree connecting them, with the tree possibly
including additional points (called _Steiner_ points) as nodes. Computing the
Steiner tree is one of the classic and most fundamental problems in Computer
Science, Combinatorial Optimization, and Operations Research, with both great
theoretical and practical relevance and interest [Lju21]. This problem emerges
in a number of contexts, such as network design problems, design of integrated
circuits, location problems [CD13, Cho01, HR92, Len12, RP08, NRRK17] and more
recently even in machine learning, systems biology, and bioinformatics
[BRK+12, IOSS02, RN10, TGK+16]. For example, in VLSI circuits, wire routing is
carried out by wires running only in vertical and horizontal directions, due
to high computational complexity of the task. Therefore, the wire length is
the sum of the lengths of vertical and horizontal segments, and the distance
between two pins of a net is actually the $\ell_{1}$-metric distance between
the corresponding geometric points in the design plane [She12].

Formally, the Steiner tree problem can be formulated in two ways: discrete and
continuous. In the Discrete Steiner Tree problem ($\mathsf{DST}$), we are
given as input two sets of points in a metric space, called _terminals_ and
_facilities_ respectively. The goal is to find the minimum-cost tree
connecting the terminals, possibly introducing new points (_Steiner_ points)
from the set of facilities as nodes in the solution. In the Continuous Steiner
Tree problem ($\mathsf{CST}$), we are only given a set of terminals as input,
and we are allowed to use any point in the metric space as a Steiner point in
the Steiner tree connecting all the terminals.

#### General Metrics.

In general metrics, where the metric space is specified as part of the input
(for example, by specifying all pairwise distances), it does not make sense to
discuss the $\mathsf{CST}$ problem, so we restrict our attention to
$\mathsf{DST}$. The Steiner tree problem is one of Karp’s 21
$\mathsf{NP}$-complete problems, i.e., in his seminal work [Kar72], Karp
showed that $\mathsf{DST}$ is $\mathsf{NP}$-complete. Therefore, the attention
of the algorithmic community turned towards obtaining good approximation
algorithms for $\mathsf{DST}$ in general metrics. It is well-known that a
minimum-cost tree only containing the terminals as nodes is a 2-approximation
for $\mathsf{DST}$ (and $\mathsf{CST}$) [GP68, Vaz01].

A sequence of improved approximation algorithms for $\mathsf{DST}$ in general
metrics appeared in the literature [Zel93, KZ97, PS00, RZ05], culminating with
the famous $\ln(4)+\varepsilon<1.39$ factor approximation algorithm by Byrka,
Grandoni, Rothvoß, and Sanitá [BGRS13] (where $\varepsilon>0$ is an
arbitrarily small constant). On the hardness of approximation front, Chlebík
and Chlebíková [CC08] showed that $\mathsf{DST}$ in general metrics is hard to
approximate to a factor of $\frac{96}{95}>1.01$. Thus, there is still quite a
substantial gap in our understanding of the approximability of $\mathsf{DST}$
in general metrics.

######  Open Question 1.

What is the tight inapproximability ratio of $\mathsf{DST}$ in general
metrics?

#### Geometric Metrics.

Special cases of $\mathsf{CST}$ in Euclidean metric were studied by Fermat,
Torricelli and other mathematicians in as early as the
$17\textsuperscript{th}$ century and were also discussed in a letter from
Gauss to Schumacher in 1836 (see [BGTZ14] for more details on the history of
this problem). On the other hand, phylogeny reconstruction is a long-standing
(dating from Darwin’s evolutionary theory) and intensively studied problem in
computational biology, and computing the phylogenetic tree is essentially
equivalent to solving $\mathsf{CST}$ in the Hamming metric [FG82]. We have
already discussed the importance of $\mathsf{CST}$ in the $\ell_{1}$-metric in
VLSI design. Therefore, there has been a lot of interest in understanding the
complexity of $\mathsf{CST}$ in $\ell_{p}$-metrics.

Garey, Graham, and Johnson showed that Euclidean $\mathsf{CST}$ is
$\mathsf{NP}$-hard, even in the plane [GGJ77]. Garey and Johnson also showed
$\mathsf{NP}$-hardness of $\mathsf{CST}$ in the $\ell_{1}$-metric [GJ77] (also
in the plane). Foulds and Graham extended this further, showing
$\mathsf{NP}$-hardness $\mathsf{CST}$ in the Hamming metric [FG82]. These
intractability results lead to the search for efficient approximation
algorithms.

In a remarkable series of works, a $\mathsf{PTAS}$ was established for
$\mathsf{CST}$ in $\ell_{1}$ and $\ell_{2}$-metrics in constant dimensions
(indeed, Arora’s $\mathsf{PTAS}$ extends to all $\ell_{p}$-metrics) [Aro98,
Mit99, RS98]. However, it was unclear if $\mathsf{CST}$ in $\ell_{1}$ and
$\ell_{2}$-metrics in high dimensions333By high dimensions, we simply refer to
a regime where the dimension is at least logarithmic in the number of input
points. admitted a $\mathsf{PTAS}$. Trevisan [Tre00] answered this question in
the negative for the $\ell_{1}$-metric, by showing that $\mathsf{CST}$ in
$\ell_{1}$-metric is $\mathsf{APX}$-hard [CDV11, Han66, DJS86, War95]. He left
it as an open problem to show a similar hardness for the (arguably more
important) Euclidean $\mathsf{CST}$ in high dimensions.

######  Open Question 2.

Does Euclidean $\mathsf{CST}$ in high dimensions admit a $\mathsf{PTAS}$ or is
it $\mathsf{APX}$-hard?

If a geometric optimization problem is $\mathsf{APX}$-hard, it is often
easiest to establish that hardness in the $\ell_{\infty}$-metric. Intuitively,
this arises due to the existence of the Fréchet embedding, an isometric
embedding of discrete metric spaces into the $\ell_{\infty}$-metric. However,
it remained unknown whether high-dimensional $\mathsf{CST}$ in the
$\ell_{p}$-metric is $\mathsf{APX}$-hard for any $p>1$, including $p=\infty$.
Morally, we should not be able to understand hardness of approximation of
Euclidean $\mathsf{CST}$ until at least understanding the hardness of
approximation of $\mathsf{CST}$ in the $\ell_{\infty}$-metric.

######  Open Question 3.

Does high dimensional $\mathsf{CST}$ in the $\ell_{\infty}$-metric admit a
$\mathsf{PTAS}$ or is it $\mathsf{APX}$-hard?

We now shift our focus to $\mathsf{DST}$ in $\ell_{p}$-metrics. It is natural
to ask about the complexity of $\mathsf{DST}$ instances arising from pointsets
in $\ell_{p}$-metrics. Also, most approximation algorithms for $\mathsf{CST}$
in $\ell_{p}$-metric work by reducing them to an instance of $\mathsf{DST}$ in
$\ell_{p}$-metric (including, for example, Arora’s $\mathsf{PTAS}$ [Aro98]).
Therefore, from a hardness point-of-view, studying $\mathsf{DST}$ in
$\ell_{p}$-metrics can also be seen as a stepping stone to understanding
$\mathsf{CST}$ in $\ell_{p}$-metrics. For example, we can ask the following
discrete variant of Open Question 2.

######  Open Question 4.

Does Euclidean $\mathsf{DST}$ in high dimensions admit a $\mathsf{PTAS}$ or is
it $\mathsf{APX}$-hard?

We remark that exploring the discrete avenue to better understand the
continuous version has been pursued for another celebrated geometric problem:
_clustering_. The discrete and continuous versions of minimizing popular
clustering objectives such as $k$-means and $k$-median has been studied by the
theoretical computer science community extensively [BPR+17, ANSW20, CNS22,
CK19, CKL22].

###  1.1 Our results

Our first contribution is the resolution of Open Question 4. In fact, we prove
the $\mathsf{APX}$-hardness of $\mathsf{DST}$ for all $\ell_{p}$-metrics.

######  Theorem 1.1 (Informal version of Theorem 5.2).

Let $p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$. There is some constant
$\varepsilon>0$ such that $\mathsf{DST}$ is $\mathsf{NP}$-hard to approximate
to $(1+\varepsilon)$ factor in the $\ell_{p}$-metric. This holds even when the
dimension of the space containing the terminal set is logarithmic in the
number of terminals.

In fact, it is sufficient to prove that $\mathsf{DST}$ is $\mathsf{APX}$-hard
in the Euclidean metric, and then simply use the near isometric embedding of
$\ell_{2}$-metric to other $\ell_{p}$-metrics [R0̈6] to obtain that
$\mathsf{DST}$ is $\mathsf{APX}$-hard in every $\ell_{p}$-metric.

That said, our result is stronger than suggested in Theorem 1.1, in the
following sense. We provide our reduction from a hybrid variant of the set
cover and set packing problems (both restricted to the case when the input is
a collection of sets each of size exactly 3). Therefore, if and when the tight
inapproximability results for these problems on set systems are obtained, it
would immediately imply strong hardness of approximation factors for
$\mathsf{DST}$ in $\ell_{p}$-metrics (thus making progress on Open Question
1). For this reason, we explicitly compute inapproximability factors
throughout, even though the current known hardness of bounded set cover and
set packing yield very small constant factor inapproximability bounds.

Elaborating, our reduction is from the
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ problem, where given as input a
collection of sets $\mathcal{S}$ over universe $[n]$, we would like to
distinguish between the completeness case where there exists $n/3$ pairwise
disjoint sets in $\mathcal{S}$ that cover the whole universe $[n]$, and the
soundness case where every set cover of $[n]$ from $\mathcal{S}$ must be of
size at least $(1+\delta)(n/3)$ and every subcollection of pairwise disjoint
sets in $\mathcal{S}$ can cover at most a $(1-\varepsilon)$ fraction of the
universe. Note that if $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ problem is
$\mathsf{NP}$-hard then we may assume $\delta\in[\varepsilon/2,2\varepsilon]$
(see Remark 2.1 for an explanation).

We derive the following hardness of approximation factors, in terms of the
parameters of the reduction from $\mathsf{SP_{3}}$ to $\mathsf{DST}$, from our
proof of Theorem 5.2.

######  Theorem 1.2.

Let $p\in\mathbb{R}_{\geq 1}\cup\\{\infty\\}$. Assuming
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard, we have that
$\mathsf{DST}$ in $\ell_{p}$-metric is $\mathsf{NP}$-hard to approximate to
$(1+\gamma)$ factor, where

$\gamma:=\begin{cases}\delta/4&\text{ if }p=\infty\\\
\frac{\varepsilon}{2}\left(1-\frac{1}{3^{1/p}}\right)+2\delta\left(\frac{1}{2\cdot
3^{1/p}}-\frac{3}{8}\right)&\text{ if }p>1/\log_{3}(4/3)\\\
\varepsilon/8&\text{ if }p=1/\log_{3}(4/3)\approx 3.8\\\ \varepsilon/26&\text{
if }p\in[1,1/\log_{3}(4/3))\end{cases}$

We have only tried to optimize our reduction for $p=2$ and
$p>1/\log_{3}(4/3)\approx 3.8$, and, even then, we only optimize fully in the
case of $\delta=\varepsilon/2$. It is possible to obtain a better relationship
between $\varepsilon$, $\delta$, and $\gamma$ for
$p\in(1,1/\log_{3}(4/3))\setminus\\{2\\}$ by carefully analyzing the
constraints mentioned in Theorem 5.2.

In Figure 1, we capture the interplay between $\varepsilon,\delta,$ and
$\gamma$. The purple region indicates that, the between set packing and set
cover (actually vertex cover) problems, the reduction (i.e., embedding) of the
set system only goes through by starting from the covering problem and not
from the packing problem. The green region on the other hand is the exact
opposite, and the reduction of the set system to the $\mathsf{DST}$ only goes
through by starting from the packing problem and not from the covering
problem. In the yellow region, the behavior is unclear, in part because we did
not carefully analyze the dependency between $\varepsilon$ and $\delta$.
Finally, in the red region, we benefit from both the covering and packing
hardness. This is elaborated further in Section 5.2.

$\displaystyle\frac{1}{\log_{3}4\ -\ 1}\approx 3.819$$\displaystyle
1$$\displaystyle\infty$$\displaystyle 2$ Figure 1: Color-coded range of
$\ell_{p}$ hardness of approximation dependency on $\varepsilon$ and $\delta$.

Moreover, we note that we can derive explicit constants for the hardness of
approximation factors, and we do for $\mathsf{DST}$ in the Hamming
($\ell_{0}$), $\ell_{1},\ell_{2}$-metrics in Appendix A.

#### Dimensionality Reduction.

Our proof of Theorem 1.1 holds when the dimension of the pointset has linear
dependency in the size of the pointset. However, we can use the dimensionality
reduction technique introduced in [CK19] and generalized in [CKL22] to obtain
the same inapproximability result as in Theorem 1.1, even when the dimension
of the pointset has logarithmic dependency on the size of the pointset. We
discuss these dimensionality reduction details (for constant $p$) in Appendix
C. Assuming the _Exponential Time Hypothesis_ [IP01, IPZ01], the dimension
cannot be reduced much below logarithmic in size of pointset as the runtime of
the approximation scheme of [Aro98, Mit99, RS98] would then be running in
subexponential time.

#### String Metrics.

By applying the isometric embedding of the Hamming metric to the Ulam metric
(for example see Lemma 4.5 in [ABC+21]) we can prove $\mathsf{APX}$-hardness
for $\mathsf{DST}$ in the Ulam metric. Similarly, by applying the near-
isometric embedding of the Hamming metric to the edit metric (for example see
Section 4.1 in [Rub18]) we can prove $\mathsf{APX}$-hardness for
$\mathsf{DST}$ in the edit metric as well. See Appendix B for details.

Our second contribution is establishing the relative computational hardness of
$\mathsf{DST}$ and $\mathsf{CST}$. Although solving $\mathsf{DST}$ instances
is often used as a subroutine in algorithms for $\mathsf{CST}$, prior to this
work it was unclear whether solving $\mathsf{DST}$ problems was
computationally easier or harder in general. We show that $\mathsf{DST}$ is
essentially at least as hard as $\mathsf{CST}$.

######  Theorem 1.3 (Informal version of Theorem 3.1).

Let $p\in[1,\infty]$ and $\alpha>0$. If $\mathsf{CST}$ in the
$\ell_{p}$-metric is $\mathsf{NP}$-hard to approximate within a factor of
$(1+\alpha)$, then, for all $\varepsilon>0$, $\mathsf{DST}$ in the
$\ell_{p}$-metric is $\mathsf{NP}$-hard to approximate within a factor of
$(1+\alpha-\varepsilon)$.

We prove this by showing that we can efficiently compute a collection of
candidate Steiner points for a $\mathsf{DST}$ instance such that the optimal
tree for the $\mathsf{DST}$ instance is near-optimal for the corresponding
$\mathsf{CST}$ instance. Hence, efficient approximation algorithms for
$\mathsf{DST}$ yield similarly effective approximation algorithms for
$\mathsf{CST}$. Indeed, one consequence of this result is an improved
approximation algorithm for high-dimensional $\mathsf{CST}$ (see Corollary
3.4). The proof makes use of recent structural results about near-optimal
Steiner trees [BG21].

Our third contribution is the resolution of Open Question 3. In fact, our
result establishes a rather neat connection between chromatic number of a
graph and the cost of the resulting Steiner tree.

######  Theorem 1.4 (Informal version of Theorem 6.1 and Corollary 6.3).

There is a reduction from a graph $G$ of order $n$ to an instance of
$\mathsf{CST}$ in the $\ell_{\infty}$-metric such that the optimal cost of the
Steiner tree is $(n+\chi(G))/2$, where $\chi(G)$ is the chromatic number of
$G$. Consequently, $\mathsf{CST}$ in the $\ell_{\infty}$-metric is
$\mathsf{APX}$-hard.

We remark that our current hardness results are derived from the hardness of
graph coloring on graphs with linear chromatic number. Although the current
hardness is only enough to imply $\mathsf{APX}$-hardness of $\mathsf{CST}$ in
the $\ell_{\infty}$-metric, stronger inapproximability results for graph
coloring immediately translate to more robust results for $\mathsf{CST}$.

###  1.2 Our Techniques

In this subsection, we contextualize our techniques and provide a high level
description of our technical contributions. First, we discuss about the
techniques needed to prove Theorem 1.3.

#### Reduction from $\mathsf{CST}$ to $\mathsf{DST}$.

$\mathsf{CST}$ and $\mathsf{DST}$ have each independently garnered
considerable interest, but, prior to this work, the relative computational
hardness of the problems was unclear.444In fact, to the best of our knowledge,
the distinction between the discrete and continuous variants was never
formalized and systematically studied in the literature. On the one hand,
searching over a possibly uncountable collection of candidate Steiner points
in $\mathsf{CST}$ appears daunting. On the other hand, perhaps it is possible
to select collections of candidate Steiner points for $\mathsf{DST}$ that more
effectively emulate other computationally hard problems. However, as the other
side of the same coin, the continuous version allows the algorithm designer
the freedom to pick Steiner points anywhere in space, whereas the discrete
variant restricts the use of the geometry of the space by only allowing
Steiner points from the set of facilities.

These remarks also hold (in spirit) for other geometric optimization problems.
For a useful comparison, considering Clustering. Rather surprisingly, in
[CKL21], the authors showed that, in the $\ell_{\infty}$-metric space, the
continuous version of clustering is possibly harder than the discrete version.

In this paper we show in a sense the opposite is true for Steiner trees, i.e.,
we show that, up to an arbitrarily small factor, $\mathsf{DST}$ is at least as
hard to approximate as $\mathsf{CST}$ (see Theorem 1.3 above). The proof uses
a recent work by Bartal and Gottlieb [BG21] who show that there exist near-
optimal Steiner trees composed of optimal Steiner trees of constant size,
linked by edges between terminals. By embedding all small subsets of terminals
in low dimensional spaces and computing optimal Steiner trees using existing
$\mathsf{PTAS}$’s, we can then construct a set of candidate Steiner points for
$\mathsf{DST}$ (by unioning all of the Steiner points in the optimal Steiner
trees of these small subsets). Then, the optimal Steiner tree on the
$\mathsf{DST}$ instance approximates the cost of the Steiner tree on the
$\mathsf{CST}$ instance arbitrarily well. As a consequence, this yields the
best known approximation algorithm for high-dimensional $\mathsf{CST}$
(Corollary 3.4).

Next, we present the techniques needed to prove Theorems 1.1 and 1.2, by first
setting up the appropriate technical context.

#### Known Reductions from Set Cover and Vertex Cover.

The following is a gap-preserving reduction from Set Cover to $\mathsf{DST}$
in general metrics due to Karp [Kar72]. Given a set system
$([n],\mathcal{S})$, where $\mathcal{S}$ is a collection of $m$ subsets of
$[n]$, we construct a $\mathsf{DST}$ instance as follows. Our terminals will
be $[n]\cup\\{r\\}$ (a special root vertex is introduced). Our facilities will
be the subsets in $\mathcal{S}$. We connect each subset to $r$ and also have
edges between subsets/facilities and terminals/universe elements based on
their membership. The metric is simply the shortest path metric on the graph.
In the completeness case there is a set cover of size $k$, and that
corresponds to a Steiner tree of cost $n+k$. In the soundness case, if every
set cover of $[n]$ must be of size ($1+\delta)k$, (for some $\delta>0$), then
one can show that the Steiner tree cost is at least $n+k(1+\delta)$. By then
considering set systems where each set contains exactly 3 elements and in
which the set cover is a partition in the completeness case, we obtain
$k=n/3$, and thus $\mathsf{DST}$ is hard to approximate to $(1+\delta/4)$
factor.

To obtain $\mathsf{APX}$-hardness for $\mathsf{DST}$ in the Hamming (or
$\ell_{1}$) metric, we can simply start from a special set system, namely the
vertex cover problem on cubic graphs, and then embed them into the Hamming
space as follows. Given a vertex cover instance, $G(V,E)$, our facilities are
$\mathbf{e}_{1},\ldots,\mathbf{e}_{|V|}$, and for every edge $(u,v)$ we have
the terminal $\mathbf{e}_{u}+\mathbf{e}_{v}$ (where $\mathbf{e}_{i}$ is a
standard basis vector). We have a special additional terminal (much like the
reduction from set cover problem) which is the all-zeroes vector. The
completeness and soundness case go through like in the set cover instance,
although some care needs to be taken in the completeness case. In particular,
we cannot assume that the minimum vertex cover forms an independent set in the
completeness case as the problem of deciding whether that is the case is in P.

We can then try to similarly reduce from vertex cover to $\mathsf{DST}$ in the
Euclidean metric, but the reduction fails in a suggestive manner. Consider
using the same choice of facilities and terminals as in the Hamming case.
Given a vertex cover of size $k$, there is a Steiner tree of cost $m+k$ where
we choose the facilities corresponding to the vertices in the vertex cover.
Each non-root terminal is a leaf node connected either to a facility at
distance $1$ or directly to the all-zeroes vector. Each facility is then
connected to the all-zeroes vector.

However, unlike in the Hamming metric, such a Steiner tree might be far from
optimal. Crucially, if a facility is adjacent to two non-root terminals, it is
also more efficient to connect each of those adjacent terminals directly to
the all-zeroes vector, incurring a saving of $3-2\sqrt{2}$ in the Steiner tree
cost.

It is relatively straightforward to show that there are minimal cost Steiner
trees in which all non-root terminals are leaf nodes and either adjacent to a
facility of maximum degree or the all-zeroes vector. This is notably the same
as the construction outlined above upon removing facilities adjacent to two
non-root terminals. However, the minimum cost of a Steiner tree on these
facilities and terminals no longer only depends on the minimum size of a
vertex cover in $G$. Instead, the cost of the Steiner tree is minimized by
finding a maximum independent set, then taking the corresponding Steiner
points, and connecting all terminals corresponding to edges not incident to
the independent set directly to the all-zeroes vector. Our reduction from
minimum vertex cover naturally transformed into a reduction from maximum
independent set!

Importantly, when we consider this reduction for even larger $p$, larger than
around $p\approx 2.409$, the Steiner points lose all of their utility and even
facilities adjacent to three non-root terminals do not help reduce the cost.
By using a more robust reduction from set packing, the analog of maximum
independent set on graphs, we manage to avoid this issue.

#### Reduction from Set Packing to Euclidean $\mathsf{DST}$.

Our main insight is that while we cannot reduce from the vertex cover problem
(on even cubic graphs) to Euclidean $\mathsf{DST}$, we can however reduce from
the independent set problem on cubic graphs to Euclidean $\mathsf{DST}$.

As such, we work with set packing problem, a generalization of the independent
set problem. In particular, we work with $\mathsf{SP_{3}}$, the set packing
problem where each set has cardinality $3$, and it becomes much easier to
limit the adjacencies of Steiner points when they depend on fewer coordinates.
We also assume that there is a set partition in the completeness case. Given a
set system $([n],\mathcal{S})$ where $\mathcal{S}$ is a collection of subsets
of $[n]$ of cardinality $3$, we construct an instance of Euclidean
$\mathsf{DST}$ as follows. The terminals are
$\\{\mathbf{e_{i}}\,:\,i\in[n]\\}\cup\\{\mathbf{0}\\}$ and correspond exactly
to the elements of the universe $[n]$, besides the addition of a special root
terminal $\mathbf{0}$. The facilities are
$\\{\frac{1}{6}(\mathbf{e_{i}}+\mathbf{e_{j}}+\mathbf{e_{k}})\,:\,\\{i,j,k\\}\in\mathbf{S}\\}$.
Each facility corresponds exactly to a set in $\mathcal{S}$; it is a scaling
of the characteristic vector of the set. In the completeness case, there is a
set packing. Choosing the facilities corresponding to the sets in the packing
yields a Steiner tree of cost $(\sqrt{3}/2+1/\sqrt{108})n$. Each universe
element is connected to the facility such that the corresponding universe
element is contained in the corresponding set in the packing. All facilities
are connected to the root terminal $\mathbf{0}$. In the soundness case,
suppose that every set packing of $([n],\mathcal{S})$ can cover at most
$(1-\varepsilon)n$ elements. One can show that there exists a minimum cost
tree such that: (1) the choice of facilities correspond to a maximal set
packing $\mathcal{S}^{\prime}\subseteq\mathcal{S}$, (2) each facility is
adjacent exactly to $\mathbf{0}$ and the three terminals corresponding to
universe elements contained in the facility’s set, and (3) each non-root
terminal is a leaf node and is either adjacent to a Steiner point or the root
terminal $\mathbf{0}$. Given this structure, the cost of the tree is at least
$((1-\varepsilon)(\sqrt{3}/2+1/\sqrt{108})+\varepsilon)n$, yielding hardness
of approximation within a factor of $1+\varepsilon/26$. The scale factor of
$1/6$ in the contruction of the facilities is chosen carefully to ensure
$(1)$, $(2)$, and $(3)$ and optimize this hardness of approximation factor
(See Section 5 for details.).

This reduction is natural when the terminals are universe elements and the
Steiner points are sets. By having our facilities depend on multiple
coordinates, we keep the terminals far apart and also keep Steiner points
relatively far apart (at least relative to our root) so that we can limit
their adjacencies. Thus, upon removing the zeroes vector (special terminal),
the Steiner tree splits into many connected components which can be
interpreted as a choice of sets for our set packing.

#### Reduction from Set Packing to $\mathsf{DST}$ in $\ell_{p}$-metric Spaces.

It turns out that the reduction from $\mathsf{SP_{3}}$ to Euclidean
$\mathsf{DST}$ generalizes to a reduction from $\mathsf{SP_{3}}$ to
$\mathsf{DST}$ in $\ell_{p}$-metric spaces. There are two main differences.

First, we modify our hard instance of $\mathsf{SP_{3}}$ slightly to become
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$. The completeness case is identical
to that outlined in the Euclidean $\mathsf{DST}$ case above. In the soundness
case, in addition to each set packing of $([n],\mathcal{S})$ covering at most
$(1-\varepsilon)n$ elements, we also have that, for any set cover
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that
$[n]\subseteq\cup_{S\in\mathcal{S}^{\prime}}S$,
$|\mathcal{S}^{\prime}|\geq(1+\delta)(n/3)$. We add this restriction on the
size of minimum set covers since we observe that, for certain $p$, the
hardness of approximation of $\mathsf{DST}$ in $\ell_{p}$-metric spaces
resultant from this reduction depends on both $\varepsilon$ and $\delta$ (or
even only $\delta$). See Figure 1 and the surrounding discussion.

Additionally, in the reduction to $\mathsf{DST}$ in the $\ell_{p}$-metric, the
scale factor of $1/6$ in the Euclidean setting becomes some constant depending
on $p$. In part, this is to sufficiently restrict the structure of optimal
Steiner trees in the soundness case. Different choices of scale factor also
yield improved hardness of approximation ratios. For example, it is optimal to
use a scale factor close to $1/2$ for very large $p$.

Finally, we discuss below some context around Open Problems 2 and 3, while
also discussing our techniques for proving Theorem 1.4 (resolution of Open
Problem 3).

#### Prior Work on $\mathsf{CST}$ and Technical Difficulties.

Prior to this work, the only $\mathsf{APX}$-hardness results for high
dimensional $\mathsf{CST}$ were in the Hamming $(\ell_{0})$ and Rectilinear
$(\ell_{1})$ metrics [War95, Tre00]. The discrete structure of Hamming
$\mathsf{CST}$ makes it far more amenable to existing tools, such as
reductions from hard graph problems, than other variants of $\mathsf{CST}$.
Indeed, Trevisan’s proof of $\mathsf{APX}$-hardness of Rectilinear
$\mathsf{CST}$ is a direct reduction from Hamming $\mathsf{CST}$. While he
appeals to the integrality property of the Min Cut LP relaxation, Hanan showed
decades earlier that instances of Rectilinear $\mathsf{CST}$ admit optimal
Steiner trees using only Steiner points on the grid formed by the terminals
[Han66]. This Hanan grid arises from the coordinate independence in the
$\ell_{1}$-metric and is unique to the $\ell_{1}$-metric among
$\ell_{p}$-metrics.

In other $\ell_{p}$-metrics, we know much less. From [GGJ77], we know that
Euclidean $\mathsf{CST}$ is $\mathsf{NP}$-hard. The proof is shown in the
plane, making heavy use of the fact that optimal Euclidean Steiner trees have
non-intersecting edges and those edges meet at at least 120 degree angles
[GP68]. However, the non-intersecting edge property is not especially useful
for point configurations outside of the plane. Without this property, we have
very few strong tools for restricting the structure of optimal Steiner trees.
Indeed, we do not know a proof of $\mathsf{NP}$-hardness of Euclidean
$\mathsf{CST}$ which does not involve directly appealing to hardness in the
plane. This poses a major barrier to showing $\mathsf{APX}$-hardness of
Euclidean $\mathsf{CST}$. In low dimensions, we know a $\mathsf{PTAS}$ exists
[Aro98], so we cannot appeal to $\mathsf{NP}$-hardness techniques. Hence,
showing $\mathsf{APX}$-hardness in high-dimensions will ultimately require a
brand new $\mathsf{NP}$-hardness argument.

Euclidean $\mathsf{CST}$ has also been heavily studied from the perspective of
discrete geometry. The central quantity of interest in that setting is the
Steiner ratio of a point configuration: the ratio of the cost of an optimal
Steiner tree and a minimum spanning tree. For example, the Steiner ratio of
the three vertices of a unit equilateral triangle is $\sqrt{3}/2$ with the
optimal Steiner tree achieved by adding the center of the triangle as a
Steiner point and connecting it to the vertices. Perhaps the most basic
question about the Steiner ratio is the following: what is the minimum Steiner
ratio over point configurations in the Euclidean plane? Gilbert and Pollak
conjectured that it is exactly $\sqrt{3}/2\approx 0.866$, coming from the
equilateral triangle [GP68]. This conjecture, the Gilbert-Pollak Steiner ratio
conjecture, remains open after more than half a century [IT12]. The best known
lower bound on this quantity is $\approx 0.824$, leaving a major gap, even in
the plane [CG85].

Predictably, in higher dimensions we know even less about the Steiner ratio
and the construction of Steiner trees. Although, extrapolating from the plane,
one might guess that the vertices of a regular simplex might admit the minimum
Steiner ratio in higher dimensions (the Generalized Gilbert-Pollak Steiner
ratio conjecture), Du and Smith disproved this conjecture without providing a
satisfying new candidate point configuration [DS96]. Moreover, we do not know
how to construct optimal Steiner trees of high-dimensional point
configurations, not even of the vertices of regular simplices (although [CG76]
gives a candidate optimal Steiner tree for some dimensions). As in the plane,
we also have an enormous gap in the bounds on the Steiner ratio: the minimum
lies somewhere between $0.669$ and $0.62$ [CG76, DS96, DWLX11].

Given our weak bounds, we cannot appeal to the Steiner ratio in analyzing
delicate inapproximability arguments. The fact that we cannot even construct
high-dimensional optimal Steiner trees compounds this difficulty further. The
state of affairs is similar in other $\ell_{p}$-metrics. New results about the
inapproximability of high-dimensional $\mathsf{CST}$ require novel structural
insights.

#### Reduction from Graph Coloring to $\mathsf{CST}$ in the
$\ell_{\infty}$-metric.

In this work, we show $\mathsf{APX}$-hardness for $\mathsf{CST}$ in the
$\ell_{\infty}$-metric. Our proof is unlike the results in [War95, Tre00].
Unable to reduce the problem from a discrete metric space (e.g., Hamming
space), we rely instead on the observation that the distance between any two
points in the $\ell_{\infty}$-metric is determined by a single coordinate. We
use this observation to introduce structural guarantees on Steiner trees we
construct in the $\ell_{\infty}$-metric.

Given a graph, we arbitrarily orient its edges to form the digraph $G(V,A)$.
We construct an instance of $\mathsf{CST}$ in the $\ell_{\infty}$-metric as
follows. Each coordinate of the terminals corresponds to an edge in $A$. The
terminals themselves correspond to vertices, along with the usual addition of
a root terminal $\mathbf{0}$, the all-zeroes vector. Given $v\in V$ and $a\in
A$, the terminal $t$ corresponding to $v$ is $1$ in the coordinate
corresponding to $a$ if $a$ is an outgoing edge from $v$, $-1$ if $a$ is an
incoming edge to $v$, and $0$ otherwise. This ensures that for each
coordinate, there are exactly two terminals that are nonzero in that
coordinate. Intuitively, the terminals corresponding to adjacent vertices are
far apart (distance $2$), and non-neighboring vertices are close together
(distance $1$).

Then, a minimum proper vertex coloring $\pi:G\to[\chi(G)]$ induces a low cost
Steiner tree of these terminals. For each color class of vertices, there is a
Steiner point $s$ at distance $1/2$ from the set of corresponding terminals of
that color class. Among those terminals, for each coordinate $i$, there is at
most one terminal nonzero in that coordinate (using that each color class is
an independent set). Setting $s_{i}$ to be $0$ or half of that nonzero
coordinate yields the desired Steiner point (thus, we have
$\|s\|_{\infty}=1/2$). The tree is then constructed by connecting the
terminals corresponding to each color class to the Steiner point described
above and then connecting each of those Steiner points to $\mathbf{0}$. Each
edge in the tree is of cost exactly $1/2$ and there are $n+\chi(G)+1$ total
vertices, yielding a total cost of $(n+\chi(G))/2$.

It turns out that this simple tree is actually the optimal Steiner tree for
this configuration! Upon showing this fact, the hardness of graph coloring
(even in graphs with linear chromatic number) yields $\mathsf{APX}$-hardness
of $\mathsf{CST}$ in the $\ell_{\infty}$-metric.

To do this, we show that there exists an optimal Steiner tree exhibiting many
complementary properties and then prove that this tree is precisely the tree
described above. At a high level, the objective is to prove two main claims:
nonzero terminals are leaf nodes in the Steiner tree, and no Steiner point is
adjacent to another Steiner point. Upon showing these two claims, it is easy
to check that the Steiner points in the optimal tree are of the desired form.

Underlying the arguments required for each of these claims is an important
observation about the structure of optimal Steiner trees of this
$\mathsf{CST}$ instance. Let $T$ be an optimal Steiner tree of this
$\mathsf{CST}$ instance, and let $t,t^{\prime}$ be terminals such that
$t_{i}=1$ and $t_{i}^{\prime}=-1$. Observe that $t$ and $t^{\prime}$ are the
only terminals in $T$ with nonzero $i\textsuperscript{th}$ coordinates. We can
show that there exists an optimal Steiner tree such that the
$i\textsuperscript{th}$ coordinate of Steiner points on the path between $t$
and $t^{\prime}$ decreases maximally away from $t$ until the coordinate
reaches $0$ (in the sense of determining the distance between adjacent
points). Likewise, the $i\textsuperscript{th}$ coordinate increases maximally
toward $0$ along edges away from $t^{\prime}$. Throughout, the coordinates
reduce in magnitude maximally away from the path linking $t$ and $t^{\prime}$.
If, for example, the path between $t$ and some Steiner point $s$ passes
through $\mathbf{0}$, then $s$ cannot have any coordinates of the same sign as
$t$. Adopting this view of the points in $T$ being projected onto the
$i\textsuperscript{th}$ coordinate is valuable intuition for the proofs.

For example, we use this intuition in proving that we may assume nonzero
terminals are leaf nodes. It is easy to show that in some optimal Steiner
tree, the nonzero terminals are non-adjacent, but, a priori, it is unclear
whether they may be adjacent to many Steiner points. Suppose that $t$ is a
nonzero terminal adjacent to multiple Steiner points. Consider removing the
edges from $t$ to Steiner points such that their resultant connected
components do not contain $\mathbf{0}$. The idea is that, in these new
connected components, coordinates of Steiner points with the same sign as
coordinates of $t$ are no longer useful, so we can set them all to zero. Upon
doing so, connecting the Steiner originally adjacent to $t$ to $\mathbf{0}$
reconnects the tree without increasing the cost. This amounts to ensuring that
$\mathbf{0}$ is included in the path between these Steiner points and $t$.

Showing that the Steiner points in the tree are non-adjacent is the most
technical part of the proof. To do so, we first consider Steiner leaves, the
Steiner points in the Steiner tree that become leaf nodes upon removing all
nonzero terminals in the tree. One important property of these Steiner points
is that they are necessarily adjacent to more terminals than Steiner points
(it is easy to show that Steiner points must be degree at least $3$ by the
triangle inequality). It is straightforward to show that terminals adjacent to
the same Steiner point cannot overlap in nonzero coordinates. Then, to
minimize the total cost of the edges incident to the Steiner leaf, its
coordinates must have magnitude at most $1/2$, with magnitude $1/2$ in each of
the nonzero coordinates of the adjacent terminals (with the same sign as that
nonzero coordinate). Using this fact we can show that the terminals adjacent
to adjacent Steiner leaves cannot overlap on nonzero coordinates either (by
removing the edge between the Steiner leaves and adding a new edge to
$\mathbf{0}$). Indeed, an even stronger fact is true: if two Steiner leaves
are adjacent to a common Steiner point, then the terminals adjacent to the
Steiner leaves cannot overlap on nonzero coordinates. This follows from the
usual trick of dropping an edge and connecting one of the Steiner leaves
directly to $\mathbf{0}$.

By leveraging these facts and the coordinate-wise view of the Steiner tree, we
can show that each non-leaf Steiner point in the tree is adjacent to at least
one other non-leaf Steiner point. To do this, consider $s$ and $s^{\prime}$,
two Steiner leaves adjacent to a common Steiner point $s^{\prime\prime}$. We
can remove all edges from $s^{\prime}$ to its adjacent terminals and connect
them instead to $s$. We can then modify $s$ to ensure that all neighboring
terminals are at distance $1/2$ away and then remove $s^{\prime}$ entirely
since it is a Steiner leaf. Repeating this process will result in one of two
things. Either $s^{\prime\prime}$ will become degree $2$ and can be removed
via the triangle inequality or $s^{\prime\prime}$ is adjacent to another non-
leaf Steiner point. After repeating for all Steiner points adjacent to Steiner
leaves, all remaining non-leaf Steiner points will be adjacent to at least one
other non-leaf Steiner point.

Finally, consider removing all nonzero terminals and Steiner leaves. The
resulting tree has at most vertex of degree $1$, $\mathbf{0}$, and, hence, is
only a tree if all Steiner points were Steiner leaves. That is, all Steiner
points in the tree must have only been adjacent to terminals.

###  1.3 Organization of the Paper

In Section 2 we define the problems of interest to this paper. In Section 3,
we relate $\mathsf{CST}$ to $\mathsf{DST}$, describing the reduction between
the two problems. In Section 4, we provide our generic framework of moving
from a set system to an abstract and yet parameterized metric space. In
Section 5, we detail our $\ell_{p}$-metric embedding of the abstract metric
space described in the previous section. In Section 6 we prove
$\mathsf{APX}$-hardness of $\mathsf{CST}$ in the $\ell_{\infty}$-metric via a
reduction from graph coloring. In Appendix A, we prove explicit factors of
inapproximability for $\mathsf{DST}$ in $\ell_{0},\ell_{1},$ and
$\ell_{2}$-metrics. In Appendix B, we explain how to derive inapproximability
of $\mathsf{DST}$ in string metrics using known results from the literature.
In Appendix C, we show that our hardness results for $\mathsf{DST}$ hold even
in $O(\log n)$-dimensions using a specialized near-isometric embedding.

##  2 Preliminaries

In this section, we detail some notations and definitions related to
$\ell_{p}$-metric spaces, the Steiner tree problem, the graph coloring
problem, the set packing problem, and the vertex cover problem.

####  $\ell_{p}$-metrics.

Let $p\in\mathbb{R}_{\geq 1}\cup\\{0,\infty\\}$. For any two points
$a,b\in\mathbb{R}^{d}$ we denote the distance between them in the
$\ell_{p}$-metric by

$\|a-b\|_{p}:=\begin{cases}\left|\\{i\in[d]|a_{i}\neq b_{i}\\}\right|&\text{
if }p=0,\vspace{0.15cm}\\\
\left(\underset{i\in[d]}{\sum}|a_{i}-b_{i}|^{p}\right)^{1/p}&\text{ if
}p\in\mathbb{R}_{\geq 1},\vspace{0.15cm}\\\ \underset{i\in[d]}{\max}\
|a_{i}-b_{i}|&\text{ if }p=\infty.\end{cases}$

#### Steiner tree problem.

Let $(\mathcal{X},\Delta)$ be a metric space on set $\mathcal{X}$ and distance
function $\Delta$. Given a set $P$ of points in $(\mathcal{X},\Delta)$, a
Steiner tree of those points is a minimal spanning tree of $P\cup S$ for some
$S\subseteq\mathcal{X}$. The initial points in $P$ are called terminals and
the points in $S$ are called Steiner points.

Given a tree $T$ with vertices as points in $\mathcal{X}$ and edge weights
induced by the distance function $\Delta$, the cost of the tree $T=(P\cup
S,E)$, denoted by $\operatorname{\mathsf{cost}}_{\Delta}(T)$ is

$\operatorname{\mathsf{cost}}_{\Delta}(T):=\sum_{e=(u,v)\in E}\Delta(u,v).$

In the continuous Steiner tree problem ($\mathsf{CST}$) in the metric space
$(\mathcal{X},\Delta)$, we are given as input $P\subseteq\mathcal{X}$, and the
goal is to find a minimum cost Steiner tree of $P$. In the discrete Steiner
tree problem ($\mathsf{DST}$) in the metric space $(\mathcal{X},\Delta)$, we
are given a pair $(P,X)$ as input, with $P\subseteq\mathcal{X}$ the set of $n$
terminals and $X\subseteq\mathcal{X}$ with $|X|=O(\operatorname{poly}(n))$ as
the set of facilities. The goal is then to find a minimum cost of a Steiner
tree $T=(P\cup S,E)$ of $P$ with $S\subseteq X$.

$\mathsf{DST}$ can also be considered as a graph problem. In this setting it
is called the metric Steiner Tree problem on graphs. Given a complete graph
$G=(P\cup X,E)$ with weight function $w:E\to\mathbb{R}^{+}$ satisfying the
triangle inequality, the metric Steiner tree problem is to find the minimum
cost of a Steiner tree of $P$ using Steiner points from the set $X$.

#### Graph coloring problem.

In the $k$-coloring problem, we are given a graph $G(V,E)$ and a positive
integer $k$, and the goal is to determine whether there is a proper coloring
$\pi:V\to[k]$ such that, for each $i\in[k]$, $\pi^{-1}(i)$ forms an
independent set in $G$. That is, the vertices in $G$ can be partitioned into
at $k$ independent sets. The minimum $k$ such that $G$ admits a proper
$k$-coloring is the chromatic number of $G$ and is denoted $\chi(G)$.

In the $(a,b)$-coloring, the question in to instead decide which of the
following two cases hold:

  * •

Completeness: $G$ admits a proper $a$-coloring ($\chi(G)\leq a$).

  * •

Soundness: Every proper coloring of $G$ uses at least $b$ colors ($\chi(G)\geq
b$).

#### Set packing problem.

We say that $(\mathcal{U},\mathcal{S})$ is a set system if $\mathcal{S}$ is a
collection of subsets of $\mathcal{U}$. An instance of the Set Packing problem
($\mathsf{SP}$) is given by the triple $([n],\mathcal{S},k)$, where
$([n],\mathcal{S})$ is a set system with $|\mathcal{S}|=m$ and
$k\in\mathbb{N}$, and the goal is to determine if there exists some
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that for all distinct
$S,S^{\prime}\in\mathcal{S}^{\prime}$, we have $S\cap S^{\prime}=\emptyset$
and $|\cup_{S\in\mathcal{S}^{\prime}}S|\geq k$? When all of the sets in
$\mathcal{S}$ are fixed to be of size $B$, we abbreviate the problem as
$\mathsf{SP_{B}}$.

We define $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ to be the related decision
problem in which we have as input $([n],\mathcal{S})$ as above and decide
which of the following two cases hold.

  * •

Completeness: $[n]$ may be partitioned into $n/3$ sets all of which are in
$\mathcal{S}$.

  * •

Soundness: Any collection of disjoint sets in $\mathcal{S}$ covers at most
$(1-\varepsilon)n$ elements in $[n]$, and for any collection
$\mathcal{S}^{\prime}\subset\mathcal{S}$ (sets in $\mathcal{S}^{\prime}$ need
not be pairwise disjoint) such that
$[n]\subseteq\cup_{S\in\mathcal{S}^{\prime}}S$ satisfies
$|\mathcal{S}^{\prime}|\geq(1+\delta)(n/3)$.

######  Remark 2.1.

In the soundness case, the parameters $\varepsilon$ and $\delta$ characterize
the maximum coverage of a set packing and the minimum size of a set cover,
respectively. These parameters are related. Indeed, given $\varepsilon$, we
should have $\delta\in[\varepsilon/2,2\varepsilon]$. If any collection of
disjoint sets in $\mathcal{S}$ covers at most $(1-\varepsilon)n$ elements in
$[n]$, then the smallest possible size of a set cover is
$(1+\varepsilon/2)(n/3)$ (if every additional set covers $2$ elements).
Assuming a set packing covering $(1-\varepsilon)n$ sets is possible, the
largest possible minimum set cover is $(1+2\varepsilon)(n/3)$ (covering the
remaining elements one at a time).

Our reduction will use the following $\mathsf{NP}$-hardness of
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$.

######  Theorem 2.1 (Theorem 4.4, [Pet94]).

There is some $\varepsilon>0$ such that
$(\varepsilon,\varepsilon/2)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard.

In [Pet94], they actually prove Theorem 2.1 for the Max 3-Dimensional Matching
problem, but Max 3-Dimensional Matching is a special case of
$\mathsf{SP_{3}}$. This correspondence is apparent by viewing each edge of a
$3$-uniform hypergraph as a subset of $[n]$.

#### Vertex cover problem.

In the minimum Vertex Cover problem ($\mathsf{VC}$), we are given a graph
$G(V,E)$ and a positive integer $k$, and the goal is to determine if there
exists $C\subseteq V$ with $|C|\leq k$ such that, for all $e\in E$, at least
one endpoint of $e$ is in ${C}$. Such a $C$, containing an endpoint of each
edge, is called a vertex cover of $G$.

In $(a,b)$-$\mathsf{VC}$, we are given a graph $G(V,E)$, and the goal is to
decide whether there exists a vertex cover of $G$ of size at most $a\cdot|V|$
or if every vertex cover of $G$ has size at least $b\cdot|V|$.

##  3 Reduction from $\mathsf{CST}$ to $\mathsf{DST}$

In this section, we link $\mathsf{CST}$ to $\mathsf{DST}$, proving that
$\mathsf{DST}$ is computationally harder than $\mathsf{CST}$. The sense in
which this holds is formalized in Theorem 3.1.

######  Theorem 3.1.

Let $(\mathcal{X},d)$ be a metric space such that there exists an algorithm
for $\mathsf{CST}$ in $(\mathcal{X},d)$ that runs in $O(f(n))$ time for some
computable function $f$ and $n$ the number of input terminals. Let $P$ be an
instance of $\mathsf{CST}$ in $(\mathcal{X},d)$, and let $T^{*}$ be an optimal
Steiner tree of $P$. Then, for any $\varepsilon>0$, there exists a
$\operatorname{poly}(n,\varepsilon)$-time algorithm outputting
$X\subset\mathcal{X}$ with the following properties.

  1. 1.

$|X|=\operatorname{poly}(n,\varepsilon).$

  2. 2.

If $T$ is the optimal Steiner tree on $\mathsf{DST}$ instance $(P,X)$, then

$\operatorname{\mathsf{cost}}(T^{*})\leq\operatorname{\mathsf{cost}}(T)\leq(1+\varepsilon)\operatorname{\mathsf{cost}}(T^{*}).$

To prove this, we appeal to a powerful structural result of [BG21].

######  Theorem 3.2 ([BG21]).

Let $P$ be an instance of $\mathsf{CST}$ in metric space $(\mathcal{X},d)$ and
let $T^{*}$ be an optimal Steiner tree of $P$. For any $\varepsilon>0$, there
exists constant $C_{\varepsilon}$ and Steiner tree $T^{\prime}$ of $P$ with
the following properties.

  1. 1.

$\operatorname{\mathsf{cost}}(T^{*})\leq\operatorname{\mathsf{cost}}(T^{\prime})\leq(1+\varepsilon)\operatorname{\mathsf{cost}}(T^{*})$.

  2. 2.

$T^{\prime}$ is formed by partitioning $P$ into parts of size at most
$C_{\varepsilon}$, finding optimal Steiner trees of each part, and connecting
those Steiner trees via edges between their respective terminals.

This follows from the proof of Theorem 3.2 of [BG21] with $C_{\varepsilon}\leq
2^{32/\varepsilon\ln(8/\varepsilon)}$.

###### Proof of Theorem 3.1..

Consider every subset of $P$ of size at most $C_{\varepsilon/2}$ as an
instance of $\mathsf{CST}$ in $(\mathcal{X},d)$. There are
$\operatorname{poly}(n,\varepsilon)$ such instances and optimal Steiner trees
(optimal up to an arbitrarily small factor $1+\varepsilon^{\prime}$ due to
numerical precision) can be computed in constant time (in $\varepsilon$ and
$\varepsilon^{\prime}$). Let $X$ be the union of the Steiner points used in
the Steiner tree solutions for these instances. Note that
$|X|=\operatorname{poly}(n)$ since Steiner trees on $n$ terminals may be
assumed to use at most $n-2$ Steiner points (this follows by the triangle
inequality and a degree counting argument—see Section 3.4 of [GP68], for
example). Let $T^{\prime}$ be the near-optimal Steiner tree from Theorem 3.2.
Let $Q$ be some set of terminals in the partition of terminals induced by
$T^{\prime}$. Then, the optimal Steiner tree of $\mathsf{DST}$ instance
$(Q,X)$ costs at most a $(1+\varepsilon^{\prime})$ factor more than the cost
of the optimal Steiner tree for $\mathsf{CST}$ instance $Q$. Then, since this
holds for each part in the partition of terminals induced by $T^{\prime}$ from
Theorem 3.2, if $T$ is the optimal Steiner tree on $\mathsf{DST}$ instance
$(P,X)$, then
$\operatorname{\mathsf{cost}}(T)\leq(1+\varepsilon^{\prime})\operatorname{\mathsf{cost}}(T^{\prime})\leq(1+\varepsilon^{\prime})(1+\varepsilon/2)\operatorname{\mathsf{cost}}(T^{*})$.
Since $\varepsilon^{\prime}$ can be made arbitrarily small, this implies the
desired result. ∎

In particular, Theorem 3.1 holds for all $\ell_{p}$-metric spaces and in any
dimension. This shows that $\mathsf{CST}$ is essentially no harder than
$\mathsf{DST}$ in those spaces.

######  Corollary 3.3.

For all $\varepsilon>0$ and $p\in[1,\infty]$, if there exists a polynomial
time $(1+\alpha)$-approximation algorithm for $\mathsf{DST}$ in the
$\ell_{p}$-metric, then there exists a polynomial time
$(1+\alpha+\varepsilon)$-approximation algorithm for $\mathsf{CST}$ in the
$\ell_{p}$-metric.

###### Proof.

From Theorem 3.1, it suffices to show that $\mathsf{CST}$ in the
$\ell_{p}$-metric admits an algorithm that runs in $O(f(n))$ time for some
computable function $f$ and $n$ the number of input terminals. Given a set of
terminals $P$ with $|P|=n$, consider the subspace of dimension at most $n$
formed by those points. Then, the approximation scheme of Arora (see 1.1.1 of
[Aro98]) runs in $O(f(n))$ time for a computable function $f$, yielding the
result. ∎

Theorem 3.1 and Corollary 3.3 give a construction for efficient approximation
algorithms of $\mathsf{CST}$ using the literature on $\mathsf{DST}$.

######  Corollary 3.4.

For all $\varepsilon>0$ and $p\in[1,\infty]$, $\mathsf{CST}$ in the
$\ell_{p}$-metric admits a polynomial time
$(\ln(4)+\varepsilon)-$approximation algorithm.

###### Proof.

Run the algorithm implicit in 3.1 and Corollary 3.3 to compute a
$\mathsf{DST}$ instance. Then, apply the
$(\ln(4)+\varepsilon^{\prime})-$approximation algorithm for $\mathsf{DST}$
from [BPR+17] and choose $\varepsilon^{\prime}$ to be appropriately small. ∎

##  4 The Metric Steiner Problem on Graphs

In this section, we show a gap preserving reduction from $\mathsf{SP_{3}}$ to
$\mathsf{DST}$ in general metrics. In Section 4.1 we describe how we associate
a metric space to a set system. The resultant metric spaces will be called set
system spaces. When the distances in these metric spaces satisfy an additional
collection of constraints (see Definition 4.3), these set system spaces will
be sufficient to yield a gap preserving reduction from $\mathsf{SP_{3}}$ to
$\mathsf{DST}$. The details of this reduction are provided in Subsection 4.2.

###  4.1 From Set Systems to Metric Spaces

In this subsection, we describe how to associate a metric space to a set
system555For the purposes of our application to $\mathsf{DST}$, we specify
this association to metric spaces only for set systems where each set in the
collection is of size exactly 3.. We also introduce more restricted metric
spaces that facilitate gap preserving reductions from $\mathsf{SP_{3}}$ to
$\mathsf{DST}$.

######  Definition 4.1 (Set System Space).

Let $([n],\mathcal{S})$ be a set system such that for all $S\in\mathcal{S}$,
we have $|S|=3$, and $|\mathcal{S}|:=m$. Let
$\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau\in\mathbb{R}^{+}$.
Then, we define the
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$-set
system space corresponding to $([n],\mathcal{S})$ to be the space
$(\widetilde{P}\cup X,\Delta)$ containing $n+m+1$ points and a distance
function $\Delta$. We define $P:=\\{t_{i}\,:\,i\in[n]\\}$,
$\widetilde{P}=P\cup\\{r\\}$, and $X:=\\{s_{j}\,:\,S_{j}\in\mathcal{S}\\}$. We
refer to the points in $P$ as universe elements, $r$ as the root, and the
points in $X$ as facilities. For convenience, for $s_{j}\in X$, we define
$\Gamma(s_{j})=S_{j}$.

Interpreting the points of the space as vertices in a graph, we define the
weight function $\Delta$ by defining every pairwise edge weight as follows
(the weight of the edge between each point and itself is $0$).

  * •

$\Delta(r,s)=\alpha_{\text{X}}$ for all $s\in X$.

  * •

$\Delta(r,t)=\alpha_{\text{P}}$ for all $t\in P$.

  * •

$\Delta(t_{i},s)=\beta_{\text{in}}$ for all $i\in[n]$ such that
$i\in\Gamma(s)$.

  * •

$\Delta(t_{i},s)=\beta_{\text{out}}$ for all $i\in[n]$ such that
$i\not\in\Gamma(s)$.

  * •

$\Delta(s,s^{\prime})=\gamma_{i}$ for all $s,s^{\prime}\in X$ such that
$|\Gamma(s)\cap\Gamma(s^{\prime})|=i$, for $i=0,1,$ and $2$.

  * •

$\Delta(t,t^{\prime})=\tau$ for all distinct $t,t^{\prime}\in P$.

To elucidate our choice of notation, we also provide intuitive definitions of
each parameter.

  * •

$\alpha_{\text{X}}$ is the distance from the root terminal to a Steiner point
in $X$.

  * •

$\alpha_{\text{P}}$ is the distance from the root terminal to a terminal in
$P$.

  * •

$\beta_{\text{in}}$ is the distance between a Steiner point $s$ and non-root
terminal $t_{i}$ such that the set corresponding to $s$ contains the universe
element corresponding to $t_{i}$.

  * •

$\beta_{\text{out}}$ is the distance between a Steiner point $s$ and non-root
terminal $t_{i}$ such that the set corresponding to $s$ does not contain the
universe element corresponding to $t_{i}$.

  * •

$\gamma_{i}$ is the distance between Steiner points $s$ and $s^{\prime}$ such
that their corresponding sets have an intersection of size $i$.

  * •

$\tau$ is the distance between non-root terminals.

Note that, although we say “distance” in the above intuitive descriptions, the
weight function $\Delta$ may not define a metric, so set system spaces may not
be metric spaces. The following definition resolves this issue.

######  Definition 4.2 (Metric Compatibility).

Suppose that we have
$\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau\in\mathbb{R}^{+}$,
such that all of the following inequalities hold.

  1. 1.

$\alpha_{\text{X}}\leq\min(\alpha_{\text{P}}+\beta_{\text{in}},\alpha_{\text{P}}+\beta_{\text{out}})$.

  2. 2.

$\alpha_{\text{P}}\leq\min(\alpha_{\text{X}}+\beta_{\text{in}},\alpha_{\text{X}}+\beta_{\text{out}}).$

  3. 3.

$\beta_{\text{in}}\leq\min(\alpha_{\text{X}}+\alpha_{\text{P}},$
$\beta_{\text{out}}+\tau,\gamma_{i}+\beta_{\text{out}}$ : $i\in\\{0,1,2\\})$.

  4. 4.

$\beta_{\text{out}}\leq\min(\alpha_{\text{X}}+\alpha_{\text{P}},\beta_{\text{in}}+\tau,\gamma_{i}+\beta_{\text{in}}\,:\,i\in\\{0,1,2\\})$.

  5. 5.

$\gamma_{i}\leq\min(2\alpha_{\text{X}},\gamma_{j}+\gamma_{k},2\beta_{\text{in}},2\beta_{\text{out}}$
: $i,j,k\in\\{0,1,2\\})$.

  6. 6.

$\tau\leq\min(2\alpha_{\text{P}}$, $2\beta_{\text{in}},$
$2\beta_{\text{out}})$.

In this case, we call the tuple
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$
metric compatible. Note that the constraints
$\gamma_{i}\leq\beta_{\text{in}}+\beta_{\text{out}}$ and
$\tau\leq\beta_{\text{in}}+\beta_{\text{out}}$ are implied by $\gamma_{i}\leq
2\beta_{\text{in}},2\beta_{\text{out}}$ and $\tau\leq
2\beta_{\text{in}},2\beta_{\text{out}}$.

A general diagram of an
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$-set
system space is given in Figure 2. Note that not all pairwise distances in the
diagram are labeled.

$\displaystyle\vdots$$\displaystyle r$Facilities ($\displaystyle
s_{i}$)Universe Elements
$\displaystyle(t_{i})$$\displaystyle\alpha_{\text{sr}}$$\displaystyle\alpha_{\text{sr}}$$\displaystyle\alpha_{\text{tr}}$$\displaystyle\vdots$$\displaystyle\alpha_{\text{tr}}$$\displaystyle\gamma_{2}$$\displaystyle\gamma_{1}$$\displaystyle\gamma_{0}$$\displaystyle\lambda$$\displaystyle\lambda$$\displaystyle\beta_{\text{in}}$$\displaystyle\beta_{\text{out}}$Root
Figure 2: A general
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$-set
system space with edges between different groups of nodes color-coded

######  Proposition 4.1.

If
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$
is metric compatible, then any
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$-set
system space is a metric space.

###### Proof.

Inequalities 1–6 in Definition 4.2 are precisely those necessary for the
triangle inequality to hold with distance function $\Delta$. The other metric
constraints follow trivially from Definition 4.1. ∎

Hence, if
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$
is metric compatible, associated set system space weight functions $\Delta$
are distance functions. Now we introduce the notion of Steiner embeddability,
a further restriction on metric compatible tuples. Tuples with these
restrictions induce a notion of distance on metric spaces related to set
systems that facilitates the construction of a gap preserving reduction from
$\mathsf{SP_{3}}$ to $\mathsf{DST}$.

######  Definition 4.3 (Steiner embeddability and Steiner spaces).

We call a metric compatible tuple
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$
Steiner embeddable if

  1. (P1)

Steiner proximity: $\alpha_{\text{X}}\leq 3\gamma_{2}/2,$ $\alpha_{\text{P}},$
$\beta_{\text{in}},$ $\beta_{\text{out}},$ $\gamma_{0}$, $\gamma_{1},$ $\tau$.

  2. (P2)

Root proximity: $\alpha_{\text{P}}\leq\beta_{\text{out}}.$

  3. (P3)

Steiner utility:
$\beta_{\text{in}}+\frac{\alpha_{\text{X}}}{3}<\min(\alpha_{\text{P}},\tau)$.

  4. (P4)

Steiner diameter:
$\min(\alpha_{\text{P}},\tau)\leq\beta_{\text{in}}+\gamma_{2}$.

We call any
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$-set
system space with
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$
Steiner embeddable a Steiner space.

###  4.2 Hardness of $\mathsf{DST}$ from Set Packing

In this subsection we describe a general reduction from
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ to $\mathsf{DST}$ using the language
of Steiner spaces.

######  Theorem 4.2.

Let $(\alpha_{\text{X}},$ $\alpha_{\text{P}},$ $\beta_{\text{in}},$
$\beta_{\text{out}},$ $\gamma_{0},$ $\gamma_{1},$ $\gamma_{2},\tau)$ be a
Steiner embeddable tuple. For an instance $([n],\mathcal{S})$ of
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ where $|\mathcal{S}|=m$, let
$(\widetilde{P}\cup X,\Delta)$ be the Steiner space guaranteed by Definitions
4.2 and 4.3. Then, we have the following guarantees on an instance
$(\widetilde{P}\cup X)$ of $\mathsf{DST}$ over $(\widetilde{P}\cup X,\Delta)$:

Completeness:

If $([n],\mathcal{S})$ admits a set packing of size $n/3$, then there is a
Steiner tree for $\widetilde{P}$ of cost

$n(\alpha_{\text{X}}/3+\beta_{\text{in}}).$

Soundness:

Every Steiner tree of $\widetilde{P}$ must be of cost at least

$n(\alpha_{\text{X}}/3+\beta_{\text{in}})\cdot\left(1-\varepsilon+\frac{(4\varepsilon-2\delta)}{3}\cdot\frac{\min(\alpha_{\text{P}},\tau,\beta_{\text{in}}+\alpha_{\text{X}}/2)}{\alpha_{\text{X}}/3+\beta_{\text{in}}}+\frac{(2\delta-\varepsilon)}{3}\cdot\frac{\min(\alpha_{\text{P}},\tau)}{\alpha_{\text{X}}/3+\beta_{\text{in}}}\right).$

Run Time:

Given $\alpha_{\text{X}},$ $\alpha_{\text{P}},$ $\beta_{\text{in}},$
$\beta_{\text{out}},$ $\gamma_{0},$ $\gamma_{1},$ $\gamma_{2},\tau$ and
$([n],\mathcal{S})$, the above instance of $\mathsf{DST}$ can be constructed
in $\operatorname{poly}(n+m)$ time.

The expression for the inapproximability factor in the soundness case seems
quite intricate. One may wonder if this theorem implies a stronger
inapproximability result than the simple reduction from Set Cover mentioned in
Section 1.2 for $\mathsf{DST}$ in general metrics.

######  Corollary 4.3.

If $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard, then it is
$\mathsf{NP}$-hard to approximate $\mathsf{DST}$ in general metric spaces
within a factor of $1+\delta/4$.

###### Proof.

The hardness of approximation factor is achieved by dividing the costs in the
soundness and completeness cases of Theorem 4.2. Then, we wish to maximize
both

$\frac{\min(\alpha_{\text{P}},\tau,\beta_{\text{in}}+\alpha_{\text{X}}/2)}{\alpha_{\text{X}}/3+\beta_{\text{in}}}$

and

$\frac{\min(\alpha_{\text{P}},\tau)}{\alpha_{\text{X}}/3+\beta_{\text{in}}}.$

The numerator of the first fraction is at most
$\beta_{\text{in}}+\alpha_{\text{X}}/2$. The numerator of the second fraction
is at most $\alpha_{\text{P}}\leq\alpha_{\text{X}}+\beta_{\text{in}}$ by the
triangle inequality. Supposing that both inequalities were in fact tight, our
problem would reduce to maximizing
$\frac{\alpha_{\text{X}}/2+\beta_{\text{in}}}{\alpha_{\text{X}}/3+\beta_{\text{in}}}$
and
$\frac{\alpha_{\text{X}}+\beta_{\text{in}}}{\alpha_{\text{X}}/3+\beta_{\text{in}}}$.
Both are maximized for minimum $\beta_{\text{in}}$ and, since
$\alpha_{\text{X}}\leq\beta_{\text{in}}$ by (P1), the best possible is
$\beta_{\text{in}}=\alpha_{\text{X}}$. Assuming there is some tuple
$(\alpha_{\text{X}},$ $\alpha_{\text{P}},$ $\beta_{\text{in}},$
$\beta_{\text{out}},$ $\gamma_{0},$ $\gamma_{1},$ $\gamma_{2},\tau)$ that both
satisfies these additional constraints and is Steiner embeddable, we would
then have that $\mathsf{DST}$ is $\mathsf{NP}$-hard to approximate within a
factor of

$1-\varepsilon+\frac{(4\varepsilon-2\delta)}{3}\cdot\frac{9}{8}+\frac{(2\delta-\varepsilon)}{3}\cdot\frac{3}{2}=1+\delta/4.\qed$

In fact, $\ell_{\infty}$ $\mathsf{DST}$ can satisfy these constraints and
achieve this hardness of approximation factor. See Theorem 5.3.

######  Remark 4.1.

Interestingly, as shown in Section 1.2, there exists a simple reduction from
Set Cover with sets of size $3$ to $\mathsf{DST}$ which yields this same
hardness in general metric spaces. Nonetheless, $\varepsilon$, the set packing
parameter in $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is highly relevant in
certain other metric spaces. See, for example Theorem 5.2 and Corollary 5.5
for applications to $\ell_{p}$ metric spaces.

We now prove Theorem 4.2. Given any hard instance of $\mathsf{SP_{3}}$, using
the language of Subsection 4.1, we can consider the corresponding
$(\alpha_{\text{X}},$ $\alpha_{\text{P}},$ $\beta_{\text{in}},$
$\beta_{\text{out}},$ $\gamma_{0},$ $\gamma_{1},$ $\gamma_{2},\tau)$-set
system space $((P\cup\\{r\\})\cup X,\Delta)$. This space may be interpreted as
an instance of $\mathsf{DST}$ with terminals $\widetilde{P}=P\cup\\{r\\}$,
candidate Steiner points $X$, and pairwise distances given by $\Delta$
determining edge weights.

#### Completeness.

In the completeness case, the $\mathsf{SP_{3}}$ instance has a solution that
partitions $[n]$ into sets from $\mathcal{S}$. Let $C$ be such a partition.
For each $\\{i,j,k\\}\in C$, connect $t_{i}$, $t_{j}$, and $t_{k}$ to
$s=\Gamma^{-1}(\\{i,j,k\\})$. Then, connect each such $s$ to $r$. This results
in a Steiner tree of total cost $n(\alpha_{\text{X}}/3+\beta_{\text{in}})$.
See Figure 3.

$\displaystyle
r$$\displaystyle\Gamma^{-1}(\\{i_{1},i_{2},i_{3}\\})$$\displaystyle
t_{i_{1}}$$\displaystyle t_{i_{2}}$$\displaystyle
t_{i_{3}}$$\displaystyle\Gamma^{-1}(\\{i_{4},i_{5},i_{6}\\})$$\displaystyle\Gamma^{-1}(\\{i_{n-2},i_{n-1},i_{n}\\})$Universe
elements $\displaystyle(t_{i})$$\displaystyle t_{i_{4}}$$\displaystyle
t_{i_{5}}$$\displaystyle t_{i_{6}}$$\displaystyle t_{i_{n-2}}$$\displaystyle
t_{i_{n-1}}$$\displaystyle t_{i_{n}}$Facilities $\displaystyle(s_{j})$Root
terminal$\displaystyle\cdots$

Figure 3: Steiner tree construction in the completeness case of Theorem 4.2

.

#### Soundness.

In the soundness case, we prove a series of consistent claims about the
adjacencies of universe elements (non-$r$ terminals) and Steiner points. The
claims rely intimately on the properties of Steiner embeddable tuples.
Ultimately, the claims will show that there is some minimum length Steiner
tree mirroring much of the structure of the completeness case. This then
yields insight into the size of a set packing in the $\mathsf{SP_{3}}$
instance, thereby lower-bounding the length of a minimum Steiner tree.

We want $r$ to serve as a root for the Steiner tree with its subtrees inducing
groups of related Steiner points. To achieve this goal, we need to restrict
the adjacencies of both universe elements and Steiner points. In Proposition
4.4 we show that there exists a minimum length Steiner tree such that, for
each universe element $t_{i}$, $t_{i}$ is adjacent to only Steiner points $s$
such that $i\in\Gamma(s)$. We hope to interpret the Steiner points in the
Steiner tree as a choice of sets from $\mathcal{S}$. This property is
important since it means the adjacency of a universe element to a Steiner
point can be interpreted as the set corresponding to the Steiner point
covering the universe element.

Lemma 4.5 further restricts the adjacencies of universe elements. It shows
that we may assume that edges between universe elements cannot connect
substantial portions of the tree—one of the endpoints of such edges must be a
leaf node. Indeed, the leaf node endpoint will ultimately become a universe
element not covered by the set packing induced by the Steiner tree. Notably,
Lemma 4.5 leaves open the option that a universe element could serve as a
connecting hub for the tree, avoiding the need for Steiner points and limiting
the role of $r$. Lemma 4.7, proved using Lemma 4.6, discounts that
possibility, enforcing that non-leaf node universe elements must be connected
to Steiner points. However, even with Lemma 4.5, terminals could conceivably
connect to many Steiner points adjacent to other terminals. Lemma 4.8 shows
that we may assume that this is not the case. Proposition 4.9, combined with
Lemma 4.7, shows that we may assume that universe elements of degree greater
than $1$ are not adjacent to $r$. This yields some insight into how groups of
terminals connected to common Steiner points are connected to $r$.

The combination of these results severely limits the adjacency of universe
elements. They are either adjacent to the root $r$, adjacent to some other
universe element connected to a Steiner point, or are connected to some
Steiner point whose corresponding set contains their corresponding element of
$[n]$. In the former two cases, the universe element is a leaf node in $T$. In
the latter case, while the universe element may not be a leaf node, if it is
not, its only other neighbors are leaf node terminals. Treating those leaf
node terminals as “uncovered” universe elements allows us to treat all
terminals as leaf nodes.

The most important and most technical part of the proof is Lemma 4.10. Lemma
4.10 shows that we may assume that there are no edges between Steiner points
in the Steiner tree. In combination with the severely limited adjacencies of
universe elements, this shows that we may assume that removing $r$ from the
tree (and ignoring terminals not adjacent to Steiner points) divides the tree
into groups of universe elements connected to Steiner points. By Proposition
4.4, these universe elements correspond to elements of $[n]$ contained in the
sets corresponding to the Steiner points. So, the Steiner points adjacent to
three terminals actually correspond precisely to a packing of sets from
$\mathcal{S}$.

We want this induced packing to be large to yield insight into the size of
maximum packing in the $\mathsf{SP_{3}}$ instance. Indeed, the induced packing
corresponds to a maximum packing, as shown in Lemma 4.12. Lemma 4.11 merely
facilitates the proof of Lemma 4.12. The rest of the proof follows from this
correspondence.

Now we proceed with the proof. Let $T=(T_{V},T_{E})$ be a minimum Steiner tree
of $P$ in $G$. We wish to show that we may assume a nearly identical structure
to the completeness case, particularly in that it is optimal to pack as many
terminals into sets as possible. As we will show, these packings arise in the
Steiner tree as groups of three terminals $t_{i}$, $t_{j}$, $t_{k}$ connected
to a single Steiner point $s=\Gamma^{-1}(\\{i,j,k\\})$ which is in turn
connected to $r$. In each successive claim, we assume that the properties of
the previous claims initially hold.

######  Proposition 4.4.

We may assume that $(t_{i},s)\in T_{E}$ for $t_{i}\in P$ and $s\in X$ only if
$i\in\Gamma(s)$.

###### Proof.

Suppose $(t_{i},s)\in T_{E}$ for $t_{i}\in P$, $s\in X$, and
$i\not\in\Gamma(s)$. Then,
$\Delta(t_{i},s)=\beta_{\text{out}}\geq\alpha_{\text{P}},\alpha_{\text{X}}$
from (P1) and (P2) of Definition 4.3. Remove $(t_{i},s)$ from $T_{E}$. Then,
one of the resulting connecting components contains $r$ so we may add edge
$(r,s)$ or $(r,t_{i})$ to reconnect the graph. The change in cost is then
either $\alpha_{\text{X}}-\beta_{\text{out}}$ or
$\alpha_{\text{P}}-\beta_{\text{out}}$ which, in either case, is at most $0$.
This operation reduces the number of edges of the form $(t_{i},s)\in T_{E}$
for $t_{i}\in P$, $s\in X$, and $i\not\in\Gamma(s)$, so repeating this process
completes the proof since it yields a minimum cost $T$ satisfying the claim. ∎

######  Lemma 4.5.

We may assume that if $(t,t^{\prime})\in T_{E}$ for some $t,t^{\prime}\in P$,
then $\deg(t)=1$ or $\deg(t^{\prime})=1$ in $T$.

###### Proof.

Suppose otherwise. Let $(t,t^{\prime})\in T_{E}$ with $t,t^{\prime}\in P$ and
$\deg(t),\deg(t^{\prime})>1$. Remove $(t,t^{\prime})$. If the resultant
connected component not containing $r$ contains a Steiner point $s$, we may
add an edge $(r,s)$ to reconnect the tree. Since $\alpha_{\text{X}}\leq\tau$
by (P1), the cost of the tree does not increase.

Otherwise, without loss of generality assume that the connected component
containing $t^{\prime}$ does not contain a Steiner point and does not contain
$r$. Hence it merely contains terminals
$\\{t_{i_{1}},t_{i_{2}},\ldots,t_{i_{k}}\\}\subseteq P$. Remove all $(k-1)$
edges in this connected component. Each was of length $\tau$. Now, add an edge
$(t,t_{i_{j}})$ for $1\leq j\leq l$. This reconnects the tree and fixes its
original cost.

Note that in either case, the degree of each terminal is non-increasing.
Hence, we reduced the number of edges between terminals with both terminals
having degree $>1$, so repeating this process yields the desired result. Also
note that we do not add any edges of the form considered in Proposition 4.4,
so the two claims are consistent. ∎

######  Lemma 4.6.

$T$ includes some $s\in X$. In particular, there exists $(s,t)\in T_{E}$ such
that $s\in X$ and $t\in P$.

###### Proof.

If there are no Steiner points in $T$, then we may assume that either every
$t\in P$ is a leaf node connected to $r$ (in the case of
$\alpha_{\text{P}}<\tau$) or there exists $\widetilde{t}\in P$ such that
$\widetilde{t}$ is connected to $r$ and every other terminal is a leaf node
with an edge to $\widetilde{t}$. This is because, since $T$ is a tree, it has
a fixed number of edges. Additionally, each edge is of length
$\alpha_{\text{P}}$ or $\tau$. Then, in the former case, since
$\alpha_{\text{P}}<\tau$, there is a unique tree with all edges of length
$\alpha_{\text{P}}$ (namely connecting every universe element to $r$), and the
tree is minimum, that must be the tree. In the latter case, the minimum
possible length of the tree is having one edge of length $\alpha_{\text{P}}$
(to connect some universe element to $r$) and the rest of length $\tau$. The
described tree is such a tree.

Now, let $t_{i},t_{j},t_{k}\in P$ and $s\in X$ such that
$\Gamma(s)=\\{i,j,k\\}$. We may assume w.l.o.g. that none of the terminals are
$\widetilde{t}$ in the latter case (using $m>3$). Then, remove the edges
incident to $t_{i},t_{j},t_{k}$, disconnecting the graph into four connected
components. We may reconnect the graph by introducing $s$ as a Steiner point,
adding edges from $t_{i}$, $t_{j}$, and $t_{k}$ to $s$ and then adding an edge
from $s$ to $r$. The change in cost is
$3\beta_{\text{in}}+\alpha_{\text{X}}-3\min(\alpha_{\text{P}},\tau)$. In
either case the change in cost is negative, using (P3), contradicting
minimality of $T$. ∎

######  Lemma 4.7.

We may assume that $t\in P$ has $\deg(t)>1$ in $T$ only if $t$ is adjacent to
a Steiner point.

###### Proof.

Suppose that $t\in P$ has degree greater than $1$ but is not adjacent to any
Steiner points. By Lemma 4.5, then all of the neighbors of $t$ are either $r$
or $t^{\prime}\in P$ with $\deg(t^{\prime})=1$.

Now, if $\tau>\alpha_{\text{P}}$, removing all of $t$’s incident edges and
connecting $t$ and all of its neighbors $t^{\prime}\in P$ to $r$ reduces the
cost of the tree, preserves connectivity, and decreases the degree of $t$ to
$1$. Note that the number of edges removed equals the number of edges added.
This is because $t$ must be adjacent to $r$ since all of its neighbors are
leaf nodes from Lemma 4.5 and $T$ is connected.

If $\tau\leq\alpha_{\text{P}}$, since there must be some $\widetilde{t}\in P$
connected to a Steiner point $s$ by Lemma 4.6, we can drop all of the edges
incident to $t$ and add edges from $t$ and all its previously neighboring
terminals to $\widetilde{t}$. This does not increase the cost of the tree
since $\tau\leq\alpha_{\text{P}}$ in this case. It also preserves connectivity
of the tree.

Repeating this process then yields the claim. Note that this process is
consistent with Proposition 4.4 since it does not add any edges from Steiner
points to terminals. This process is also consistent with Lemma 4.5 since one
endpoint of every edge added between elements of $P$ in the second case is a
leaf node. ∎

######  Lemma 4.8.

We may assume that each $t\in P$ is adjacent to at most one Steiner point.

###### Proof.

Suppose otherwise, let $t_{i}\in P$ be adjacent to more than one Steiner
point. From Proposition 4.4, $t_{i}$ is adjacent only to $s\in S$ such that
$i\in\Gamma(s)$. Drop edges from $t_{i}$ to Steiner points such that $t_{i}$
remains in the connected component with $r$. Then, add the same number of
edges from $r$ to a Steiner point in each other connected component. This does
not increase the cost of $T$ since $\alpha_{\text{X}}\leq\beta_{\text{in}}$
from (P1). Additionally, this process reduces the number of elements of $P$
adjacent to more than one Steiner point, so repeating this completes the
claim.

This process is consistent with Proposition 4.4 since none of the edges
considered in that claim are added. It is consistent with Lemmas 4.5 and 4.7
since the degree of non root terminals only decreases in this process. ∎

######  Proposition 4.9.

We may assume that if $t\in P$ such that $t$ is adjacent to a Steiner point
$s$, then $t$ is not adjacent to $r$.

###### Proof.

Suppose that $(t,r)\in T_{E}$. Drop $(t,r)$ and add edge $(s,r)$. This
reconnects the tree and does not increase its cost since
$\alpha_{\text{X}}\leq\alpha_{\text{P}}$ by (P1). As usual, repeating this
process yields the desired claim. Moreover, this process is consistent with
the above claims. We do not add an edges of the form to violate Proposition
4.4 or Lemma 4.8, and we only decrease the degree of terminals so this process
is consistent with Lemmas 4.5 and 4.7. ∎

######  Lemma 4.10.

We may assume that $(s,s^{\prime})\not\in T_{E}$ for $s,s^{\prime}\in X$.

###### Proof.

First, if $\gamma_{0},\gamma_{1},\gamma_{2}\geq\alpha_{\text{X}}$, then the
result follows easily. Suppose $(s,s^{\prime})\in T_{E}$ for $s,s^{\prime}\in
X$. Then, remove the edge between them. Assume w.l.o.g. that $s$ is in the
resultant connected component with $r$. Then, add edge $(s^{\prime},r)$ to
reconnect the graph. Since
$\gamma_{i}=\Delta(s,s^{\prime})\geq\Delta(s^{\prime},r)=\alpha_{\text{X}}$,
the cost of the tree does not increase under this operation.

If instead $\gamma_{0},\gamma_{1}\geq\alpha_{\text{X}}$ but
$\gamma_{2}<\alpha_{\text{X}}$ (the only other case by (P1)), we proceed
carefully. By applying the procedure above we may assume that
$(s,s^{\prime})\in T_{E}$ only if $|\Gamma(s)\cap\Gamma(s^{\prime})|=2$. Fix
$s\in X$ with edges to other Steiner points. We may assume that $s$ has at
most $3$ neighboring Steiner points. This is because each of $s$’s neighbors
overlap $\Gamma(s)=\\{i,j,k\\}$ on two elements by Proposition 4.4, and there
are three choices of pairs of elements to overlap on ($\\{i,j\\}$,
$\\{i,k\\}$, or $\\{j,k\\}$). Hence, for all but one neighbor per pair of
overlapping set elements, the edges to $s$ can be adjusted to be edges to one
another. For example, if $s^{\prime}$ and $s^{\prime\prime}$ are Steiner
points adjacent to $s$ such that
$\\{i,j\\}\subset\Gamma(s^{\prime}),\Gamma(s^{\prime\prime})$, then
$\Delta(s^{\prime},s^{\prime\prime})=\Delta(s,s^{\prime})=\Delta(s,s^{\prime\prime})=\beta_{\text{in}}$
so the edge $(s,s^{\prime\prime})$ may be replaced by the edge
$(s^{\prime},s^{\prime\prime})$ without changing the cost or connectivity of
the tree.

Similarly, we may assume that $s$ is not adjacent to $r$ by moving an edge
from $s$ to $r$ to be an edge from $r$ to one of $s$’s neighboring Steiner
points. Now we consider two cases based on the number of neighboring Steiner
points to $s$.

#### Case 1: $s$ is adjacent to two or three Steiner points.

If $s$ is adjacent to at least two Steiner points $s^{\prime}$ and
$s^{\prime\prime}$, then
$\Gamma(s)\subseteq\Gamma(s^{\prime})\cup\Gamma(s^{\prime\prime})$ since
$|\Gamma(s)\cap\Gamma(s^{\prime})|=2$,
$|\Gamma(s)\cap\Gamma(s^{\prime\prime})|=2$, and
$\Gamma(s),\Gamma(s^{\prime}),\Gamma(s^{\prime\prime})$ are distinct sets of
size $3$. Hence, using Proposition 4.4, for each non-root terminal adjacent to
$s$, we may remove its edge to $s$ and add a new edge to $s^{\prime}$ or
$s^{\prime\prime}$ (depending on which induces less cost) without changing the
connectivity or cost of $T$.

At this point, $s$ has degree $2$ or $3$. If $s$ has degree $2$, $s$’s only
neighbors are two Steiner points $s^{\prime}$ and $s^{\prime\prime}$ such that
$|\Gamma(s^{\prime})\cap\Gamma(s^{\prime\prime})|=1$. Drop $s$ and its
incident edges. Add an edge from one of $s$’s former neighbors to $r$ to
reconnect $T$. This induces an additive cost of
$\alpha_{\text{X}}-2\gamma_{2}\leq 0$. This inequality holds since
$2\gamma_{2}\geq\gamma_{1}$ by the triangle inequality and
$\alpha_{\text{X}}\leq\gamma_{1}$ by (P1).

So, we may assume that $s$ has degree exactly $3$. But consider removing $s$
and its incident edges. This reduces the cost of $T$ by $3\gamma_{2}$. To
reconnect $T$, we add edges from $r$ to a Steiner point in each of the
connected components of $T$ not containing $r$. Both components may be clearly
contain Steiner points. This costs $2\alpha_{\text{X}}$. Hence, since
$3\gamma_{2}/2\geq\alpha_{\text{X}}$ by (P1), this does not increase the cost
of the tree.

#### Case 2: $s$ is adjacent to exactly one Steiner point.

Suppose $s$ is only adjacent to one other Steiner point, $s^{\prime}$. Then,
since $|\Gamma(s)\cap\Gamma(s^{\prime})|=2$, we can remove edges from $s$ to
all but one of its neighboring universe elements and replace those with edges
from the terminals to $s^{\prime}$ without changing the connectivity or cost
of $T$. Now, we have that $s$ is not adjacent to $r$, $s$ is adjacent to at
most one Steiner point (our present case), and $s$ is adjacent to at most one
universe element. Then, remove $s$ and its incident edges from $T$. If $s$ was
not adjacent to any terminals, the tree remains connected and its cost
decreases (and note that $s$ is not adjacent to $r$).

Otherwise, suppose that $s$ was adjacent to a universe element $t$. If $t$ had
degree greater than $1$, then, by Lemmas 4.7 and 4.8 and Proposition 4.9,
$t$’s other neighbors are exactly leaf node universe elements. Remove the
edges from those terminals to $t$ and replace those edges with edges to some
other terminal adjacent to a Steiner point (for example, some terminal
adjacent to $s^{\prime}$). This fixes the cost of the tree.

Now, add an edge from $t$ to either a terminal adjacent to a Steiner point or
$r$ (whichever edge is cheaper). This changes the cost of the tree by an
additive factor of

$\min(\alpha_{\text{P}},\tau)-\gamma_{2}-\beta_{\text{in}}\leq 0$

and reconnects the tree. The inequality holds by (P4).

Repeating this process removes all edges between Steiner points since it
reduces the number of edges between Steiner points by at least one in each
iteration.

Now we check that this process is consistent with the above claims. We do not
add any edges to violate Proposition 4.4. This process is consistent with
Lemmas 4.5 and 4.7 since the only time we add an edge between non-$r$
terminals in this process is in Case 2 and all such added edges are between a
leaf node and a terminal adjacent to a Steiner point. This process is
consistent with Lemma 4.8 since we only replace edges from non-$r$ terminals
to Steiner points with different Steiner point endpoints than adding
additional edges to Steiner points. Finally, the only time we add an edge from
a non-$r$ terminal to $r$ is in Case $2$, and we only do this when the non-$r$
terminal is a leaf node. Hence, this process is consistent with Proposition
4.9. ∎

One important consequence of the above claims is that any path between two
Steiner points in $T$ must pass through $r$. That facilitates computing the
cost of the tree. Before completing the proof, we prove a lemma that
facilitates our analysis.

######  Lemma 4.11.

We may assume that each Steiner point has degree at least $3$ in $T$.

###### Proof.

If there is a Steiner point of degree $1$, dropping the Steiner point and its
incident edge yields a lower cost tree, violating minimality of $T$. Now
suppose that $s$ is a Steiner point of degree $2$ in $T$. By Lemma 4.10 and
Proposition 4.4, $s$’s only possible neighbors are $r$ and $t_{i}\in P$ such
that $i\in\Gamma(t_{i})$. One of the two neighbors must be $r$ since $T$ is
connected and, by Lemma 4.7 and Proposition 4.9, none of $s$’s neighboring
universe elements nor their neighboring universe elements may be adjacent to
$r$. Then, $s$’s neighbors are precisely $r$ and some universe element.

If $\alpha_{\text{P}}\leq\tau$, then we may assume that $s$’s neighboring
universe element is a leaf node. In that case, drop $s$ and its incident edges
and connect $s$’s neighboring universe element to $r$. This does not increase
the cost of the tree by the triangle inequality and maintains connectivity.

If $\tau<\alpha_{\text{P}}$, let $t$ be $s$’s universe element neighbor.
Remove $s$ and its incident edges and add an edge from $r$ to $t$. As above,
this retains connectivity and does not increase the cost of the tree by the
triangle inequality. Now, the tree must have an additional Steiner point by
Lemma 4.6 (otherwise we contradict minimality). That Steiner point must be
adjacent to a universe element $\widetilde{t}$ since otherwise it is degree
$1$. But replacing the edge $(t,r)$ with an edge $(t,\widetilde{t})$ then
reduces the cost of the tree while preserving connectivity, contradicting
minimality of the tree.

Hence, degree $2$ Steiner points are only even possible when
$\alpha_{\text{P}}\leq\tau$. In that case, this simple modification is
evidently consistent with all of the above claims. ∎

######  Lemma 4.12.

The Steiner points in $T$ adjacent to $3$ terminals correspond exactly to a
maximum packing of sets in $\mathcal{S}$.

###### Proof.

By Proposition 4.4 and Lemma 4.8, we know that a given terminal $t_{i}$ is
adjacent to $s$ only if $i\in\Gamma(s)$ and is adjacent to at most one such
$s$. Then, since every $S\in\mathcal{S}$ has $|S|=3$, the Steiner points
adjacent to $3$ terminals correspond exactly to a disjoint choice of sets from
$\mathcal{S}$.

It remains to prove that this choice of sets is of maximum size. To show this,
we need to understand the cost of $T$.

Partition the edges of $T$ into three sets $E_{1},E_{2},$ and $E_{3}$ defined
as follows: edges incident to universe elements not adjacent to Steiner
points, edges incident to Steiner points adjacent to two universe elements,
and edges incident to Steiner points adjacent to three universe elements.
Lemma 4.5 and Proposition 4.9 imply that every edge without a leaf universe
element involves a Steiner point. Then, Proposition 4.4, Lemma 4.11, and the
fact that the sets in $\mathcal{S}$ are each cardinality $3$ shows that this
accounts for all for all edges in $T$.

Now, let $x_{1}$ be the number of universe elements not adjacent to Steiner
points, $x_{2}$ the number of universe elements adjacent to Steiner points
adjacent to two universe elements, and $x_{3}$ the number of universe elements
adjacent to Steiner points adjacent to three universe elements. By Lemma 4.5
and Proposition 4.9 combined with the restrictions on the adjacency of Steiner
points from Proposition 4.4 and Lemma 4.10, every Steiner point must be
adjacent to $r$ since $T$ is connected. Then, the total cost contributed by
edges in $E_{1}$ is $\min(\alpha_{\text{P}},\tau)x_{1}$,
$(\alpha_{\text{X}}/2+\beta_{\text{in}})x_{2}$ for $E_{2}$, and
$(\alpha_{\text{X}}/3+\beta_{\text{in}})x_{2}$ for $E_{3}$.

Then, the cost of $T$ is precisely

$\min(\alpha_{\text{P}},\tau)x_{1}+(\beta_{\text{in}}+\alpha_{\text{X}}/2)x_{2}+(\beta_{\text{in}}+\alpha_{\text{X}}/3)x_{3}.$

But, since
$\beta_{\text{in}}+\alpha_{\text{X}}/3<\min(\alpha_{\text{P}},\tau)$ by (P3)
and
$\beta_{\text{in}}+\alpha_{\text{X}}/3<\beta_{\text{in}}+\alpha_{\text{X}}/2$,
this cost is minimized for maximizing $x_{3}$. This means that the set of
Steiner points in $T$ adjacent to $3$ terminals must correspond to a maximum
packing of sets in $\mathcal{S}$ (by minimality of the cost of $T$). ∎

As a result of Lemma 4.12, we have the following.

######  Corollary 4.13.

In the soundness case we have

$\operatorname{\mathsf{cost}}_{\Delta}(T)\geq
n(\alpha_{\text{X}}/3+\beta_{\text{in}})\cdot\left(1-\varepsilon+\frac{(4\varepsilon-2\delta)}{3}\cdot\frac{\min(\alpha_{\text{P}},\tau,\beta_{\text{in}}+\alpha_{\text{X}}/2)}{\alpha_{\text{X}}/3+\beta_{\text{in}}}+\frac{(2\delta-\varepsilon)}{3}\cdot\frac{\min(\alpha_{\text{P}},\tau)}{\alpha_{\text{X}}/3+\beta_{\text{in}}}\right).$

###### Proof.

Define $x_{1},x_{2},$ and $x_{3}$ as in the proof of Lemma 4.12 and let
$P_{1},P_{2},$ and $P_{3}$ partition $P$ into the universe elements counted by
$x_{1}$, $x_{2}$, and $x_{3}$. From the proof of Lemma 4.12, we have that the
cost of the $T$ is given by

$\operatorname{\mathsf{cost}}_{\Delta}(T)=\min(\alpha_{\text{P}},\tau)x_{1}+(\beta_{\text{in}}+\alpha_{\text{X}}/2)x_{2}+(\beta_{\text{in}}+\alpha_{\text{X}}/3)x_{3}.$

From Lemma 4.12, this is minimized for maximum $x_{3}$. Now, as stated in
Lemma 4.12, the sets in $\mathcal{S}$ corresponding to each Steiner point
adjacent to three universe elements correspond to a packing of sets. Since we
are in the soundness case, we then have $x_{3}\leq(1-\varepsilon)n$. Since we
are lower bounding the cost of $T$ and maximizing $x_{3}$ minimizes the cost
of $T$, suppose $x_{3}=(1-\varepsilon)n$.

Now we make use of $\delta$, describing how to construct a set cover
$\mathcal{S}^{\prime}$ from $T$. For each Steiner point $s\in T$, add
$\Delta(s)$ to $\mathcal{S}^{\prime}$. For each remaining uncovered universe
element, add some set covering that element. This yields a set cover of size
at most $x_{1}+x_{2}/2+x_{3}/3$. Since we are in the soundness case (and using
$x_{3}=(1-\epsilon)n$) we have that

$x_{1}+x_{2}/2+(1-\epsilon)(n/3)\geq(1+\delta)(n/3)$

and

$x_{1}+x_{2}+(1-\epsilon)n=n.$

Then, this implies $(4\varepsilon-2\delta)/3\cdot n\geq x_{2}$. Our bound on
$\operatorname{\mathsf{cost}}_{\Delta}(T)$ then follows by maximizing $x_{2}$
when $\beta_{\text{in}}+\alpha_{\text{X}}/2<\min(\alpha_{\text{P}},\tau)$. ∎

##  5 $\mathsf{APX}$-hardness of $\mathsf{DST}$ in $\ell_{p}$-metrics

In this section, we describe the embedding of the metric Steiner tree
instances (described in the previous section), into $\mathbb{R}^{n}$ equipped
with the $\ell_{p}$-metric for $p\in(1,\infty]$. The $\mathsf{APX}$-hardness
when $p=1$ follows easily from the known $\mathsf{APX}$-hardness of
$\mathsf{CST}$ in $\ell_{1}$-metric or $\ell_{0}$-metric given in [Tre00] (or
see Theorem A.5 for a simplified reduction).

###  5.1 An Embedding into $\ell_{p}$-metric Spaces

For a given $p$, our corresponding instance of $\mathsf{DST}$ in
$\ell_{p}$-metric will be as follows. For an instance $([n],\mathcal{S})$ of
$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ where $|\mathcal{S}|=m$, let
$P=\\{\mathbf{e_{i}}\,:\,i\in[n]\\}$. Then, the set of terminals are defined
to be $\widetilde{P}=P\cup\\{\mathbf{0}\\}$ (with $r=\mathbf{0}$ the
distinguished “root” terminal). Let $\theta_{p}$ be a scalar defined for each
$p$. Then, the set of facilities is defined to be

$X=\\{\theta_{p}\cdot(\mathbf{e_{i}}+\mathbf{e_{j}}+\mathbf{e_{k}})\,:\,\\{i,j,k\\}\in\mathcal{S}\\}.$

We choose $\theta_{p}$ such that the following properties hold:

  1. 1.

$0<\theta_{p}\leq 1/2$ and

  2. 2.

$3((1-\theta_{p})^{p}+2\theta_{p}^{p})^{1/p}+(3\theta_{p}^{p})^{1/p}<3.$

Note that this is possible since, for

$f_{p}(x)=3((1-x)^{p}+2x^{p})^{1/p}+(3x^{p})^{1/p}-3$

we have $f_{p}(0)=0$ and $\frac{df_{p}(0)}{dx}=-3+3^{1/p}<0$ for $p>1$. This
point configuration induces a complete graph $G=(\widetilde{P}\cup X,E)$ with
edge costs given by distances in the $\ell_{p}$-metric.

Now, we check that the conditions of Theorem 4.2 hold. Clearly our choices of
distances are metric compatible since they arise from a metric space.

######  Remark 5.1.

Note that, for $p\in(1,\infty)$,

  * •

$\alpha_{\text{X}}=3^{1/p}\theta_{p}$,

  * •

$\alpha_{\text{P}}=1$,

  * •

$\beta_{\text{in}}=((1-\theta_{p})^{p}+2\theta_{p}^{p})^{\frac{1}{p}}$,

  * •

$\beta_{\text{out}}=(1+3\theta_{p}^{p})^{\frac{1}{p}}$,

  * •

$\gamma_{0}=6^{1/p}\theta_{p}$,

  * •

$\gamma_{1}=4^{1/p}\theta_{p}$,

  * •

$\gamma_{2}=2^{1/p}\theta_{p}$, and

  * •

$\tau=2^{1/p}$.

When $p=\infty$, we instead have

  * •

$\alpha_{\text{X}}=\gamma_{0}=\gamma_{1}=\gamma_{2}=\theta_{p}$,

  * •

$\alpha_{\text{P}}=\beta_{\text{out}}=\tau=1$, and

  * •

$\beta_{\text{in}}=1-\theta_{p}$.

######  Proposition 5.1.

For each $p\in(1,\infty]$, the corresponding tuple
$(\alpha_{\text{X}},\alpha_{\text{P}},\beta_{\text{in}},\beta_{\text{out}},\gamma_{0},\gamma_{1},\gamma_{2},\tau)$
from the above is Steiner embeddable.

###### Proof.

For all $p$, the tuple is clearly metric compatible since it arises from a
metric space. It clear that (P1), (P2), (P3), and (P4) hold when $p=\infty$.
Now we prove that these constraints hold when $p$ is finite. Note first that

$\displaystyle 3^{1/p}\theta_{p}$
$\displaystyle\leq((1-\theta_{p})^{p}+2\theta_{p}^{p})^{1/p}$
$\displaystyle<((1-\theta_{p})^{p}+2\theta_{p}^{p})^{1/p}+3^{1/p}\theta_{p}/3<1\leq
2^{1/p}.$

The first inequality follows from $0<\theta_{p}\leq 1/2$ and the last
inequality follows from
$3((1-\theta_{p})^{p}+2\theta_{p}^{p})^{1/p}+(3\theta_{p}^{p})^{1/p}<3.$ This
immediately implies
$\alpha_{\text{X}}\leq\alpha_{\text{P}},\beta_{\text{in}},\tau$. Since
$0<\theta_{p}\leq 1/2$, $\beta_{\text{in}}<\beta_{\text{out}}$, and
$\alpha_{\text{X}}\leq\gamma_{1},\gamma_{2}$ is clear. Also observe that
${}_{st}\leq 3\gamma_{2}/2$ if and only if $(3/2)^{\frac{1}{p}}\leq 3/2$ which
holds for all $p\geq 1$. This proves (P1) holds. The inequality
$\alpha_{\text{P}}\leq\beta_{\text{out}}$ is immediate (showing (P2)) and
$\beta_{\text{in}}+\frac{\alpha_{\text{X}}}{3}<\min(\alpha_{\text{P}},\tau)$
holds by our choice of $\theta_{p}$ (showing (P3)).

It then remains to show
$\min(\alpha_{\text{P}},\tau)\leq\beta_{\text{in}}+\gamma_{2}$, (P4). But note
that

$1=(1-\theta_{p})+\theta_{p}\leq\beta_{\text{in}}+\gamma_{2},$

completing the proof. ∎

Then, applying Theorem 4.2, we have the following.

######  Theorem 5.2.

Let $p\in(1,\infty)$. Suppose that

  1. 1.

$0<\theta_{p}\leq 1/2$,

  2. 2.

$3[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+3^{\frac{1}{p}}\theta_{p}<3$,

  3. 3.

$(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard.

Then, $\mathsf{DST}$ in the $\ell_{p}$-metric is $\mathsf{NP}$-hard to
approximate within a factor of

$(1-\varepsilon)+\frac{(4\varepsilon-2\delta)}{3}\cdot\frac{\min(1,[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+\frac{3^{1/p}}{2}\theta_{p})}{[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+3^{\frac{1-p}{p}}\theta_{p}}+\frac{(2\delta-\varepsilon)}{3}\cdot\frac{1}{[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+3^{\frac{1-p}{p}}\theta_{p}}>1.$

In particular, for all $p\in(1,\infty)$, there exists $\theta_{p}$ such that
the first two conditions above hold and Theorem 2.1 implies
$(\varepsilon_{0},\varepsilon_{0}/2)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard
for some $\varepsilon_{0}>0$.

######  Remark 5.2.

Curiously, we observe that the importance of $\varepsilon$ and $\delta$
depends dramatically on $p$. For $p\in(1,1/\log_{3}(4/3))$, $\delta$ is
sometimes irrelevant. This occurs when $\theta_{p}$ is chosen such that
$1<[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}$. Intuitively, this
means that in the soundness case, the optimal Steiner tree not only
corresponds to a maximal set packing (as proved in Lemma 4.12), but also that
the terminals (universe elements) that are not yet covered by the packing,
would like to connect by an edge directly with the root in the optimal Steiner
tree, instead of having two terminals (universe elements) connecting to a
common Steiner point (which is then connected to the root). This happens for
$\theta_{2}=1/6$, for example. See Figure 1.

By applying the Fréchet embedding to the hard instance in Theorem 4.2, we have
that only $\delta$ is relevant to the hardness of $\mathsf{DST}$ in
$\ell_{\infty}$-metric (and not $\varepsilon$). In many other settings, it
appears that both $\varepsilon$ and $\delta$ play a role with larger $\delta$
permitting better hardness of approximation. Below we prove the non-dependency
of $\varepsilon$ for $\mathsf{DST}$ in $\ell_{\infty}$-metric, without
invoking the Fréchet embedding.

######  Theorem 5.3.

If $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard, then
$\mathsf{DST}$ in $\ell_{\infty}$-metric is $\mathsf{NP}$-hard to approximate
within a factor of $1+\delta/4$.

###### Proof.

Note that $\theta_{\infty}=1/2$ satisfies the required properties for
Proposition 5.1. Then, from Corollary 4.3, it suffices to simply check that,
for $p=\infty$,
$\beta_{\text{in}}+\alpha_{\text{X}}/2=\min(\alpha_{\text{P}},\tau,\beta_{\text{in}}+\alpha_{\text{X}}/2)$,
$\min(\alpha_{\text{P}},\tau)=\alpha_{\text{X}}+\beta_{\text{in}}$, and
$\beta_{\text{in}}=\alpha_{\text{X}}$. This is clear from observing the
distances in Remark 5.1. ∎

######  Corollary 5.4.

For all $p\in[1,\infty]$, $\mathsf{DST}$ in $\ell_{p}$-metric is
$\mathsf{APX}$-hard.

###### Proof.

The case of $\mathsf{DST}$ in $\ell_{1}$-metric follows from the known
$\mathsf{APX}$-hardness of $\mathsf{CST}$ in $\ell_{1}$-metric or
$\ell_{0}$-metric given in [Tre00] (or see Theorem A.5). The cases of
$p\in(1,\infty)$ and $p=\infty$ follow from Theorems 5.2 and 5.3,
respectively. ∎

###  5.2 Hardness of Approximating $\mathsf{DST}$ in $\ell_{p}$-metrics

Optimizing for the choice of $\theta_{p}$, we have the following.

######  Corollary 5.5.

If $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard, then for
$p\in[\frac{1}{\log_{3}(4/3)},\infty]$, $\mathsf{DST}$ in $\ell_{p}$-metric is
$\mathsf{NP}$-hard to approximate within a factor

$1+\varepsilon\left(\frac{1}{2}-\frac{1}{2\cdot
3^{1/p}}\right)+2\delta\left(\frac{1}{2\cdot 3^{1/p}}-\frac{3}{8}\right).$

In particular, we have $\mathsf{DST}$ in $\ell_{p}$-metric is
$\mathsf{NP}$-hard to approximate within a factor of $1+\varepsilon/8$.

###### Proof.

The second part of the claim occurs when $\delta=\varepsilon/2$. In this case,
the second fractional term in Theorem 5.2 is nullfied. Then, observe that, for
a fixed $p$, while

$[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+\frac{3^{1/p}}{2}\theta_{p}\leq
1,$

the hardness of approximation factor is maximized for maximal $\theta_{p}$. By
our constraints on $\theta_{p}$, $\theta_{p}\leq 1/2$. When $\theta_{p}=1/2$
is valid we have

$3[(1-1/2)^{p}+2(1/2)^{p}]^{\frac{1}{p}}+3^{\frac{1}{p}}(1/2)=2\cdot
3^{1/p}<3.$

This then holds for $\frac{1}{\log_{3}(3/2)}<p.$ Additionally,

$[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+\frac{3^{1/p}}{2}\theta_{p}\leq
1,$

holds for $\theta_{p}=1/2$ if and only if $3^{1/p}\cdot\frac{3}{4}\leq 1$ so
$p\geq\frac{1}{\log_{3}(4/3)}.$ Hence, for
$p\in[\frac{1}{\log_{3}(4/3)},\infty]$, the embedding with $\theta_{p}=1/2$
yields that $\mathsf{DST}$ in $\ell_{p}$-metric is hard to approximate within
a factor of $1+\varepsilon/8$.

If $(\varepsilon,\delta)$-$\mathsf{SP_{3}}$ is $\mathsf{NP}$-hard for
$\delta>\varepsilon/2$, we get improved hardness for
$p\in[\frac{1}{\log_{3}(4/3)},\infty]$ by using $\theta_{p}=1/2$. Computing
yields the claimed expression. ∎

When $\delta>\varepsilon/2$, optimizing the hardness exactly is more
challenging. This is because, for $p$ finite, the maximum value of

$\frac{1}{[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}}$

arises for $\theta_{p}<1/2$, so the optimal value depends intimately on
$\delta$. Likewise, when $p\in(1,\frac{1}{\log_{3}(4/3)})$, we need
$\theta_{p}<1/2$. At that point even finding a permissible choice of
$\theta_{p}$ requires an explicit computation.

We summarize the dependence of the hardness of $\mathsf{DST}$ in
$\ell_{p}$-metric on $\varepsilon$ and $\delta$ (and therefore the dependence
on the hardness of Set Packing and Set Cover) in Figure 1. The purple region,
$p\in\\{1,\infty\\}$, is the range where there is no dependency on
$\varepsilon$, and hence the reduction only uses the hardness of set packing
(see Corollary 4.3 and Theorem A.5). In the red range,
$[1/(\log_{3}(4/3),\infty)$, we show in Corollary 5.5 a dependency on both
$\varepsilon$ and $\delta$.

The behavior in the yellow range is less clear. For $p$ such that the optimal
choice of $\theta_{p}$ satisfies

$[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+\frac{3^{1/p}}{2}\theta_{p}<1,$

the hardness depends both on $\delta$ and $\varepsilon$; larger $\delta$ will
yield increased hardness of approximation. This is, however, not the case for
all values of $p$ in the yellow region. The choice of $p=2$ is a notable
exception (see Corollary A.1). In the green region there is no dependence on
$\delta$. This is because the optimal choice of $\theta_{p}$ satisfies

$[(1-\theta_{p})^{p}+2\theta_{p}^{p}]^{\frac{1}{p}}+\frac{3^{1/p}}{2}\theta_{p}\geq
1.$

##  6 $\mathsf{APX}$-hardness of $\mathsf{CST}$ in $\ell_{\infty}$-metric

The main result of this section is the following.

######  Theorem 6.1.

There is a polynomial time reduction from a graph $G$ of order $n$ to an
instance of $\mathsf{CST}$ in the $\ell_{\infty}$-metric such that the optimal
cost of the Steiner tree is $(n+\chi(G))/2$.

In [CFF+08], they study the problem of partitioning a cubic graph into the
minimum number of independent cliques. The minimum size of such a partition is
the minimum size of a partition of the complement graph into independent sets,
the chromatic number of the complement graph. In particular, they show the
following.

######  Theorem 6.2 ([CFF+08], Theorem 7).

There exist constants $\varepsilon_{1}<\varepsilon_{2}$ such that
$(\varepsilon_{1}n,\varepsilon_{2}n)$-coloring is $\mathsf{NP}$-hard.

The combination of Theorems 6.1 and 6.2 implies that $\mathsf{CST}$ in the
$\ell_{\infty}$-metric is $\mathsf{APX}$-hard.

######  Corollary 6.3.

$\mathsf{CST}$ in the $\ell_{\infty}$-metric is $\mathsf{APX}$-hard.

Now we prove Theorem 6.1. Given an undirected simple graph, we arbitrarily
direct/orient the edges in the graph to form a digraph $G(V,A)$. Define the
function $\Gamma:V\to\mathbb{R}^{|A|}$ such that, for all $i\in V$,

$\Gamma(i)=\left(\sum_{(i,j)\in
A}\mathbf{e_{(i,j)}}\right)-\left(\sum_{(j,i)\in A}\mathbf{e_{(j,i)}}\right),$

where $\mathbf{e_{(i,j)}}$ is the standard basis vector in $\mathbb{R}^{|A|}$
with $1$ in the coordinate corresponding to the directed edge $(i,j)$ and $0$
elsewhere. Let $P=\\{\Gamma(i)\mid\,i\in V\\}$. Our corresponding instance of
$\mathsf{CST}$ in the $\ell_{\infty}$-metric is on the set of terminals
$\widetilde{P}=P\cup\\{\mathbf{0}\\}$. We will refer to $\mathbf{0}$ as the
root terminal.

In the spirit of the language of gap-preserving reductions, we refer to the
case of showing that the optimal cost of a Steiner tree of $\widetilde{P}$ is
at most $(n+\chi(G))/2$ as the completeness case. Similarly, the case of
showing that the optimal cost of a Steiner tree of $\widetilde{P}$ is at least
$(n+\chi(G))/2$ is the soundness case.

###  6.1 Completeness Case

Let $\pi:V\to[a]$ be a proper $a$-coloring of the vertices in $G$. Let $A^{+}$
and $A^{-}$ be two distinct partitions of $A$ where for every $k\in[a]$, the
$k\textsuperscript{th}$ part of $A^{+}$ is $A^{+}(k):=\\{(i,j)\in
A\mid\pi(i)=k\\}$ and the $k\textsuperscript{th}$ part of $A^{-}$ is
$A^{-}(k)=\\{(j,i)\in A\mid\pi(i)=k\\}$. Define
$\sigma:[a]\to\mathbb{R}^{|A|}$ as follows. The function $\sigma$ will map
each color class to a Steiner point. We have

$\forall k\in[a],\ \sigma(k)=\left(\sum_{f\in
A^{+}(k)}\frac{1}{2}\cdot\mathbf{e_{f}}\right)-\left(\sum_{f\in
A^{-}(k)}\frac{1}{2}\cdot\mathbf{e_{f}}\right).$

Now, our set of Steiner points will be exactly the set $\\{\sigma(k)\mid
k\in[a]\\}$. Note that, since $\pi$ is a proper coloring, for all $k\in[a]$,
$A^{+}(k)\cap A^{-}(k)=\emptyset$. We create our Steiner tree as follows. Add
an edge from each Steiner point $\sigma(k)$ to the root terminal $\mathbf{0}$.
Additionally, add an edge from each non-root terminal $t\in P$ to the Steiner
point $\sigma(\pi(\Gamma^{-1}(t)))$. Note that $\sigma(\pi(\Gamma^{-1}(t)))$
is the Steiner point corresponding to the color class corresponding to the
vertex mapped to terminal $t$. See Figure 4.

Note that the resultant Steiner tree is connected and every edge has length
$1/2$. This length is clear for the edges from Steiner points to the root
terminal. Now fix some $t\in P$. In particular, if $t_{f}=1$, then $f\in
A^{+}(\pi(\Gamma^{-1}(t))).$ That is, in this case,
$\sigma(\pi(\Gamma^{-1}(t)))_{f}=1/2$ since $\pi$ is a proper coloring.
Similarly, if $t_{f}=-1$, then $f\in A^{-}(\pi(\Gamma^{-1}(t)))$. Hence, in
this case, $\sigma(\pi(\Gamma^{-1}(t)))_{f}=-1/2$. Note that
$\left\lVert\sigma(\pi(\Gamma^{-1}(t)))\right\rVert_{\infty}=1/2$ by
definition, so, namely, if $t_{f}=0$, $|\sigma(\pi(\Gamma^{-1}(t)))_{f}|\leq
1/2$. Altogether, this implies that
$\left\lVert\sigma(\pi(\Gamma^{-1}(t)))-t\right\rVert_{\infty}=1/2$.

Hence, this constructed tree has total cost $(n+a)/2$. In particular, the
optimal cost of a Steiner tree in this instance of $\mathsf{CST}$ in the
$\ell_{\infty}$-metric is at most $(n+\chi(G))/2$.

Non-root Terminals $\displaystyle(P)$Steiner PointsRoot Terminal
($\displaystyle\mathbf{0}$)$\displaystyle{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}\sigma}{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}(}{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11}1}{\color[rgb]{0.82,0.01,0.11}\definecolor[named]{pgfstrokecolor}{rgb}{0.82,0.01,0.11})}$$\displaystyle{\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}\sigma}{\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}(}{\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14}2}{\color[rgb]{0.96,0.65,0.14}\definecolor[named]{pgfstrokecolor}{rgb}{0.96,0.65,0.14})}$$\displaystyle{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02}\sigma}{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02}(}{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02}3}{\color[rgb]{0.25,0.46,0.02}\definecolor[named]{pgfstrokecolor}{rgb}{0.25,0.46,0.02})}$$\displaystyle{\color[rgb]{0.74,0.06,0.88}\definecolor[named]{pgfstrokecolor}{rgb}{0.74,0.06,0.88}\sigma}{\color[rgb]{0.74,0.06,0.88}\definecolor[named]{pgfstrokecolor}{rgb}{0.74,0.06,0.88}(}{\color[rgb]{0.74,0.06,0.88}\definecolor[named]{pgfstrokecolor}{rgb}{0.74,0.06,0.88}a-2}{\color[rgb]{0.74,0.06,0.88}\definecolor[named]{pgfstrokecolor}{rgb}{0.74,0.06,0.88})}$$\displaystyle{\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}\sigma}{\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}(}{\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1}a-1}{\color[rgb]{0.56,0.07,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.07,1})}$$\displaystyle{\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}\sigma}{\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}(}{\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89}a}{\color[rgb]{0.29,0.56,0.89}\definecolor[named]{pgfstrokecolor}{rgb}{0.29,0.56,0.89})}$$\displaystyle\Gamma\left(\pi^{-1}(1)\right)$$\displaystyle\Gamma\left(\pi^{-1}(2)\right)$$\displaystyle\Gamma\left(\pi^{-1}(3)\right)$$\displaystyle\Gamma\left(\pi^{-1}(a-2)\right)$$\displaystyle\Gamma\left(\pi^{-1}(a-1)\right)$$\displaystyle\Gamma\left(\pi^{-1}(a)\right)$$\displaystyle\cdots$$\displaystyle\cdots$$\displaystyle\cdots$$\displaystyle\cdots$$\displaystyle\cdots$$\displaystyle\cdots$$\displaystyle\cdots$
Figure 4: Steiner tree of $P$ constructed from an $a$-coloring of $G$

###  6.2 Soundness Case

It remains to show that the optimal cost of a Steiner tree of $\widetilde{P}$
in the $\ell_{\infty}$-metric is at least $(n+\chi(G))/2$. To do so, we prove
a series of lemmas which in tandem show that the Steiner tree constructed in
the completeness case is in fact optimal.

######  Lemma 6.4.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree of $\widetilde{P}$.
Then, for all $(u,v)\in E$, we have $\left\lVert u-v\right\rVert_{\infty}\leq
1.$

###### Proof.

Suppose $T$ has some edge of length greater than $1$. Remove the edge from
$T$. Now, the resultant graph $T^{\prime}$ is split into two connected
components. This yields a partition of the terminals in $\widetilde{P}$ into
two parts. If one part contains no terminals, dropping that part yields a
lower cost tree.

Otherwise, consider the minimum spanning tree of the terminals in
$\widetilde{P}$. All edges have length $1$. Namely, since it is a spanning
tree, it has some edge crossing the cut induced by the partition of terminals
in $T^{\prime}$. Adding that edge to $T^{\prime}$ forms a new Steiner tree of
cost less than $T$, contradicting minimality of $T$ and proving the claim. ∎

For ease of notation, in the remainder of this section we will make use of the
following function $\operatorname{sgn}:\mathbb{R}\to\\{-1,0,1\\}$, where

$\operatorname{sgn}(x)=\begin{cases}-1,&\text{if }x<0;\\\ 0,&\text{if }x=0;\\\
1,&\text{if }x>0.\end{cases}$

With Lemma 6.5, we begin showing that there are optimal Steiner trees which
are highly structured.

######  Lemma 6.5.

There exists an optimal Steiner tree $T(\widetilde{P}\cup X,E)$ with the
following two properties.

  1. (P1)

Rapid decay: For all edges $(u,v)\in E$ with $u\in P\cup X$ and $v\in X$, if
$u_{i}\neq 0,v_{i}\neq 0,$ and
$\operatorname{sgn}(u_{i})=\operatorname{sgn}(v_{i})$, then
$|u_{i}-v_{i}|=\|u-v\|_{\infty}$.

  2. (P2)

Short edges: Each edge $(u,v)$ for $u,v\in P\cup X$ satisfies
$\|u-v\|_{\infty}<1.$

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree of $\widetilde{P}$.
Consider the $i$th coordinate (corresponding to some arc in $G(V,A)$). First,
note that there are exactly two terminals in $P$ with nonzero $i$th
coordinate. Let $t$ be the terminal such that $t_{i}=1$. Root $T$ at $t_{i}$
in the sense of directing each edge in $T$ away from $t_{i}$. Suppose that
$(u,v)$ is a directed edge in $T$ such that $u_{i},v_{i}>0$, and
$\|u-v\|_{\infty}\neq u_{i}-v_{i}$. Note that this is only possible for $u\in
P\cup X$ and $v\in X$.

We construct a new Steiner tree $T^{\prime}$ with
$\operatorname{\mathsf{cost}}_{\infty}(T^{\prime})\leq\operatorname{\mathsf{cost}}_{\infty}(T)$.
The tree $T^{\prime}$ will be the same as $T$ except for the following
modifications. Set $v_{i}^{\prime}:=\max(0,u_{i}-\|u-v\|_{\infty})$. Since
$v_{i}>v_{i}^{\prime}\geq 0$, and, for all terminals other than $t$ we have
$t_{i}\leq 0$, this cannot increase the length of edges to terminals (compared
to $T$). This is because, by Lemma 6.4, since $v_{i}>0$, $v$ cannot be
adjacent to terminals other than $t$.

Now, if for all directed edges $(v,w)$ in $T$ with $w\in X$ we have
$v_{i}^{\prime}\geq w_{i}$, then we have
$\operatorname{\mathsf{cost}}_{\infty}(T^{\prime})\leq\operatorname{\mathsf{cost}}_{\infty}(T)$
(since $v_{i}\geq v_{i}^{\prime}$). Otherwise, suppose there exists some $w$
such that $v_{i}^{\prime}<w_{i}$. Then, set $w_{i}^{\prime}:=v_{i}^{\prime}$.
Then, if for all $(w,x)$ we have $w_{i}^{\prime}=v_{i}^{\prime}\geq x_{i}$, we
have
$\operatorname{\mathsf{cost}}_{\infty}(T^{\prime})\leq\operatorname{\mathsf{cost}}_{\infty}(T)$.
Otherwise, repeat this process, setting $x_{i}^{\prime}:=v_{i}^{\prime}$,
checking the $i$th coordinate of the out-neighbors of $x^{\prime}$ in
$T^{\prime}$ and setting their $i$th coordinates to $v_{i}^{\prime}$ if they
are greater. Since $T^{\prime}$ is acyclic and finite, this process will
eventually terminate.

Repeat this process for all other directed edges $(u,v)$ with $u_{i},v_{i}>0$,
and $\|u-v\|_{\infty}\neq u_{i}-v_{i}$, treating the newly created optimal
Steiner tree $T^{\prime}$ as $T$ and the resultant tree as $T^{\prime}$. Then,
further repeat this process for all other coordinates $i$. Afterward, repeat
this process for all coordinates $i$, except this time for all edges $(u,v)$
with $u_{i},v_{i}<0$ and $\|u-v\|_{\infty}\neq v_{i}-u_{i}$. For negative
coordinates and a directed edge $(u,v)$ such that $u_{i},v_{i}<0$ and
$\|u-v\|_{\infty}\neq v_{i}-u_{i}$, we will set
$v_{i}^{*}:=\min(0,u_{i}+\|u-v\|_{\infty})$. Since each round of modifying the
tree only affects a single coordinate (and only Steiner points which are
nonzero and of a given sign in those coordinates), this yields (P1).

Before we modify the tree further to ensure (P2), we observe that (P1) implies
a useful property of the Steiner points in the Steiner tree.

######  Claim 6.5.1.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree satisfying (P1).
Then, for all Steiner points $s\in X$, $\left\lVert s\right\rVert_{\infty}<1.$

###### Proof.

Let $t\in P$ be the unique terminal with $t_{i}=1$. Then, suppose that $s\in
X$ is a Steiner point adjacent to $t$. From Lemma 6.4, $s_{i}\geq 0$. Since
the distance between any two points in $T$ is greater than $0$ (assuming no
degenerate Steiner points), from (P1), $s_{i}<1$. Then, consider rooting $T$
at $t$. (P1) immediately implies that the $i\textsuperscript{th}$ coordinate
of any Steiner point not adjacent to $t$ is at most the maximum
$i\textsuperscript{th}$ coordinate of the Steiner points adjacent to $t$. This
observation holds for any coordinate $i$ and holds similarly for negatively
signed coordinates, yielding the claim. ∎

Now, suppose that $T^{\prime}$ is the optimal Steiner tree resultant from the
modifications for ensuring (P1). Let $(u,v)$ be an edge with $u,v\in P\cup X$.
By Lemma 6.4, $\|u-v\|_{\infty}\leq 1$. If $\|u-v\|_{\infty}=1$, consider
removing the edge $(u,v)$, thereby disconnecting the tree. One of $u$ or $v$
will be in the same resultant connected component as $\mathbf{0}$. Connect the
other to $\mathbf{0}$, reconnecting the tree with an edge of cost at most $1$.
Repeating this process yields (P2) since all edges added in each iteration of
this process involve $\mathbf{0}$ and each iteration removes an edge in
violation of (P2). Since this process only removes edges and adds edges
adjacent to $\mathbf{0}$, the resultant tree still satisfies (P1). ∎

Optimal Steiner trees with the properties of Lemma 6.5 have some other useful
properties.

######  Corollary 6.6.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree satsfying the
properties of Lemma 6.5. Then, for all $t,t^{\prime}\in P$,
$(t,t^{\prime})\not\in E$.

###### Proof.

Note that for all $t,t^{\prime}\in P$ distinct, $\|t-t^{\prime}\|_{\infty}\geq
1$. (P2) then implies the desired result. ∎

######  Corollary 6.7.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree satisfying the
properties of Lemma 6.5. Then, for all coordinates $i$ and $t,t^{\prime}\in P$
such that $t_{i}=1$ and $t_{i}^{\prime}=-1$, there does not exist Steiner
point $s\in X$ such that $(t_{i},s),(t_{i}^{\prime},s)\in E$. That is, $t$ and
$t^{\prime}$ do not share a common neighboring Steiner point.

###### Proof.

Suppose otherwise. Then, consider $s_{i}$. (P2) implies that $s_{i}>0$ and
$s_{i}<0$, a contradiction. ∎

We now proceed by a series of lemmas extending the structural constraints
established in Lemma 6.5.

######  Lemma 6.8.

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

  1. (P3)

Terminal connectivity: For all $t\in P$, $t$ is a leaf node.

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be an optimal Steiner tree satisfying (P1) and
(P2) (such a tree exists from Lemma 6.5). We modify $T$ without increasing the
cost to yield the desired Steiner tree.

First, by Corollary 6.6, there are no edges between non-root terminals in $T$.
Now, suppose that $t\in P$ is adjacent to $\mathbf{0}$ and some Steiner point
$s$. Note that $t$ may be adjacent to other Steiner points. Drop the edge from
$t$ to $\mathbf{0}$ and replace it with an edge from $\mathbf{0}$ to $s$. From
Claim 6.5.1, this decreases the cost of $T$, contradicting minimality.

Finally, suppose that $t$ is adjacent to at least two Steiner points and is
not adjacent to $\mathbf{0}$. Consider the subtrees of $T$ that would contain
these Steiner points if we removed $t$ from the tree. In particular, one of
the subtrees must contain $\mathbf{0}$ and the others cannot contain
$\mathbf{0}$. Let $s$ be a Steiner point adjacent to $t$ whose resultant
subtree does not contain $\mathbf{0}$. Call the subtree $T_{s}$. Now, drop the
edge from $s$ to $t$. For each coordinate $i$ such that $t_{i}\neq 0$, for all
Steiner points $s^{\prime}$ in $T_{s}$, if
$\operatorname{sgn}(s^{\prime}_{i})=\operatorname{sgn}(t_{i})$, set
$s^{\prime}_{i}=0$. This cannot increase the cost of $T_{s}$—the length of
edges between Steiner points cannot increase, the length of edges between
Steiner points and terminals with $i\textsuperscript{th}$ coordinate $0$
cannot increase, and, by (P2), any Steiner points adjacent to the terminal
with opposite sign $i\textsuperscript{th}$ coordinate are unaffected. Now add
an edge from $s$ to $\mathbf{0}$, reconnecting the tree. In particular, we now
have $s_{j}\neq 0$ only if $t_{j}=0$, so $\|s\|_{\infty}$ is at most the
former distance between $s$ and $t$. Hence, these modifications did not
increase the cost of the tree and removed a neighbor of $t$ without adding any
neighbors to a nonzero terminal. Repeating this process—for other Steiner
points $s$ adjacent to $t$ such that their subtrees resultant from removing
$t$ do not contain $\mathbf{0}$—yields (P3). Crucially, these modifications
are consistent with (P1) and (P2). After making these modifications, the tree
remains optimal and we can re-apply the modifications detailed in the proof of
Lemma 6.5 to ensure (P1) and (P2) since those modifications do not add edges
to any terminals in $P$. ∎

Optimal Steiner trees with properties (P1), (P2), and (P3) reflect some the
structure of the Steiner trees constructed in the completeness case. In
particular, Corollary 6.7 combined with (P3) shows that these optimal Steiner
trees induce a proper coloring of $V$. The color classes are defined by the
(unique) Steiner points adjacent to non-root terminals, and each non-root
terminal adjacent to $\mathbf{0}$ has its own color class. Given some optimal
Steiner tree with properties (P1), (P2), and (P3), the induced coloring of $V$
is given by the function $\pi_{T}$. Denote the set of non-root terminals
adjacent to a Steiner point $s$ by $P(s)$ (note that $\Gamma^{-1}(P(s))$ is a
color class defined by $\pi_{T}$).

Equipped with these structural observations, additional completeness structure
emerges in the following lemma. In the statement of the lemma, $\sigma$ is
defined exactly as in Section 6.1, induced by the coloring $\pi_{T}$. In other
words, for all Steiner points $s$ only adjacent to non-root terminals and
$\mathbf{0}$, if $s$ is adjacent to some terminal $t$ with $t_{i}\neq 0$, then
$s_{i}=t_{i}/2$.

######  Lemma 6.9.

There exists an optimal Steiner tree $T(\widetilde{P}\cup X,E)$ satisfying
(P1), (P2), and (P3), and the following additional property.

  1. (P4)

Completeness structure: For all Steiner points $s$ only adjacent to non-root
terminals and $\mathbf{0}$, we have $s=\sigma(\pi_{T}(\Gamma^{-1}(P(s))))$.

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be a Steiner tree satisfying (P1), (P2), and
(P3). Consider some such Steiner point $s$ in $T$ adjacent to only non-root
terminals and $\mathbf{0}$. Note that, by (P3), since nonzero terminals are
leaf nodes, $s$ must be adjacent to $\mathbf{0}$ so that $T$ is connected.

First, we may assume that if $s_{i}\neq 0$, then there exists $t\in P(s)$ such
that $t_{i}\neq 0$. Otherwise setting $s_{i}=0$ does not increase the cost of
the tree.

Next, if there exists $t\in P(s)$ with $t_{i}=1$, then, by Corollary 6.7,
$t^{\prime}$ such that $t^{\prime}_{i}=-1$ is not an element of $P(s)$.
Moreover, (P2) then implies that $s_{i}>0$. The analogous facts are true if
there exists $t\in P(s)$ with $t_{i}=-1$.

Now suppose that $\left\lVert s\right\rVert_{\infty}=1/2+\varepsilon$ for some
$\varepsilon>0$. Then, for each $i$ such that $s_{i}>0$, set
$s_{i}=\min(s_{i},1/2)$, and, for each $j$ such that $s_{j}<0$, set
$s_{j}=\max(s_{j},-1/2)$. Note that, for at most one $t\in P(s)$,
$\|s-t\|_{\infty}$ will increase as a result of this operation (and it will
increase by at most $\varepsilon$). However, $\|s\|_{\infty}$ will decrease by
$\varepsilon$, implying that the overall cost of the tree does not increase as
a result of this operation (due to the edge to $\mathbf{0}$).

Finally, suppose that there is some $i$ such that $0<|s_{i}|<1/2$. Let

$\min_{\\{i\,:\,0<|s_{i}|<1/2\\}}|s_{i}|=1/2-\varepsilon$

for some $\varepsilon>0$ and let

$i_{0}=\operatorname*{arg\,min}_{\\{i\,:\,0<|s_{i}|<1/2\\}}|s_{i}|.$

Let $\widetilde{t}$ be a terminal in $P(s)$ such that
$|s_{i_{0}}|=1/2-\varepsilon$ and $\widetilde{t}_{i_{0}}\neq 0$. Then, for
each $i$ such that $s_{i}>0$, set $s_{i}=1/2$ and for each $j$ such that
$s_{j}<0$, set $s_{j}=-1/2$. Now, this modification decreases the distance
from $s$ to $\widetilde{t}$ by $\varepsilon$ while increasing the distance
from $\mathbf{0}$ to $s$ by at most $\varepsilon$. Moreover, for all $t\in
P(s)$, this does not increase $\|t-s\|_{\infty}$ since, from the previous
modification, $\|t-s\|_{\infty}\geq 1/2$. Hence, this does not increase the
cost of $T$ and yields (P4). Note that (P1), (P2), and (P3) are all preserved
under these operations. ∎

Lemma 6.9 shows that when Steiner points are not adjacent to other Steiner
points, they appear exactly like Steiner points in the completeness case. Our
next objective is then to show that we may assume there are no edges between
Steiner points. To do so, we will first consider the most “extremal” Steiner
points which are not accounted for by Property (P4). Let $T(\widetilde{P}\cup
X,E)$ be an optimal Steiner tree satisfying (P1), (P2), (P3), and (P4). Then,
removing all terminals in $P$ will result in a smaller (connected) tree since
all such terminals are leaf nodes by (P3). Call the non-terminal leaf nodes in
the resultant tree Steiner leaves. We show that Steiner leaves are highly
structured in Lemma 6.10.

######  Lemma 6.10.

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

  1. (P5)

Steiner leaf structure: For all Steiner leaves $s\in X$, $\|s\|_{\infty}=1/2$
. Moreover, for each coordinate $i$ such that there exists $t\in P(s)$ with
$t_{i}\neq 0$, $|s_{i}|=1/2$.

###### Proof.

Let $T(\widetilde{P}\cup X,E)$ be a Steiner tree satisfying (P1), (P2), (P3),
and (P4). Suppose that $s$ is a Steiner leaf in $T$ not satisfying (P5). Using
the triangle inequality, we may assume that $s$ has degree at least $3$
(otherwise, the Steiner point may be replaced by an edge directly between its
two neighbors without increasing the cost of the tree). Such an application of
the triangle inequality is consistent with (P1), (P3), and (P4). The argument
in Lemma 6.5 to achieve (P2) can be reapplied if this results in an edge of
length $1$. Then, the fact that $s$ is a Steiner leaf implies that $|P(s)|\geq
2$. If $s$ is only adjacent to terminals, we may apply (P4).

Otherwise, $s$ must be adjacent to one Steiner point $s^{\prime}$ and at least
two nonzero terminals. Suppose that $\left\lVert
s\right\rVert_{\infty}=1/2+\varepsilon$ for some $\varepsilon>0$. There are
two cases to consider.

First, suppose 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})$. Let
$\gamma=\max(\\{|s_{i}|\,:\,\forall t\in P(s),t_{i}=0\\}\cup\\{1/2\\}).$ That
is, $\gamma$ is a maximum magnitude of a coordinate of $s$ not corresponding
to a coordinate of a terminal in $P(s)$ (or $1/2$ if no such coordinates are
greater than $1/2$). Now, for all coordinates $i$ such that
$t_{i}=1/2+\varepsilon$, set $t_{i}=\gamma$. Likewise, for all coordinates $j$
such that $t_{j}=-1/2-\varepsilon$, set $t_{j}=-\gamma$. This increases
$\|s-t\|_{\infty}$ for at most one $t\in N(s)$ by at most
$1/2+\varepsilon-\gamma$, but for all other $t^{\prime}\in N(s)$,
$\|s-t^{\prime}\|_{\infty}$ decreases by $1/2+\varepsilon-\gamma$. Hence, this
can only increase the cost of tree if the tree if $\|s-s^{\prime}\|_{\infty}$
increases. But, we may propagate this reduction in magnitude of coordinates