is $|U|<M$, then from Lemma 4.2, level-$i$ is light, and we will just ignore
this layer by giving up local evidence on it. From now on we assume that
$|U|>M/2$.

We now simulate the algorithm AlgSetCover in Section 4.2 with some
modifications. We use another parameter $R=50n^{1/7}\log n/\varepsilon$. First
we partition the terminals into subsets $T_{\textnormal{high}}$ and
$T_{\textnormal{low}}$ such that (i) for every $u\in T_{\textnormal{high}}$,
the number of Steiner nodes $v$ at distance at most
$(3/5)\cdot(1+\varepsilon)^{i}$ from $u$ is at least $R$; and (ii) for every
$u\in T_{\textnormal{low}}$, the number of Steiner nodes $v$ at distance at
most $(3/5)\cdot(1+\varepsilon)^{i}$ from $v$ is at most $2R$. Such a
partition can be computed with $\underline{\tilde{O}(kn/R)=\tilde{O}(k\cdot
n^{6/7})}$ queries. Note that, for each terminal in $T_{\textnormal{high}}$,
the element in $U$ that corresponds to the level-$i$ connected component that
the terminal belongs to is contained in at least $R$ sets. Since $|U|>M/2$, we
can show via similar arguments that $\varepsilon|U|$ random sets will cover
all these elements (as $M\cdot R>n/\varepsilon$). Therefore, we can ignore all
level-$i$ connected components that contain a terminal in
$T_{\textnormal{high}}$.

Next, we partition the Steiner vertices into subsets $V_{1}$ and $V_{2}$,
using another parameter $P=n^{2/7}$ such that (i) for every vertex $v\in
V_{1}$, the number of terminals in $T_{\textnormal{low}}$ at distance at most
$(3/5)\cdot(1+\varepsilon)^{i}$ from $v$ is at most $100P$; and (ii) for every
vertex $v\in V_{1}$, the number of terminals in $T_{\textnormal{low}}$ at
distance at most $(3/5)\cdot(1+\varepsilon)^{i}$ from $v$ is at least $P$.
Such a partition can be computed with
$\tilde{O}(nk/P)=\underline{\tilde{O}(k\cdot n^{5/7})}$ queries. A similar
argument shows

$|V_{2}|\leq\frac{kR}{P}=\frac{k\cdot 50n^{1/7}\log
n/\varepsilon}{n^{2/7}}=O(n^{6/7}\log n)=o(M)=o(|U|).$

We now define $U_{\textnormal{low}}$ as the set of small level-$i$ connected
components that consist of only terminals in $T_{\textnormal{low}}$. Let
${\mathcal{W}}_{1},{\mathcal{W}}_{2}$ be the collections of sets naturally
defined by Steiner nodes in $V_{1},V_{2}$, respectively. We consider the set
cover instances $({\mathcal{W}}_{1},U_{\textnormal{low}})$ and
$({\mathcal{W}}_{2},U_{\textnormal{low}})$ separately.

We first estimate the value of $|U_{\textnormal{low}}|-{\textnormal{\sf
SC}}({\mathcal{W}}_{2},U_{\textnormal{low}})$. Since
$|{\mathcal{W}}_{2}|=o(|U|)$, in order to obtain a
$(2,\varepsilon|U|)$-estimate of $|U|-{\textnormal{\sf
SC}}({\mathcal{W}}_{2},U_{\textnormal{low}})$, it is sufficient to estimate
$|\bigcup_{W\in{\mathcal{W}}_{2}}W|$ to within an additive factor of
$\varepsilon|U|$. This can be done in a similar way as estimating $|U|$.
Specifically, we pick a random terminal $u\in U_{\textnormal{low}}$ and run
the procedure $\mathsf{BFS}(u,i)$. If the level-$i$ connected component that
contains $u$ is small, then we set $X(u)$ to be the inverse of the size of
this component; otherwise we set $X(u)=0$. So the random variable $X$ is
supported on $[0,1]$ and
$\mathbb{E}[X]=|\bigcup_{W\in{\mathcal{W}}_{2}}W|/|T_{\textnormal{low}}|$.
From Chernoff bound, if we repeat the experiment for $100k\log n/(\varepsilon
M)$ times, then we can obtain an estimate of
$|\bigcup_{W\in{\mathcal{W}}_{2}}W|$ to within an additive factor of
$\varepsilon M$. The query complexity of this step is $\tilde{O}(k\cdot
k/M)=\underline{\tilde{O}(k\cdot n^{1/7})}$.

We next estimate the value of $|U|-{\textnormal{\sf
SC}}({\mathcal{W}}_{1},U_{\textnormal{low}})$. We proceed similarly as
AlgSetCover, by defining an auxiliary graph $H$ on $U$ and estimate its
maximal matching size. Similar to Section 4.2, we only need to design a
subroutine for finding all neighbors of a given element in $H$. This can be
done as follows. Note that an element in $H$ corresponds to a small level-$i$
connected component. We first find all Steiner nodes in $V_{1}$ that is close
to (at distance at most $(3/5)\cdot(1+\varepsilon)^{i}$ from) the component,
and then find all terminals that are close to each of these Steiner nodes.
Since any small components has at most $\tilde{O}(1)$ representatives, the
number of such terminals is at most $R\cdot
P=\tilde{O}((n^{1/7}/\varepsilon)\cdot
n^{2/7})=\tilde{O}(n^{3/7}/\varepsilon)$. For each of these terminals, we run
the procedure $\mathsf{BFS}(\cdot,i)$ on it to figure out if it indeed lies in
a small component or not, and if the answer is yes, the component that
contains the terminal is counted as a neighbor in $H$. The query complexity
for all $\mathsf{BFS}$ procedures is $\underline{\tilde{O}(n^{3/7}\cdot
k/\varepsilon)}$. Lastly, via similar arguments, we can show that the query
complexity of implementing the maximal matching estimation algorithm on $H$ is
$O(RP\cdot RPk)=\underline{\tilde{O}(n^{6/7}\cdot k)}$.

We note that it is immediate to generalize above procedure to handle the
cardinality-$2$ sets, since when estimating $|U|-{\textnormal{\sf
SC}}({\mathcal{W}}_{1},U_{\textnormal{low}})$, we have figured out all
elements in each explored set (and will be able to discard the set whenever it
contains exactly two elements in $U$).

#### Simulation of Step 3

We now describe the simulation of Step 3, the four-vertex subroutine. Recall
that, with the knowledge of terminal-induced metric, we constructed a laminar
family and its partitioning tree ${\mathcal{T}}$ to represents its
hierarchical structure, and we only aim to find a node $x_{S}\in
V({\mathcal{T}})$, such that $x_{S}$ has exactly two children in
${\mathcal{T}}$ and each child of $x_{S}$ also has exactly two children in
${\mathcal{T}}$. Consider such a node $x_{S}$ at level $i$. Note that, if a
child of $x_{S}$ splits (into two child nodes) at a lower-
than-$(i-\log_{1+\varepsilon}(1/\varepsilon_{0}))$ level, then the advantage
obtained within this child node is at most
$\varepsilon_{0}(1+\varepsilon)^{i}$, and it is safe to ignore it. Thus, we
can run $\mathsf{BFS}$ on all terminals $S$ for all levels between
$i-\log_{1+\varepsilon}(1/\varepsilon_{0})$ and $i$ to figure out the
hierarchical structure of $S$ between these levels and calculate
$\mathsf{adv}(S)$. The query time is $\tilde{O}(k)$.

The additional steps needed in simulating Step 3 are similar to that of Step
2, we first find the first $(2ML\log n/\varepsilon)$ terminals in $R_{i-1}$.
If $|R_{i-1}|\leq 2ML\log n/\varepsilon$, than we already figured out all
level-$i$ connected components, and we then simply proceed as before: sample
$O(\log n/\varepsilon^{10})$ small components and calculate the advantage of
them. Otherwise, similar to Step 2, we first estimates $|U|$. Either we
correctly establish that $|U|<M$, in which case level $i$ is light and can be
safely ignored; or we correctly establish that $|U|>M/2$. Now we sample
$O(k\log n/(\varepsilon^{10}M))$ terminals, and for each sampled terminal $u$,
we first run $\mathsf{BFS}(u,i-1)$ to figure out the component $S$ that
contains $u$. If $S$ is a small component, we calculate $\mathsf{adv}(S)$, and
add it to $B_{i}$ with probability $1/|S|$. The process is the same as
sampling $\log n/\varepsilon^{10}$ small components in $U$ and sum up the
advantage of them. So $B_{i}$ is a good approximation of $A_{i}$ in this case
as well. The total query complexity is $\tilde{O}(nk/M)=\tilde{O}(n^{1/7}k)$.

Altogether, the query complexity is $\tilde{O}(n^{12/7}+n^{6/7}\cdot k)$.

##  5 An $\tilde{\Omega}(nk)$ Lower Bound for $(2-\varepsilon)$-Approximate
Steiner Tree

In this section, we provide the proof of Theorem 2 by showing that any
randomized algorithm that computes a $(2-\varepsilon)$-approximate Steiner
Tree performs at least $\Omega(nk)$ queries in the worst case. Throughout this
section, we assume that $k\leq n/100$.

We first construct a distribution on metric Steiner Tree instances $(V,T,w)$
as follows. The vertex set $V$ and the terminal set $T$ are fixed (recall that
$|V|=n$ and $|T|=k$). The terminal set is partitioned into
$t=\left\lfloor\frac{k}{\left\lfloor 1/\varepsilon\right\rfloor}\right\rfloor$
sets $T=\bigcup_{1\leq i\leq t}T_{i}$, such that each set $T_{i}$ contains
either $\left\lfloor 1/\varepsilon\right\rfloor$ or $\left\lceil
1/\varepsilon\right\rceil$ terminals. This partitioning is fixed as well. The
only randomized part is the weight-metric $w$. Let $X$ be a set chosen
uniformly at random from all size-$t$ subsets of $V\setminus T$. We call
vertices in $X$ _crucial_ vertices. We then choose a random one-to-one mapping
from $X$ to $[t]$, and for each $i\in[t]$, we call the vertex in $X$ that is
mapped to $i$ the _$i$ -crucial_ vertex. The random metric $w$ is defined
according to the random set $X$ as follows. For every $i\in[t]$, the weight
between the $i$-crucial vertex in $X$ and every terminal in $T_{i}$ is $1$,
and the weight between any other pair of vertices in $V$ is $2$. It is easy to
verify that $w$ always satisfies the triangle inequality.

We call edges that are incident to crucial vertices _crucial edges_. Clearly,
crucial edges form $t$ disjoint stars. It is easy to verify that, although $w$
is random, any two realizations of $w$ are isomorphic, and so the metric
Steiner Tree cost is always the same. In particular, the optimal Steiner tree
contains all crucial edges and $(t-1)$ other edges connecting the star graphs
formed by crucial edges, and so ${\mathsf{ST}}(V,T,w)=k\cdot 1+(t-1)\cdot
2=k+2t-2$. On the other hand, any Steiner tree that contains $k^{\prime}$
crucial edges has to contain at least $(t-1)+(k-k^{\prime})$ other edges in
order to span all terminals, and its total cost is at least $k^{\prime}\cdot
1+\big{(}(t-1)+(k-k^{\prime})\big{)}\cdot 2=2k-k^{\prime}+2t-2$. Therefore, in
order to compute a Steiner tree of cost
$(2-4\varepsilon)\cdot{\mathsf{ST}}(V,T,w)$, which is a Steiner tree of cost
$(2-4\varepsilon)(k+2t-2)$, an algorithm has to finds at least
$(2k+2t-2)-(2-4\varepsilon)(k+2t-2)=4\varepsilon k-2t\geq\varepsilon k$ edges.

Observe that, from the construction of $w$, if a terminal $u\in T_{i}$ has a
weight-$1$ edge connecting to a Steiner vertex, then that Steiner vertex is
the $i$-crucial vertex in $X$ and every other terminal in $T_{i}$ is also
connected to it by weight-$1$ edges. For ease of analysis, we consider the
following distribution of instances $(V^{\prime},T^{\prime},w^{\prime})$. The
terminal set $T^{\prime}$ contains, for each $i\in[t]$, a terminal $u_{i}\in
T_{i}$, and it is fixed. The vertex set $V^{\prime}=T^{\prime}\cup(V\setminus
T)$ and is also fixed. The metric $w^{\prime}$ is random and defined as
follows. Let $X$ be a set chosen uniformly at random from all size-$t$ subsets
of $V\setminus T$, and we then choose a random one-to-one mapping from $X$ to
$[t]$. We define $i$-crucial vertices similarly as before. For every
$i\in[t]$, the weight between the $i$-crucial vertex in $X$ and terminal
$u_{i}$ is $1$, and the weight between any other pair of vertices in
$V^{\prime}$ is $2$. It is easy to observe that a size-$t$ set $X$ and a
mapping from $X$ to $[t]$ defines a metric $(V,T,w)$ and a metric
$(V^{\prime},T^{\prime},w^{\prime})$, and a query in either metric can be
simulated by a query in the other. Additionally, in order to find at least
$\varepsilon k$ crucial edges in $w$, it is necessary to find $(\varepsilon
k)/\left\lceil 1/\varepsilon\right\rceil\geq\varepsilon^{2}k/2$ crucial edges
in $w^{\prime}$.

We say that an crucial edge $(u,x)$ is _discovered_ by an algorithm at some
step iff the set of queries performed by the algorithm before this step
uniquely identify the edge $(u,x)$ to be a crucial edge. We say that a
terminal is discovered iff its (unique) incident crucial edge is discovered,
otherwise we say it is _undiscovered_. From Yao’s minimax principle [Yao77]
and the above discussion, in order to prove Theorem 2, it suffices to prove
the following lemma.

######  Lemma 5.1.

Any deterministic algorithm that discovers in expectation at least
$\varepsilon^{2}k/2$ crucial edges in the distribution on $w^{\prime}$ defined
above performs at least $\Omega(\varepsilon^{2}nk)$ queries in expectation.

In the remainder of this section, we provide the proof of Lemma 5.1. From now
on, we only consider algorithms that perform queries to the metric
$w^{\prime}$ instead of the metric $w$. We follow the framework used in the
proof of Lemma 5.3 in [ACK19], which shows that any randomized algorithm that
outputs an approximate maximal matching performs at least $\Omega(n^{2})$
queries in the worst case.

Consider a deterministic algorithm and the sequence of queries it performs. We
partition the sequence into _phases_ as follows. The first phase starts at the
first query, a phase ends as soon as a crucial edge is discovered, and the
next phase starts right after the previous phase ends. For each integer $j$,
let $Z_{j}$ be the random variable denoting the number of queries performed in
the $j$-th phase. In order to prove Lemma 5.1, it suffices to show that
$\mathbb{E}[\sum_{1\leq j\leq\varepsilon^{2}k}Z_{i}]=\sum_{1\leq
j\leq\varepsilon^{2}k}\mathbb{E}[Z_{i}]=\Omega(\varepsilon^{2}nk)$.

From the construction of $w$, the weight between any pair of Steiner vertices
and the weight between any pair of terminals is always $2$, so the only
potentially useful queries are the ones between a terminal and a Steiner
vertex. We define the _uncertainty_ of a terminal $u\in T^{\prime}$ at some
step to be $(n-k)$ minus the number of queries involving $u$ performed by the
algorithm so far. We say that a phase is _bad_ , iff at the start of the
phase, there exists an undiscovered terminal whose uncertainty is below
$3n/4$; and we say that a phase is _good_ , iff at the start of the phase, the
uncertainty of every undiscovered terminal is at least $3n/4$. The proof of
Lemma 5.1 is concluded by the following claims.

######  Claim 5.1.

The expected number of queries in a good phase is at least $n/200$.

###### Proof.

We use the following lemma, which is similar to Lemma 5.4 in [ACK19].

######  Lemma 5.2.

Let $H=(A,B,E)$ be a bipartite graph with $|A|=a$ and $|B|=b$ (where $b>10a$),
such that every vertex in $A$ has degree at least $2b/3$, then for every edge
$e\in E$, the probability that $e$ is contained in a uniformly at random
chosen $A$-perfect matching in $G$ is at most $2/b$ (here an $A$-perfect
matching is a matching that matches all vertices of $A$).

###### Proof.

It is easy to verify from Hall’s Theorem that $H$ always contains a perfect
matching. Consider an edge $(u,v)\in E$ where $u\in A$ and $v\in B$. Let $M$
be an $A$-perfect matching that contains edge $(u,v)$. We construct $b/2$
other $A$-perfect matchings as follows. Let $B^{\prime}$ be the set of
vertices in $B\setminus\left\\{v\right\\}$ that is adjacent to $u$ in $H$ but
is not an endpoint of any edge in $M$. Since $\deg_{H}(u)\geq 2b/3$ and
$b>10a$, we get that $|B^{\prime}|\geq 2b/3-1-b/10\geq b/2$. For each vertex
$v^{\prime}\in B^{\prime}$, we define $M_{v^{\prime}}$ to be the matching
obtained from $M$ by replacing edge $(u,v)$ with edge $(u,v^{\prime})$.
Clearly, $M_{v^{\prime}}$ is an $A$-perfect matching for every $v\in
B^{\prime}$, so we obtained a collection of at least $b/2$ other $A$-perfect
matchings that do not contain edge $(u,v)$, that we denote by
${\mathcal{F}}(M)$. On the other hand, for every pair $M,M^{\prime}$ of
distinct $A$-perfect matchings in $H$ that contains the edge $(u,v)$, the
collections ${\mathcal{F}}(M),{\mathcal{F}}(M^{\prime})$ are disjoint. This is
because for every matching $\hat{M}\in{\mathcal{F}}(M)$ and for every matching
$\hat{M}^{\prime}\in{\mathcal{F}}(M^{\prime})$, $\hat{M}$ and
$\hat{M}^{\prime}$ must differ on an edge not incident to $u$, as $M$ and
$M^{\prime}$ do. Therefore, the number of perfect $A$-matchings in $H$ is at
least $(b/2)$ times the number of perfect $A$-matchings in $H$ that contains
the edge $(u,v)$, and the lemma now follows. ∎

By definition, at the start of a good phase, the uncertainty of every
undiscovered terminal is at least $3n/4$. Therefore, for the next $n/24$
queries, it is easy to verify that the graph induced by all unqueried edges
satisfy the conditions of Lemma 5.2, and so the probability that any single
query finds an edge of weight $1$ is at most $2/(n-k)\leq 3/n$. Thus, with
probability at least $(n/24)\cdot(3/n)=1/8$, none of the first $n/24$ queries
of a good phase finds a weight-$1$ edge. This implies that the expected number
of queries in a good phase is at least $(1/8)\cdot(n/24)\geq n/200$. ∎

######  Claim 5.2.

If the algorithm performs less than $\varepsilon^{2}nk/20$ queries, then the
number of bad phases is at most $\varepsilon^{2}k/4$.

###### Proof.

Since any useful query is between a terminal and a Steiner vertex, a useful
query reduces the uncertainty of exactly one terminal by $1$. Therefore, in
order to have $\varepsilon^{2}k/40$ bad phases, the reduction in the total
uncertainty is at least
$(\varepsilon^{2}k/4)\cdot(n-k-3n/4)\geq\varepsilon^{2}nk/200$, which implies
that the algorithm performs at least $\varepsilon^{2}nk/200$ queries. ∎

From the above two claims, in order to find $\varepsilon^{2}k/2$ crucial
edges, either the algorithm performs at least $\varepsilon^{2}nk/20$ queries,
or the number of bad phases encountered by the query sequence is at most
$\varepsilon^{2}k/4$. Thus, in the first $\varepsilon^{2}k/2$ phases, there
are at least $\varepsilon^{2}k/4$ good phases, implying that the expected
number queries made by the algorithm is at least
$(\varepsilon^{2}k/4)\cdot(n/200)=\Omega(\varepsilon^{2}nk)$. This completes
the proof of Lemma 5.1, and therefore also completes the proof of Theorem 2.

##  6 Upper and Lower Bounds for $\alpha$-Approximate Steiner Tree
($\alpha\geq 2$)

In this section we provide the proof of Theorem 5.

###  6.1 Upper Bound

We start by presenting an $\tilde{O}(k^{2}/\alpha)$ query algorithm for any
$\alpha\geq 2$. The query algorithm for any $\alpha\geq 2$ is very similar to
the algorithm in the proof of Theorem 1 in [CKT22], which shows a one-pass
$\tilde{O}(n/\beta)$ streaming algorithm for estimating the metric MST cost to
within factor $\beta$ (for any $\beta>1$). Note that we may assume without
lose of generality that $\alpha=\Omega(\log^{2}n)$, as otherwise we can simply
query all terminal-terminal weight (which is $k^{2}=\tilde{O}(k^{2}/\alpha)$
queries) and then compute the minimum spanning tree on $T$, which is a
$2$-approximate Steiner Tree (and therefore an $\alpha$-approximate Steiner
Tree as $\alpha\geq 2$).

##### Algorithm.

Let $\beta=\alpha/(100\log n)$. We first choose a uniformly at random
size-$\left\lceil k/\beta\right\rceil$ subset of $T$, and denote it by
$T^{\prime}$. We then query all weights between pairs of terminals in
$T^{\prime}$, and use the acquired information to compute the minimum spanning
tree ${\mathcal{T}}^{\prime}$ over $T^{\prime}$. Lastly, for every terminal
$u\notin T$, we query all weights between $u$ and terminals in $T^{\prime}$,
and let $f(u)=\arg_{u^{\prime}\in
T^{\prime}}\min\left\\{w(u,u^{\prime})\right\\}$. Finally, we output the tree
${\mathcal{T}}$ defined as
${\mathcal{T}}={\mathcal{T}}^{\prime}\cup\left\\{(u,f(u))\mid u\in T\setminus
T^{\prime}\right\\}$.

On the one hand, observe that the algorithm only queries weights with one
endpoint in $T^{\prime}$ and the other endpoint in $T$, so the number of
queries performed by the algorithm is at most
$k\cdot(k/\beta)=\tilde{O}(k^{2}/\alpha)$. On the other hand, it is easy to
verify that the algorithm always outputs a spanning tree on $T$. The proof
that the spanning tree ${\mathcal{T}}$ output by the algorithm above is with
high probability an $\alpha$-approximate Steiner Tree is similar to the
analysis on pages 15-16 in [CKT22], and is deferred to Appendix E.

###  6.2 Lower Bound

We now prove an $\Omega(k^{2}/\alpha)$ lower bound for computing an
$\alpha$-approximate Steiner Tree for any $\alpha\geq 2$. In fact, we will
show that, if all vertices in the metric space are terminals (so there are $k$
terminals and no Steiner vertices), then for every $\alpha\geq 2$, computing a
spanning tree of cost at most $\alpha$ times the minimum spanning tree cost
requires at least $\Omega(k^{2}/\alpha)$ queries. Since the metric Steiner
Tree cost is at most twice the minimum terminal spanning tree cost, this lower
bound implies the lower bound in Theorem 5 (as we can construct a metric
Steiner Tree instance, where all Steiner vertices are sufficiently far from
all terminals and so any $\alpha$-approximate Steiner tree may only terminal-
terminal edges, and is therefore a terminal spanning tree).

It is easy to observe that it suffices to consider the case where $\alpha\geq
2$ is an integer and $k$ is divisible by $100\alpha$. We generate a metric
space $w$ from the following distribution. The vertex set $V=T$ is fixed. Let
${\mathcal{P}}$ be a partitioning of $T$, that is chosen uniformly at random
from all partitioning of $T$ that partition $T$ into $t=k/100\alpha$ sets
$T_{1},\ldots,T_{t}$ of size $100\alpha$ each. For every pair $u,u^{\prime}$
of terminals in the same part of ${\mathcal{P}}$, $w(u,u)=1$, and for all
other pairs $u,u^{\prime}$, $w(u,u)=2\alpha$.

We call the weight-$1$ edges as _crucial_ edges. It is easy to verify that,
although metric $w$ is random, any two realizations of $w$ are isomorphic, and
so the minimum spanning cost is always the same. In particular, the minimum
spanning tree contains $(k-t)$ crucial edges and $(t-1)$ other edges
connecting the trees incide each partition, and so
${\mathsf{MST}}(w)=(k-t)\cdot 1+(t-1)\cdot 2\alpha=1.02k-t-2\alpha$. On the
other hand, for any spanning tree that contains $k^{\prime}$ crucial edges and
$(k-k^{\prime}-1)$ other edges, its total cost is at least $k^{\prime}\cdot
1+(k-k^{\prime}-1)\cdot 2\alpha=2\alpha k-(2\alpha-1)k^{\prime}-2\alpha$.
Therefore, in order for a spanning tree ${\mathcal{T}}$ to approximate the
minimum spanning tree to within factor $\alpha$, the tree ${\mathcal{T}}$ has
to contain at least

$\frac{2\alpha
k-2\alpha-\alpha\cdot(1.02k-t-2\alpha)}{2\alpha-1}=\frac{0.98\alpha
k-2\alpha+\alpha t+2\alpha^{2}}{2\alpha}\geq 0.01k$

crucial edges, and so there must be at least $0.01k$ vertices in $T$, such
that ${\mathcal{T}}$ contains a crucial edge incident to it.

We say that an edge is _discovered_ by an algorithm at some step iff the set
of queries performed by the algorithm before this step uniquely identify the
edge to be a weight-$1$ edge or a weight-$2\alpha$ edge. We say that a vertex
$u$ is _settled_ iff the algorithm has discovered a crucial edge incident to
$u$; otherwise we say that it is _unsettled_. Similarly, we say that a part
$T_{i}$ in the partitioning ${\mathcal{P}}$ is settled iff all its vertices
are settled. From Yao’s minimax principle [Yao77] and the above discussion, in
order to prove the lower bound of Theorem 5, it suffices to prove the
following lemma.

######  Lemma 6.1.

Any deterministic algorithm that settles at least $0.01k$ vertices in the
distribution on $w$ defined above performs at least $\Omega(k^{2}/\alpha)$
queries in expectation.

In the remainder of this section, we provide a proof of Lemma 6.1. We use a
similar approach as in Section 5. Consider a deterministic algorithm and the
sequence of queries it performs. Assume without loss of generality that the
algorithm terminates whenever it settles $0.01k$ vertices. We partition the
sequence of queries it makes as follows. The first phase starts at the first
query, a phase ends as soon as a previously unsettled vertex is settled, and
the next phase starts right after the previous phase ends. For each $j\geq 1$,
we let $Z_{j}$ be the random variable denoting the number of queries performed
in the $j$-th phase. In order to prove Lemma 6.1, it suffices to show that
$\sum_{1\leq j\leq 0.01k}\mathbb{E}[Z_{i}]=\Omega(k^{2}/\alpha)$.

We classify all phases into good ones and bad ones as follows. We say that an
unsettled vertex $u$ is _well-discovered_ , iff the number of parts $T_{i}$ in
${\mathcal{P}}$ such that some edge in $E(u,T_{i})$ has been discovered is at
least $t/10$. We say that a phase is _type-1 bad_ , iff at the start of this
phase there exists an unsettled part $T_{i}\in{\mathcal{P}}$, and such that
all discovered edges in $E(T_{i},T\setminus T_{i})$ touch at least $k/10$
vertices outside $T_{i}$. We say that a phase is _type-2 bad_ iff at the start
of this phase there exists a well-discovered vertex. If a phase is neither
type-1 bad nor type-2 bad, then we say it is _good_. For ease of analysis,
whenever the algorithm starts a type-1 bad phase due to some part $T_{i}$, we
immediately reveal to the algorithm the weight of all edges with at least one
endpoints in $T_{i}$, so the part $T_{i}$ is settled right away; and whenever
the algorithm starts a type-2 bad phase due to some well-discovered unsettled
vertex $u$, we immediately reveal a crucial edge incident on $u$, so $u$ and
the other endpoint of the revealed edge are settled right away. We prove the
following claims.

######  Claim 6.1.

The expected number of queries in a good phase is at least $k/1600\alpha$.

###### Proof.

Recall that the metric $w$ is defined based on a partitioning ${\mathcal{P}}$
of $T$ into $t=k/100\alpha$ subsets of size $100\alpha$ each (that we call a
_valid_ partitioning). We say that a valid partitioning ${\mathcal{P}}$
_joins_ a pair $u,u^{\prime}$ of vertices in $T$, iff $u,u^{\prime}$ lie in
the same part of ${\mathcal{P}}$, otherwise we say that ${\mathcal{P}}$
_separates_ the pair $u,u^{\prime}$. We say that a valid partitioning
${\mathcal{P}}$ of $T$ is _consistent_ with the current queries, iff (i) every
discovered crucial edge has both its endpoints lying in the same part of
${\mathcal{P}}$ and every discovered edge that is not crucial has its
endpoints in different partitions; (ii) every unsettled vertex $u$ is not
well-discovered; and (iii) for every unsettled part $T_{i}$ in
${\mathcal{P}}$, all discovered edges in $E(T_{i},T\setminus T_{i})$ touch at
least $k/10$ vertices outside $T_{i}$. In other words, a partitioning
${\mathcal{P}}$ is consistent iff it provides consistent answers for all
queries made by the algorithm, and the algorithm is not a bad phase given the
current queries. Intuitively, from the algorithm’s viewpoint, the up-to-date
distribution (according to the answers to the queries performed so far) of the
underlying partitioning should be the uniform distribution on all
partitionings that are consistent with the current queries. We prove the
following observation.

######  Observation 6.1.

At any time during the first $k/(10\alpha)$ queries of a good phase, for every
pair $u,u^{\prime}$ of vertices in $T$ such that $u,u^{\prime}$ are not both
settled and the edge $(u,u^{\prime})$ has not been queried yet, the number of
consistent partitionings that separate the pair $u,u^{\prime}$ is at least
$k/800\alpha$ times the number of consistent partitionings that joins the pair
$u,u^{\prime}$.

###### Proof.

Consider a pair $u,u^{\prime}$ of vertices and a consistent partitioning
${\mathcal{P}}$ that joins the pair $u,u^{\prime}$. Assume without loss of
generality that $u$ is unsettled. We construct a collection of other
partitionings as follows. Let $T_{i}$ be the part in ${\mathcal{P}}$ that
contains $u$ and $u^{\prime}$. Let $T^{\prime}(u)$ be the set of all unsettled
terminals $\hat{u}$ such that (i) no edge in
$E(\left\\{\hat{u}\right\\},T_{i})$ has been discovered; and (ii) no edge in
$E(\left\\{u\right\\},T_{i^{\prime}})$ has been discovered, where
$T_{i^{\prime}}$ is the part in ${\mathcal{P}}$ that contains $\hat{u}$. We
prove the following observation.

######  Observation 6.2.

At any time during the first $k/(10\alpha)$ queries of a good phase, for every
unsettled vertex $u$, $|T^{\prime}(u)|\geq k/2$.

###### Proof.

Before this good phase, $u$ is also unsettled, so the number of vertices
$\hat{u}$ such that $(u,\hat{u})$ has been discovered is at most
$(t/10)\cdot(100\alpha)\leq k/10$. Let $T_{i}$ be the part that $u$ lies in,
since $T_{i}$ is not settled before this phase, it did not create a bad phase
before, and so the number of vertices in $T\setminus T_{i}$ that are touched
by discovered edges in $E(T_{i},T\setminus T_{i})$ is at most $k/10$. On the
other hand, note that the algorithm settles at most $0.49$ vertices before
this phase, and has performed performed at most $k/(10\alpha)$ queries in this
phase. By definition, $T^{\prime}(u)$ contains all vertices $\hat{u}$ that
does not satisfy any of the above conditions, so $|T^{\prime}(u)|\geq
k-k/10-k/10-0.01k-k/(10\alpha)\geq k/2$. ∎

For each $\hat{u}\in T^{\prime}(u)$, consider the partitioning
${\mathcal{P}}(\hat{u})$ obtained by exchanging the positions of vertices $u$
and $\hat{u}$ (that is, if originally $u\in T_{i}$ and $\hat{u}\in
T_{i^{\prime}}$, then we move $u$ to $T_{i^{\prime}}$ and move $\hat{u}$ to
$T_{i}$). Clearly, vertices $u,u^{\prime}$ are separated in
${\mathcal{P}}(\hat{u})$. We prove the following observation.

######  Observation 6.3.

For every $\hat{u}\in T^{\prime}(u)$, ${\mathcal{P}}(\hat{u})$ is a consistent
partitioning.

###### Proof.

Consider a vertex $\hat{u}\in T^{\prime}(u)$. Let $T_{i}$ be the set that
contains $u$ and let $T_{i^{\prime}}$ be the set that contains $\hat{u}$. By
definition of $T^{\prime}(u)$, no edge in $E(\left\\{\hat{u}\right\\},T_{i})$
has been discovered, and no edge in $E(\left\\{u\right\\},T_{i^{\prime}})$ has
been discovered. On the other hand, since $u$ and $\hat{u}$ are not settled,
no edge in $E(\left\\{\hat{u}\right\\},T_{i^{\prime}})$ has been discovered,
and no edge in $E(\left\\{u\right\\},T_{i})$ has been discovered. Therefore,
${\mathcal{P}}(\hat{u})$ provides consistent answers with all queries made by
the algorithm so far. On the other hand, it also implies that for every part
$T_{j}$ in ${\mathcal{P}}(\hat{u})$, all discovered edges in
$E(T_{j},T\setminus T_{j})$ touch the same set of vertices as the
corresponding part in ${\mathcal{P}}$. Lastly, it is also easy to verify that
every unsettled vertex is still not discovered in ${\mathcal{P}}(\hat{u})$.
Altogether, ${\mathcal{P}}(\hat{u})$ is a consistent partitioning with all
current queries. ∎

For every $\hat{u}\in T^{\prime}(u)$, we say that ${\mathcal{P}}(\hat{u})$ is
a _host_ of ${\mathcal{P}}$, so ${\mathcal{P}}$ has at least $k/2$ hosts. On
the other hand, for every partitioning ${\mathcal{P}}^{\prime}$ that separates
$u,u^{\prime}$, there are at most $200\alpha$ partitioning ${\mathcal{P}}$,
such that ${\mathcal{P}}$ joins $u,u^{\prime}$ and ${\mathcal{P}}^{\prime}$ is
a host of ${\mathcal{P}}$ (since in ${\mathcal{P}}^{\prime}$, $u,u^{\prime}$
belong to different parts, say $u\in T_{i}$ and $u^{\prime}\in T_{i^{\prime}}$
so it must be the case that either $u$ and some vertex in $T_{i^{\prime}}$ are
exchanged or $u^{\prime}$ and some vertex in $T_{i}$ are exchanged, a total of
at most $200\alpha$ possibilities). Therefore, the number of consistent
partitionings that separate the pair $u,u^{\prime}$ is at least
$(k/2)/(200\alpha)=k/400\alpha$ times the number of consistent partitionings
that joins the pair $u,u^{\prime}$. ∎

From 6.1, among the first $k/800\alpha$ queries in a good phase, the
probability that any single query finds a crucial edge is at most
$400\alpha/n$, and so with probability $1/2$, none of them finds a crucial
edge. This implies that the expected number of queries in a good phase is at
least $(k/800\alpha)\cdot(1/2)=k/1600\alpha$. ∎

######  Claim 6.2.

If the algorithm performs less than $k^{2}/(10^{7}\alpha)$ queries, then the
number of type-1 bad phases is at most $k/(10^{5}\alpha)$, and the number
type-2 bad phases is at most $k/10^{3}$.

###### Proof.

Assume for contradiction that the number of type-1 bad phases is more than
$k/(10^{5}\alpha)$. Then there are at least $k/(10^{5}\alpha)$ indices $i$,
such that the number of edges in $|E(T_{i},T\setminus T_{i})|$ discovered by
the algorithm is at least $k/10$. On the other hand since the algorithm never
settles more than $0.01k$ vertices, it never discovers more than $0.01k$
crucial edges. Therefore, the number of queries performed by the algorithm is
at least

$\frac{1}{2}\cdot\frac{k}{10^{5}\alpha}\cdot\bigg{(}\frac{k}{10}-\frac{k}{10^{5}\alpha}\cdot
100\alpha-0.01k\bigg{)}\geq\frac{k^{2}}{10^{7}\alpha},$

a contradiction. Assume for contradiction that the number of type-2 bad phases
is more than $k/10^{3}$, then there are more than $k/10^{3}$ well-discovered
vertices. Therefore, the number of queries performed by the algorithm over all
phases is at least $(k/10^{3})\cdot(t/10-k/(10^{5}\alpha))\cdot(1/2)\geq
k^{2}/(10^{7}\alpha)$, a contradiction. ∎

From the above two claims, we get that, in order to settle $0.01k$ vertices,
either the algorithm performs at least $k^{2}/(10^{7}\alpha)$ queries, or the
number of type-1 bad phases of its query sequence is at most
$k/(10^{5}\alpha)$ (which settles at most $0.001k$ vertices in total) and the
number of type-2 bad phases of its query sequence is at most $k/10^{3}$ (which
settles at most $0.002k$ vertices in total), and so among the first $0.01k$
phases, there are at least $0.007k$ good phases, implying that the expected
number queries made by the algorithm is at least
$0.007k\cdot(k/1600\alpha)=\Omega(k^{2}/\alpha)$. This completes the proof of
Lemma 6.1, and therefore also completes the proof of the lower bound in
Theorem 5.

##  7 An $\tilde{\Omega}(n+k^{6/5})$ Query Lower Bound for
$(2-\varepsilon)$-Estimation

In this section we provide the proof of Theorem 4, by showing that, for any
$0<\varepsilon<1$, any randomized algorithm that with probability $2/3$
estimates the Steiner Tree cost to within a factor of $2-\varepsilon$ performs
$\Omega(n+k^{6/5})$ in the worst case. We will prove a lower bound of
$\Omega(n)$ in Section 7.1 and a lower bound of $\Omega(k^{6/5})$ in
LABEL:sec:_k^{6/5}_lower. Combined together, they complete the proof of
Theorem 4. Throughout the section, we assume that $1/(2\varepsilon)<k<n/2$.

###  7.1 An $\Omega(n)$ Lower Bound

We construct a distribution ${\mathcal{D}}$ of metric Steiner Tree instance
$(V,T,w)$ as follows. The set $T$ contains $k$ terminals and the vertices in
$V\setminus T$ are denoted by $v_{1},\ldots,v_{n-k}$. We define $w_{0}$ as the
metric on $V$ where $w_{0}(v,v^{\prime})=2$ for all pairs $v,v^{\prime}\in V$.
For each $1\leq j\leq n-k$, we define a metric $w_{j}$ as follows:

  * •

For each terminal $u\in T$, $w_{j}(u,v_{j})=1$.

  * •

For every other pair $v,v^{\prime}\in V$, $w_{j}(v,v^{\prime})=2$.

In other words, the weight-$1$ edges in $w_{j}$ form a star graph where
$v_{j}$ is its center and all terminals are its leaves. It is easy to verify
that $w_{j}$ is indeed a metric. We then define the instance
$I_{j}=(V,T,w_{j})$, and the distribution ${\mathcal{D}}$ is defined as
follows: $\Pr[I_{0}]=1/2$, and for each $1\leq j\leq n-k$,
$\Pr[I_{j}]=1/(2(n-k))$.

Clearly, ${\mathsf{ST}}(I_{0})=2(k-1)$, and for each $j$,
${\mathsf{ST}}(I_{j})=k$ as the star graph formed by all weight-$1$ edges is a
Steiner Tree of cost $k$. Since $k>1/(2\varepsilon)$,
${\mathsf{ST}}(I_{0})/{\mathsf{ST}}(I_{j})>2-\varepsilon$ for all $j$, and so
estimating the metric Steiner Tree cost of a random instance sampled from
${\mathcal{D}}$ to within factor $(2-\varepsilon)$ is equivalent to
determining whether or not the random instance is $I_{0}$.

In order to correctly determining if a random instance sampled from
${\mathcal{D}}$ is $I_{0}$ with probability at least $2/3$, it is necessary
that the algorithm discovers a weight-$1$ edge on at least $(1/3)$-fraction of
the instances $I_{1},\ldots,I_{n-k}$. From Yao’s minimax principle [Yao77],
the following claim implies a $\Omega(n-k)=\Omega(n)$ lower bound on the query
complexity of any randomized algorithm, as $k\leq n/2$.

######  Claim 7.1.

Any deterministic algorithm that discovers a weight-$1$ edge on at least
$1/3$-fraction of the instances $I_{1},\ldots,I_{n-k}$ performs at least
$\Omega(n)$ queries in expectation.

###### Proof.

Observe that, in each of the instances $I_{1},\ldots,I_{n-k}$, all weight-$1$
edges are incident to one Steiner vertex, that we call the _secret vertex_ ,
and the secret vertex is $v_{1},\ldots,v_{n-k}$ with probability $1/(n-k)$
each. Since a single query can only check one Steiner vertex (by querying any
edge connecting it to a terminal), in order to find the secret vertex on at
least $1/3$-fraction of the instances $I_{1},\ldots,I_{n-k}$, any algorithm
needs to perform at least $(n-k)/3=\Omega(n-k)$ queries in expectation. ∎

###  7.2 An $\Omega(k^{6/5})$ Lower Bound

We will construct a pair
$\mathcal{D}_{\textnormal{{Y}}},\mathcal{D}_{\textnormal{{N}}}$ of
distributions on metric Steiner Tree instances, such that
$\mathcal{D}_{\textnormal{{Y}}}$ is only supported on instances $(V,T,w)$ with
${\mathsf{ST}}(V,T,w)$ close to $Z$, while $\mathcal{D}_{\textnormal{{N}}}$ is
only supported on instances instances $(V,T,w)$ with ${\mathsf{ST}}(V,T,w)$
close to $2Z$, where $Z$ is some function of $k$ that will be defined later.
We let
${\mathcal{D}}=(\mathcal{D}_{\textnormal{{Y}}}+\mathcal{D}_{\textnormal{{N}}})/2$
be the average distribution of $\mathcal{D}_{\textnormal{{Y}}}$ and
$\mathcal{D}_{\textnormal{{N}}}$. We show that, in order to report correctly
with probability at least $2/3$ whether an random instance sampled from
${\mathcal{D}}$ comes from $\mathcal{D}_{\textnormal{{Y}}}$ or
$\mathcal{D}_{\textnormal{{N}}}$, any randomized algorithm has to perform at
least $\tilde{\Omega}(k^{6/5})$ queries, thereby proving Theorem 4.

We now proceed to define the distributions $\mathcal{D}_{\textnormal{{Y}}}$
and $\mathcal{D}_{\textnormal{{N}}}$. We first define an _auxiliary instance_
$(V,T,w)$ as follows. For convenience, we let set $T$ contain
$k+k^{2/5}/\varepsilon$ terminals instead of $k$ terminals. As we will see,
this does not influence our lower bound, as
$(k+k^{2/5}/\varepsilon)^{6/5}=\Theta(k^{6/5})$.

  * •

The set $T$ is partitioned into subsets $T=\big{(}\bigcup_{1\leq j\leq
d}S_{i}\big{)}\cup\big{(}\bigcup_{1\leq i\leq d^{\prime}}T_{i}\big{)}$, where
$d=k^{2/5}$, $d^{\prime}=k^{3/5}$; for each $1\leq j\leq d$,
$|S_{j}|=1/\varepsilon$, and for each $1\leq i\leq d^{\prime}$,
$|T_{i}|=k^{2/5}$.

    * –

We call sets $S_{1},\ldots,S_{d},T_{1},\ldots,T_{d^{\prime}}$ _groups_.

    * –

We denote $S=\bigcup_{1\leq j\leq d}S_{j}$, we call terminals in $S$ _special_
terminals, and we call terminals in $T\setminus S$ _regular_ terminals. For
each $1\leq j\leq d$, we denote
$S_{j}=\left\\{s_{j,1},\ldots,s_{j,1/\varepsilon}\right\\}$. Note that
$|S|=k^{2/5}/\varepsilon$.

  * •

The set $V\setminus T$ contains $n-(k+k^{2/5}/\varepsilon)$ Steiner vertices
and is further partitioned into $d^{\prime}+1$ subsets $V\setminus
T=\bigcup_{0\leq i\leq d^{\prime}}V_{i}$, where for each $1\leq i\leq
d^{\prime}$, $|V_{i}|=k^{2/5}/\varepsilon$.

  * •

The metric $w$ is defined as follows:

    * –

For every pair $u,u^{\prime}$ of regular terminals that belong to the same
group, $w(u,u^{\prime})=0$.

    * –

For each $1\leq i\leq d^{\prime}$, we fix an arbitrary perfect matching
$M_{i}$ between terminals in $S$ and vertices in $V_{i}$. For every matched
pair $u,v^{\prime}$, $w(u,v)=1$.

    * –

The weight between every other pair of vertices in $V$ is $2$.

Figure 8: An illustration of the metric $w$. All terminals are shown in dark
blue and all Steiner vertices are shown in black. Matchings
$M_{1},\ldots,M_{k^{3/5}}$ are shown in dashed lines and the matched pairs
have weight $1$. Pairs of teminals in the same $T_{i}$ (green box) have weight
$0$. All other pairs have weight $2$.

See Figure 8 for an illustration. It is easy to verify that $w$ is indeed a
metric.

We now use the auxiliary instance defined above to construct distributions
$\mathcal{D}_{\textnormal{{Y}}}$ and $\mathcal{D}_{\textnormal{{N}}}$. Every
instance with non-zero probability in either $\mathcal{D}_{\textnormal{{Y}}}$
or $\mathcal{D}_{\textnormal{{N}}}$ has the same vertex set $\hat{V}$ and the
same terminal set $\hat{T}$, where $|\hat{V}|=|V|$ and $|\hat{T}|=|T|$. The
set $\hat{V}\setminus\hat{T}$ of Steiner vertices is further partitioned into
subsets $\hat{V}\setminus\hat{T}=\bigcup_{0\leq i\leq d^{\prime}}\hat{V}_{i}$,
where $V_{0}=\hat{V}_{0}$, and for each $1\leq i\leq d^{\prime}$,
$|\hat{V}_{i}|=|V_{i}|$. We say that a one-to-one mapping $f:\hat{V}\to V$ is
_valid_ , iff $f$ maps terminals in $\hat{T}$ to terminals in $T$, $f$ maps
every vertex in $\hat{V}_{0}$ to itself in $V_{0}$, and for each $1\leq i\leq
d^{\prime}$, $f$ maps vertices in $\hat{V}_{i}$ to vertices in $V_{i}$. Let
${\mathcal{F}}$ be the set of all valid mappings.

We first define the distribution $\mathcal{D}_{\textnormal{{N}}}$. For each
mapping $f\in{\mathcal{F}}$, we define an instance
$I_{f}=(\hat{V},\hat{T},\hat{w}_{f})$, where the metric $\hat{w}_{f}$ is
defined as follows: for every pair $v,v^{\prime}\in\hat{V}$,
$\hat{w}_{f}(v,v^{\prime})=w(f(v),f(v^{\prime}))$. The distribution
$\mathcal{D}_{\textnormal{{N}}}$ is simply defined to be the uniform
distribution over all instances in ${\mathcal{I}}_{\sf N}=\left\\{I_{f}\mid
f\in{\mathcal{F}}\right\\}$.

We now define the distribution $\mathcal{D}_{\textnormal{{Y}}}$. Consider a
mapping $g:[d]\to[d^{\prime}]$. We first define another auxiliary metric
$w_{g}$ on $V$ as follows.

  * •

For each $1\leq j\leq d$, we consider the matching $M_{g(j)}$ between $S$ and
$V_{g(j)}$. If we denote by $v^{*}_{g(j)}$ the Steiner vertex in $V_{g(j)}$
matched with terminal $s_{j,1}$, then for each $u\in S_{j}$,
$w_{g}(u,v^{*}_{g(j)})=1$, and the weight in $w_{g}$ between $u$ and its
matched Steiner vertex in $M_{g(j)}$ is $2$.

  * •

For every other pair $v,v^{\prime}\in V$,
$w_{g}(v,v^{\prime})=w(v,v^{\prime})$.

Figure 9: An illustration of the metric $w_{g}$ (where $g(1)=1$ and
$g(k^{2/5})=k^{3/5}$). The only difference between metrics $w$ and $w_{g}$ are
the weight-$1$ pairs, which are shown in dashed lines.

See Figure 9 for an illustration. It is easy to verify that $w_{g}$ is a
metric. The only difference between metrics $w$ and $w_{g}$ are the weight-$1$
pairs. In particular, for each $S_{i}$, there is a star graph consisting of
weight-$1$ edges in $w_{g}$ that spans all terminals in $S_{i}$, while there
is no such graph in $w$. These star graphs are the reason that the costs
${\mathsf{ST}}(V,T,w)$ and ${\mathsf{ST}}(V,T,w_{g})$ are roughly separated by
factor $2$.

For every mapping $f\in{\mathcal{F}}$, we define a metric Steiner Tree
instance $I_{(f,g)}$ as $I_{(f,g)}=(\hat{V},\hat{T},\hat{w}_{(f,g)})$ where
the metric $\hat{w}_{(f,g)}$ is defined as: for every pair
$v,v^{\prime}\in\hat{V}$,
$\hat{w}_{(f,g)}(v,v^{\prime})=w_{g}(f(v),f(v^{\prime}))$. The distribution
$\mathcal{D}_{\textnormal{{Y}}}$ is simply defined to be the uniform
distribution on all instances in ${\mathcal{I}}_{\sf Y}=\left\\{I_{(f,g)}\mid
f\in{\mathcal{F}},g\in{\mathcal{G}}\right\\}$, where ${\mathcal{G}}$ is the
collection of all mappings from $[d]$ to $[d^{\prime}]$.

On the one hand, it is easy to verify that every instance with non-zero
probability in $\mathcal{D}_{\textnormal{{N}}}$ is isomorphic to $(V,T,w)$,
and so it has the same Steiner Tree cost as $(V,T,w)$. Similarly, it is easy
to verify that every instance with non-zero probability in
$\mathcal{D}_{\textnormal{{Y}}}$ is isomorphic to $(V,T,w_{g})$ for an
arbitrary $g\in{\mathcal{G}}$ (and in fact all instances
$\left\\{(V,T,w_{g})\right\\}_{g\in{\mathcal{G}}}$ are isomorphic to each
other), and so it has the same Steiner Tree cost as $(V,T,w_{g})$. We next
show that ${\mathsf{ST}}(V,T,w)$ is roughly two times
${\mathsf{ST}}(V,T,w_{g})$ for every $g$. Recall that ${\mathcal{I}}_{\sf
N}=\left\\{I_{f}\mid f\in{\mathcal{F}}\right\\}$ and ${\mathcal{I}}_{\sf
Y}=\left\\{I_{(f,g)}\mid f\in{\mathcal{F}},g\in{\mathcal{G}}\right\\}$.

######  Claim 7.2.

Any instance in ${\mathcal{I}}_{\sf N}$ has Steiner Tree cost at least
$2k^{2/5}/\varepsilon$. Any instance in ${\mathcal{I}}_{\sf Y}$ has Steiner
Tree cost at most $k^{2/5}(1/\varepsilon+4)$. Hence the cost of any instance
in ${\mathcal{I}}_{\sf N}$ is more than $(2-8\varepsilon)$ times the cost of
any instance in ${\mathcal{I}}_{\sf Y}$.

###### Proof.

For any instance in ${\mathcal{I}}_{\sf N}$, any Steiner node has weight $1$
to at most $1$ terminals, so the Steiner Tree cost equals the spanning tree of
terminals, which is $2(k^{2/5}+k^{2/5}/\varepsilon-1)>2k^{2/5}/\varepsilon$.
For any instance in ${\mathcal{I}}_{\sf Y}$, any group of special terminnal
$S_{i}$ have weight $1$ to a common Steiner node, thus we can connect them at
a cost of $1/\varepsilon$. Thus the Steiner Tree cost is at most
$(1/\varepsilon)k^{2/5}+2(k^{2/5}+k^{2/5}-1)<(1+4\varepsilon)(k^{2/5}/\varepsilon)$.
Moreover, it is easy to verify that the ratio of these costs is more than
$(2-8\varepsilon)$ for any $\varepsilon>0$. ∎

We then define distribution
${\mathcal{D}}=(\mathcal{D}_{\textnormal{{Y}}}+\mathcal{D}_{\textnormal{{N}}})/2$,
and consider the following problem: Given an instance sampled from
${\mathcal{D}}$, estimate its value (Steiner Tree cost) to within a factor of
$(2-8\varepsilon)$. From 7.2, the problem is equivalent to the problem of
determining a random instance (sampled from ${\mathcal{D}}$) comes from
$\mathcal{D}_{\textnormal{{Y}}}$ or $\mathcal{D}_{\textnormal{{N}}}$. If a
randomized algorithm reports correctly with probability at least $2/3$, then
we say that the algorithm _distinguishes between
$\mathcal{D}_{\textnormal{{Y}}}$ and $\mathcal{D}_{\textnormal{{N}}}$_.
Therefore, in order to prove Theorem 4, it suffices to prove that any
algorithm that distinguishes between $\mathcal{D}_{\textnormal{{Y}}}$ and
$\mathcal{D}_{\textnormal{{N}}}$ performs $\tilde{\Omega}(k^{6/5})$ queries in
the worst case.

The remainder of this section is dedicated to the proof that any algorithm
that distinguishes between $\mathcal{D}_{\textnormal{{Y}}}$ and
$\mathcal{D}_{\textnormal{{N}}}$ performs $\tilde{\Omega}(k^{6/5})$ queries in
the worst case. Before we give the detailed proof, we provide some intuition.
From the construction of $\mathcal{D}_{\textnormal{{Y}}}$,
$\mathcal{D}_{\textnormal{{N}}}$, distinguishing between
$\mathcal{D}_{\textnormal{{Y}}}$ and $\mathcal{D}_{\textnormal{{N}}}$ is
essentially distinguishing between the metric $w$ and the metric $w_{g}$ (for
any $g$), where the identities of vertices are randomized. The main difference
between metrics $w$ and $w_{g}$ is that, in $w_{g}$, there exist Steiner
vertices that are connected to more than one (actually $1/\varepsilon$)
special terminals with weight-$1$ edges. We call such Steiner vertices _secret
vertices_. We now argue from a high level that finding a secret vertex
requires $\Omega(k^{6/5})$ queries. We call edges of weight $0$ or $1$
_crucial_ edges, since if a terminal $u$ is found incident to a crucial edge,
then we can immediately tell if $u$ is special or regular.

On the one hand, note that in the metric $w_{g}$, there are $k^{2/5}$ secret
vertices. So if we sample a random Steiner vertex $v$ from $\bigcup_{1\leq
i\leq d^{\prime}}V_{i}$ (as the vertices in $V_{0}$ are irrelevant in
distinguishing between metrics $w$ and $w_{g}$), then the probability that $v$
is a secret vertex is $O(k^{-3/5})$ as $|\bigcup_{1\leq i\leq
d^{\prime}}V_{i}|=\Omega(k)$, and so it takes $\Omega(k^{3/5})$ random samples
to get a secret vertex. However, in order to certify that $v$ is indeed a
secret vertex, we need to find at least $2$ crucial edges incident to it,
which takes $\Omega(k)$ queries as every Steiner vertex is only incident to
$O(1)$ crucial edges both in $w$ and $w_{g}$. Altogether, it takes
$\Omega(k^{3/5})\cdot\Omega(k)=\Omega(k^{8/5})$ queries to discover a secret
vertex in this way.

On the other hand, note that there are $k^{2/5}$ special terminals (in both
$w$ and $w_{g}$). So if we sample a random terminal $u$ from $T$, then the
probability that $u$ is a special terminal is $O(k^{-3/5})$ as
$|T|=\Omega(k)$, and so it takes $\Omega(k^{3/5})$ random samples to get a
special terminal. In order to certify that $u$ is indeed a special terminal,
we need to find a crucial edge incident to it. Since each special terminal is
only incident to $k^{3/5}$ crucial edges (in both $w$ and $w_{g}$), this takes
$\Omega(n/k^{3/5})=\Omega(k^{2/5})$ queries. Altogether, it takes
$\Omega(k^{3/5})\cdot\Omega(k^{2/5})=\Omega(k)$ queries to discover a special
terminal. If the algorithm performs $o(k^{6/5})$ queries, it is only able to
discover $o(k^{1/5})$ special vertices. As the identities of the terminals are
randomized, from the Birthday Paradox, with high probability all discovered
special vertices come from different groups in $S_{1},\ldots,S_{d}$, so even
if the algorithm has queried all edges incident to these discovered terminals,
with high probability it will not find any vertex that is incident to more
than one discovered special terminal, and so with high probability it will not
find any secret vertex.

In the remainder of the section, we formalize the ideas described above, in a
way similar to Section 5 and Section 6. We begin with some definitions. For
convenience, we will think of the algorithm as performing queries on $w$, but
it does not know the identities of the vertices (that is, it does know the set
$T$ and the partition $(V_{0},V_{1},\ldots,V_{d^{\prime}})$ of $V\setminus T$,
but it does not know which special terminal in set $S_{j}$ is $s_{j,i}$, for
any $j,i$). Over the course of the algorithm, we say a terminal $u$ is
_settled_ at some step, iff the set of queries performed thus far uniquely
identify $u$ to be a special terminal or a regular terminal, i.e., we have
discovered a crucial edge incident to it; otherwise we say it is _unsettled_.
For convenience of the analysis, whenever a terminal $u$ is settled, if $u$ is
a regular terminal, then we immediately reveal to the algorithm which $T_{i}$
group it belongs to; if it is a special terminal, we will immediately reveal
to the algorithm all crucial (weight-$1$) edges incident to it.

For each special terminal $u\in S$, we denote by $V(u)$ be set of Steiner
nodes that are connected to $u$ by some matching in
$\left\\{M_{1},\ldots,M_{d^{\prime}}\right\\}$. Clearly, in $w$, vertex $u$ is
connected to all vertices in $V(u)$ via crucial (weight-$1$) edges, while in
$w_{g}$, this is not always the case. We say that an edge is _discovered_ if
we can uniquely identify the weight of the edge. For any $0<\alpha<1$, we say
an unsettled terminal $u$ is _$\alpha$ -well-discovered_ if at least one of
the following four conditions is satisfied:

  1. P1.

There are at least $\alpha k^{2/5}$ groups $T_{i}$ such that we have
discovered at least one edge in $E(u,T_{i})$.

  2. P2.

There are at least $\alpha k^{2/5}$ special terminals $u^{\prime}$ such that
we discovered an edge in $E(u,V(u^{\prime}))$.

  3. P3.

$u$ is a regular terminal in the $T_{i}$, and there are at least $\alpha k$
terminals $u^{\prime}$ such that some edge in $E(u^{\prime},T_{i})$ has been
discovered.

  4. P4.

$u$ is a special terminal, and there are at least $\alpha k$ terminals
$u^{\prime}$ such that some edge in $E(u^{\prime},V(u))$ has been discovered.

The following lemma is the main technical tool for the proof of the
$\Omega(k^{6/5})$ lower bound. Intuitively, it shows that, if the algorithm
perform $o(k^{6/5})$ queries, then not only it settles or
$(\varepsilon/200)$-well-discovers very few terminals, but also it has very
limited knowledge upon the edges that it has not queried.

######  Lemma 7.1.

Let $\mathsf{Alg}$ be any deterministic algorithm that performs at most
$\varepsilon^{2}k^{6/5}/10^{9}$ queries. Then:

  * •

If the input to $\mathsf{Alg}$ is a random instance from
$\mathcal{D}_{\textnormal{{N}}}$, then with probability at least $9/10$, the
number of terminals that are either settled or $(\varepsilon/200)$-well-
discovered is at most $\varepsilon k^{4/5}/10^{4}$, and at most $\varepsilon
k^{1/5}/10^{4}$ of them are special terminals; and conditioned on the query
sequence and its answers over the course of the algorithm, for every terminal
that is neither settled nor $(\varepsilon/200)$-well-discovered, the
probability that it is a special terminal is at most $2/k^{3/5}$.

  * •

If the input to $\mathsf{Alg}$ is a random instance from
$\mathcal{D}_{\textnormal{{Y}}}$, then with probability at least $9/10$,

    * –

the number of terminals that are either settled or $(\varepsilon/200)$-well-
discovered is at most $\varepsilon k^{4/5}/10^{4}$;

    * –

at most $\varepsilon k^{1/5}/10^{4}$ of them are special terminals; and

    * –

all these special terminals belong to different $S_{i}$ groups.

Moreover, conditioned on the query sequence and its answers over the course of
the algorithm, for every unqueried edge between a Steiner vertex and a
not-$(\varepsilon/100)$-well-discovered terminal, the probability that the
edge is a crucial (weight-$1$) edge and the Steiner vertex is a secret vertex
is at most $2/k^{8/5}$.

We provide the proof of Lemma 7.1 in Section 7.2.2 and Section 7.2.3, after we
complete the proof of the $\Omega(k^{6/5})$ lower bound using it.

####  7.2.1 Completing the Proof of the $\Omega(k^{6/5})$ Lower Bound

Recall that
${\mathcal{D}}=(\mathcal{D}_{\textnormal{{Y}}}+\mathcal{D}_{\textnormal{{N}}})/2$.
In this subsection we use Lemma 7.1 to prove the following lemma.

######  Lemma 7.2.

Any randomized algorithm that, given a random instance sampled from
${\mathcal{D}}$, reports correctly with probability at least $2/3$ that the
instance comes from $\mathcal{D}_{\textnormal{{Y}}}$ or
$\mathcal{D}_{\textnormal{{N}}}$, performs at least
$\varepsilon^{2}k^{6/5}/10^{9}$ queries in the worst case.

From Yao’s minimax principle [Yao77], it suffices to consider only
deterministic algorithms that report correctly on at least $2/3$-fraction (in
${\mathcal{D}}$) of the instances.

We define a _transcript_ to be the union of a query sequence and all its
answers. We can define $\alpha$-well-discovered vertices and settled terminals
with respect to a transcript similarly.

Recall that each instance in ${\mathcal{I}}_{\sf N}$ is determined by a
mapping $f\in{\mathcal{F}}$ and each instance in ${\mathcal{I}}_{\sf Y}$ is
determined by a mapping $f\in{\mathcal{F}}$ and a mapping $g\in{\mathcal{G}}$,
so $|{\mathcal{I}}_{\sf Y}|=|{\mathcal{I}}_{\sf N}|\cdot|{\mathcal{G}}|$. Let
$\sigma$ be the transcript produced by the algorithm when given a random
instance from ${\mathcal{D}}$. Since the input is randomized, $\sigma$ is a
random variable. We say that $\sigma$ is _consistent_ with an instance $I$ iff
all answers to the queries in $\sigma$ are matched with the corresponding
weight-values in $I$. In order to prove Lemma 7.2, it suffices to show that,
if $\sigma$ always contains at most $\varepsilon^{2}k^{6/5}/10^{9}$ queries,
then with high probability, the ratio between the number of instances in
${\mathcal{I}}_{\sf Y}$ that are consistent with $\sigma$ (that we call
_consistent instances in ${\mathcal{I}}_{\sf Y}$_) and the number of instances
in ${\mathcal{I}}_{\sf N}$ that are consistent with $\sigma$ (that we call
_consistent instances in ${\mathcal{I}}_{\sf N}$_) is still roughly
$|{\mathcal{G}}|$. We prove this by showing that (i) for each consistent
instance $I_{f}\in{\mathcal{I}}_{\sf N}$, almost all mappings
$g\in{\mathcal{G}}$ give a consistent instance $I_{(f,g)}$; and (ii) for
almost all consistent instances $I_{(f,g)}\in{\mathcal{I}}_{\sf Y}$, the
instance $I_{f}\in{\mathcal{I}}_{\sf N}$ is also consistent.

We let $T^{*}$ be the subset of terminals that are either settled or
$(\varepsilon/200)$-well-discovered by $\sigma$ (so $T^{*}$ is a random
variable as well). We will focus on queries incident to vertices in $T^{*}$
and $S\setminus T^{*}$.

From Lemma 7.1, there are at most $1/10$-fraction of the consistent instances
in ${\mathcal{I}}_{\sf N}$ such that the desired properties (the number of
settled or $(\varepsilon/100)$-well-discovered terminals is low, etc) do not
hold; and there are at most $1/10$-fraction of the consistent instances in
${\mathcal{I}}_{\sf Y}$ such that the desired properties do not hold. We call
these instances _bad_ instances, and call all other consistent instances
_good_ instances.

Consider now any mapping $g\in{\mathcal{G}}$, we define the following instance
$I^{\prime}_{(f,g)}\in{\mathcal{I}}_{\sf Y}$ defined by $g$ and the $T^{*}$
which is slightly different from $I_{(f,g)}$. For each $1\leq j\leq d$, we
consider the matching $M_{g(j)}$ between $S_{j}$ and $V_{g(j)}$. If $S_{j}$
contains more than 1 terminals in $T^{*}$, then $I_{(f,g)}$ is not well
defined. If $S_{j}$ contains one such terminal and assume it is $s^{*}_{j}$,
then we first exchange the matching node of $s^{*}_{j}$ and $s_{j,1}$ in
$M_{g(j)}$. If $S_{j}$ contains no such terminal, then we do not change the
matching. After modifying the matching, for each $u\in S_{j}$, we make
$w_{g}(u,s^{*}_{g(j)})=1$ and the weight in $w_{g}$ between $u$ and its
matched Steiner vertex in $M_{g(j)}$ is $2$. Note that after the change, we
guarantee that we do not change the crucial edges incident on any terminal in
$T^{*}$.

##### From consistent instances in ${\mathcal{I}}_{\sf N}$ to consistent
instances in ${\mathcal{I}}_{\sf Y}$.

From Lemma 7.1, for every terminal $u\in T\setminus T^{*}$, the probability
(conditioned on $\sigma$ and its answers) that $u$ is special terminal is at
most $2/k^{3/5}$. Then from Markov’s Bound, with probability at least $0.98$
(i.e., on at least $0.98$-fraction of the good instances in
${\mathcal{I}}_{\sf N}$), the number of queries performed on edges in
$E(S\setminus T^{*},V\setminus T)$ is at most $\varepsilon k^{3/5}/100$. We
now show that, for such a good instance $I_{f}\in{\mathcal{I}}_{\sf N}$,
almost all mappings $g$ give consistent instance
$I^{\prime}_{(f,g)}\in{\mathcal{I}}_{\sf Y}$.

Now for a random mapping $g\in{\mathcal{G}}$. If we view the algorithm as
performing queries on $w_{g}$ (without knowing the identities of the
vertices), then from the perspective of the algorithm, the partitioning of the
special terminals into groups $S_{1},\dots,S_{k^{2/5}}$ is random. Since
$T^{*}$ contains at most $\varepsilon k^{1/5}/10^{4}$ special terminals, with
probability at least $1/10^{4}$, $|S_{j}\cap T^{*}|\leq 1$ for all $1\leq
j\leq d^{\prime}$ hold. Moreover, if $z$ queries are incident to terminals in
$S_{j}\setminus T^{*}$, then with probability at least $z/k^{3/5}$, no query
has been performed between $S_{j}\setminus T^{*}$ and $V_{g(j)}$. Thus with
probability at least $1-\varepsilon/100$, for each $1\leq j\leq d^{\prime}$,
no query has been performed on $E(S_{j}\setminus T^{*},V_{g(j)})$. If this
happens, then it is easy to verify that $I^{\prime}_{(f,g)}$ is a well defined
and consistent instance in ${\mathcal{I}}_{\sf Y}$, as the difference between
$w$ and $w_{g}$, in particular a subset of edges in $\bigcup_{1\leq j\leq
d^{\prime}}E(S_{j}\setminus T^{*},V_{g(j)})$, has not been queried at all.

Altogether, there are at least $0.98$-fraction of the good instances in
${\mathcal{I}}_{\sf N}$, such that for each such $I_{f}$, at least
$(1-\varepsilon/100-1/10^{4})\leq(1-10^{-2})$-fraction of mappings
$g\in{\mathcal{G}}$ can give consistent instances $I^{\prime}_{(f,g)}$ in
${\mathcal{I}}_{\sf Y}$.

##### From consistent instances in ${\mathcal{I}}_{\sf Y}$ to consistent
instances in ${\mathcal{I}}_{\sf N}$.

From Lemma 7.1, for every unqueried edge between a Steiner vertex and a
not-$(\epsilon/100)$-well-discovered terminal, the probability that the edge
is a crucial (weight-$1$) edge and the Steiner vertex is a secret vertex is at
most $2/k^{8/5}$. Therefore, for every $u\in S\setminus T^{*}$ and every
$1\leq i\leq d^{\prime}$, the probability that $u$ is a special terminal and
belongs to a group $S_{j}$ with $g(j)=i$ is at most
$(2/k^{8/5})\cdot(k^{2/5})=2/k^{6/5}$. For each $1\leq i\leq d^{\prime}$, if
we denote by $z_{i}$ the number of terminals $u\in S\setminus T^{*}$ such that
some edge from $E(u,V_{i})$ has been queried, then

$\Pr\Big{[}\exists j,\text{ s.t. }g(j)=i,\text{ and some edge in
$E(S_{j}\setminus T^{*},V_{i})$ has been
queried}\Big{]}\leq\frac{2z_{i}}{\varepsilon k^{6/5}}.$

Since the algorithm performs at most $\varepsilon^{2}k^{6/5}/10^{9}$ queries,
from Markov’s Bound, with probability at least $1-10^{-6}$ (i.e., on at least
$(1-10^{-6})$-fraction of the good instances in ${\mathcal{I}}_{\sf Y}$), for
all pairs $(i,j)$ with $g(j)=i$, no queries has been perform on
$E(S_{j}\setminus T^{*},V_{i})$. For each consistent instance
$I^{\prime}_{(f,g)}\in{\mathcal{I}}_{\sf Y}$ with the above property, it is
easy to verify that the corresponding instance $I_{f}$ in ${\mathcal{I}}_{\sf
N}$ is a consistent instance in ${\mathcal{I}}_{\sf N}$, as the difference
between $w$ and $w_{g}$, in particular a subset of edges in $\bigcup_{1\leq
j\leq d^{\prime}}E(S_{j}\setminus T^{*},V_{g(j)})$, has not been queried at
all.

Altogether, there are at least $(1-10^{-6})$ fraction of the good instances in
${\mathcal{I}}_{\sf Y}$, such that for each $I^{\prime}_{(f,g)}$ of them, the
corresponding instance $I_{f}$ is a consistent instance in ${\mathcal{I}}_{\sf
N}$.

Form the above discussion, the number of consistent instances in
${\mathcal{I}}_{\sf Y}$ is at least $0.9\cdot
0.98\cdot(1-10^{-2})|{\mathcal{G}}|>0.85|{\mathcal{G}}|$ times the number of
consistent instances in ${\mathcal{I}}_{\sf N}$, and it is at most
$|{\mathcal{G}}|/(0.9\cdot(1-10^{-6}))\leq 1.12|{\mathcal{G}}|$ times the
number of consistent instances in ${\mathcal{I}}_{\sf N}$. Therefore, the
algorithm reports correctly with probability at most
$\max\left\\{1/(1+0.85),1.12/(1+1.12)\right\\}\leq 2/3$.

####  7.2.2 Proof of Lemma 7.1 for $\mathcal{D}_{\textnormal{{N}}}$

In this subsection we prove of the first half of Lemma 7.1. We start with the
following claim.

######  Claim 7.3.

Let $\sigma$ be any transcript, and let
$\mathcal{D}_{\textnormal{{N}}}(\sigma)$ be the uniform distribution on all
instances in ${\mathcal{I}}_{\sf N}$ that are consistent with $\sigma$. Then

  * •

for every unqueried edge between a pair of terminals such that at least one is
unsettled and not $(\varepsilon/100)$-well-discovered, the probability in
$\mathcal{D}_{\textnormal{{N}}}(\sigma)$ that the edge is a crucial
(weight-$0$) edge is at most $2/k^{2/5}$; and

  * •

for every unqueried edge between a Steiner vertex and a unsettled and
not-$(\varepsilon/100)$-well-discovered terminal, the probability in
$\mathcal{D}_{\textnormal{{N}}}(\sigma)$ that the edge is a crucial
(weight-$1$) edge is at most $2/k$.

###### Proof.

We first prove the first property. Consider a pair $u,u^{\prime}$ of terminals
where terminal $u$ is unsettled and not $(\varepsilon/100)$-well-discovered.
Let $I,I^{\prime}$ be instances in ${\mathcal{I}}_{\sf N}$ that are consistent
with $\sigma$, such that in $I$, $u$ and $u^{\prime}$ belong to the same
$T_{j}$ group. We say that $I^{\prime}$ is _host_ by $I$, iff $I^{\prime}$ can
be obtained from $I$ by exchanging the role of $u$ with another unsettled
regular terminal $u^{\prime\prime}$ that is not in the same group as $u$ in
$I$. It is clear that in any such instance $I^{\prime}$, the answer of the
same query will $2$ (that is, the edge is not a crucial edge). Suppose $u$ and
$u^{\prime}$ are in group $T_{j}$. The number of such instances $I^{\prime}$
equals the number of terminal $u^{\prime\prime}$ such that (i)
$u^{\prime\prime}\notin T_{j}$, and no edge in $E(u^{\prime\prime},T_{j})$ has
been queried; and (ii) no edge between $u$ and the group $u^{\prime\prime}$
belongs to has been queried. Since $u$ is not $(\varepsilon/100)$-well-
discovered, Property P1, the number of $u^{\prime\prime}$ that violate (ii) is
at most $\varepsilon k/100$, and from Property P3, the number of
$u^{\prime\prime}$ that violate (i) is at most $\varepsilon k/100$. Therefore,
$I$ hosts at least $49k/50$ instances $I^{\prime}$. On the other hand, for
each instance $I^{\prime}$, the number of instances that hosts it is at most
$k^{3/5}$, since $|T_{j}|\leq k^{3/5}$. Altogether, over all instances in
${\mathcal{I}}_{\sf N}$ that are consistent with $\sigma$, at most
$50/(49k^{2/5})\leq(2/k^{2/5})$-fraction of them have $(u,u^{\prime})$ as a
crucial edge.

We now prove the second property. Consider an unsettled and
not-$(\varepsilon/100)$-well-discovered terminal $u$ and a Steiner vertex $v$.
Let $I,I^{\prime}$ be instances in ${\mathcal{I}}_{\sf N}$ that are consistent
with $\sigma$, such that in $I$, $u$ is a special terminal and $v\in V(u)$. We
say that $I^{\prime}$ is host by $I$ if $I^{\prime}$ can be obtained from $I$
by exchanging the role of $u$ with a unsettled regular terminal $u^{\prime}$
in $I$. The number of such instances is the number of unsettled regular
terminals $u^{\prime}$ in $I$ such that (i) no edge in $E(u^{\prime},V(u))$
has been queried; and (ii) no edge between $u$ and the group that contains
$u^{\prime}$ has been discovered. Since $u$ is not $(\varepsilon/100)$-well-
discovered, from Property P3, the number of regular terminals that violate (i)
is at most $\varepsilon k/100$, and Property P1, the number of regular
terminals that violate (ii) is at most $\varepsilon k^{3/5}\cdot
k^{2/5}/100=\varepsilon k/100$. Therefore, $I$ hosts at least $49k/50$
instances. On the other hand, any instance $I^{\prime}$ is host by at most one
instance since at most one crucial edge is incident to$v$. Altogether, over
all instances in ${\mathcal{I}}_{\sf N}$ that are consistent with $\sigma$, at
most $50/49k\leq(2/k)$-fraction of them have $(u,v)$ as a crucial edge. ∎

In the remainder of this subsection, we will refer to
$(\varepsilon/200)$-well-discovered vertices as _well-discovered vertices_ ,
for convenience. We call queries between two terminals _regular_ queries, and
queries between a terminal and a Steiner node _special_ queries. We say a
query is _good_ iff it discovers a previously-unknown crucial edge. In other
words, either (i) the query is a regular query, such that at least one
endpoint is not well-discovered, and the answer is $0$, or (ii) the query is a
special query such that the terminal is not $(\varepsilon/100)$-well-
discovered, and the answer is $1$. From 7.3, the probability that a regular
query is good is at most $2/k^{2/5}$, and the probability that a special query
is good is at most $2/k$. Therefore, if the algorithm performs at most
$\varepsilon^{2}k^{6/5}/10^{9}$ queries, then from Markov’s Bound, with
probability $1/50$, the number of good regular queries is at most
$\varepsilon^{2}k^{2/5}/10^{6}$, and the number of good special query is at
most $\varepsilon^{2}k^{3/5}/10^{6}$.

For every settled terminal, if it is not settled by a good query, it must
become well-discovered before it become settled. Thus if we can upper bound
the number of terminals that are well-discovered without but not settled at
some step, then we can upper bound the number of settled or well-discovered
terminals as well. For ease of analysis, we always assume that there are at
most $\varepsilon k^{4/5}/10^{4}$ terminals and $\varepsilon k^{1/5}/10^{4}$
special terminals that are settled or well-discovered, and we think of the
algorithm as being immediately terminated once this condition no longer holds.

There are four possiblities for a terminal to become well-discovered, and we
analyze them seperately.

Possibility 1: through P3. Let $u$ be such a vertex, so $u$ is a regular
terminal and the group that $T_{i}$ contains it has $\varepsilon k/200$
incident edges discovered. For each such edge, it is either discovered by a
query or because the its other endpoint is settled or well-discovered. Since
there are at most $\varepsilon k^{4/5}/10^{4}$ settled or well-discovered
terminals, there are at least $0.004\varepsilon k$ edges incident on $T_{i}$
that are discovered by queries. Thus, if the total number of queries is at
most $\varepsilon^{2}k^{6/5}/10^{9}$, then there are at most $\varepsilon
k^{1/5}/10^{6}$ groups such that the terminals in this group is well-
discovered through P3. Therefore, the number of terminals that become well-
discovered through P3 is at most $\varepsilon k^{4/5}/10^{6}$. Note that all
these terminals are regular terminals.

Possibility 2: through P4. Let $u$ be such a vertex, so $u$ is a special
terminal and the set $V(u)$ has $\varepsilon k/200$ incident edges discovered.
By the same argument, for at most $\varepsilon k^{4/5}/10^{4}$ of these edges,
the other endpoint is a settled or well-discovered terminal, and all the
others are discovered by queries. Therefore, the number of such terminals is
at most $\varepsilon k^{1/5}/10^{6}$, and all of them are special terminals.

Possibility 3: through P1 but not P3/P4. Let $u$ be such a vertex, so there
are at least $\varepsilon k^{2/5}/200$ groups $T_{i}$ such that some edge in
$E(u,T_{i})$ has been discovered. Note that each such edge is discovered
either by a query, or because we have discovered all terminals in $T_{i}$. By
previous analysis, there are at most $\varepsilon k^{1/5}$ of them. Therefore,
at least $0.004\varepsilon k^{2/5}$ edges incident on $u$ are queried.

Possibility 4: through P2 but not P3/P4. Let $u$ be such a vertex, so there
are at least $\varepsilon k^{2/5}/200$ special terminals $u^{\prime}$ such
that some edge in $E(u,V(u^{\prime}))$ has been discovered. Note that such an
edge is discovered either by a query, or because $u^{\prime}$ has already been
settled. Therefore, at least $0.004\varepsilon k^{2/5}$ edges incident to $u$
are queried.

From the analysis in Possibilities $3$ and $4$, for any terminal that becomes
well-discovered through P1 or P2 but not P3 or P4, at least $0.004\varepsilon
k^{2/5}$ of its incident edges have been queried. Therefore, there are at most
$\varepsilon k^{4/5}/(4\cdot 10^{6})$ such vertices. However, such terminals
could be either regular or special, and we still need to upper bound the
number of such special terminals. Let $u$ be any such terminal, and consider
the moment when exactly $0.004\varepsilon k^{2/5}$ of its incident edges are
queried. From 7.3, for any Steiner node $v$, the probability that $(u,v)$ is a
crucial (weight-$1$) edge is at most $2/k$. It follows that the probability
that $u$ is a special terminal is at most $(2/k)\cdot(k/k^{3/5})=2/k^{3/5}$.
By Markov’s Bound, the number of special terminals that are well-discovered is
at most $\varepsilon k^{1/5}/10^{5}$ with probability at least $1/40$.

Altogether, with probability $1-1/40-1/50\geq 9/10$, the number of settled or
well-discovered terminals is at most $(\varepsilon^{2}k^{4/5}+\varepsilon
k^{4/5}+\varepsilon k^{1/5}+\varepsilon k^{4/5})/10^{6}<\varepsilon
k^{4/5}/10^{4}$, and the number of settled or well-discovered special
terminals is at most $(\varepsilon^{2}k^{1/5}+\varepsilon
k^{1/5})/10^{6}+\varepsilon k^{1/5}/10^{5}<\varepsilon k^{1/5}/10^{4}$.

####  7.2.3 Proof of Lemma 7.1 for $\mathcal{D}_{\textnormal{{Y}}}$

In this subsection we provide the proof of the second half of Lemma 7.1

Recall that Steiner vertices that are incident to more than one crucial edges
are called _secret vertices_. We assume for now that, over the course of the
algorithm,

  * •

for every Steiver vertex, we have discovered at most one crucial edge incident
to it;

  * •

no secret vertex has more than $\varepsilon k/10^{4}$ of its incident edges
discovered;

  * •

the number of terminals that are settled or well-discovered is at most
$\varepsilon k^{4/5}/10^{4}$; and

  * •

the number of special terminals that are settled or well-discovered is at most
$\varepsilon k^{1/5}/10^{4}$.

We will show at the end of this subsection that, if any of the above condition
is not satisfied, then the algorithm has to perform at least
$\varepsilon^{2}k^{6/5}/10^{9}$ as well.

We start with the following claim, whose is very similar to 7.3, and is
omitted here.

######  Claim 7.4.

Let $\sigma$ be any transcript, and let
$\mathcal{D}_{\textnormal{{Y}}}(\sigma)$ be the uniform distribution on all
instances in ${\mathcal{I}}_{\sf Y}$ that are consistent with $\sigma$. Then

  * •

for every unqueried edge between a pair of terminals such that at least one is
unsettled and not $(\varepsilon/100)$-well-discovered, the probability in
$\mathcal{D}_{\textnormal{{Y}}}(\sigma)$ that the edge is a crucial
(weight-$0$) edge is at most $2/k^{2/5}$; and

  * •

for every unqueried edge between a Steiner vertex and a unsettled and
not-$(\varepsilon/100)$-well-discovered terminal, the probability in
$\mathcal{D}_{\textnormal{{Y}}}(\sigma)$ that the edge is a crucial
(weight-$1$) edge is at most $2/k$.

Using 7.4 and the same arguments in the proof of Lemma 7.1 for
$\mathcal{D}_{\textnormal{{N}}}$, we can prove that the number of terminals
that are settled or well-discovered is at most $\varepsilon k^{4/5}/10^{4}$,
and at most $\varepsilon k^{1/5}/10^{4}$ of them are special terminals. In
order to prove that all settled or well-discovered special terminals belong to
different $S_{j}$ groups, we use the following two claims.

######  Claim 7.5.

Let $u^{*}$ be a special terminal that is either settled or
$(\varepsilon/200)$-well discovered. Then for every other
not-$(\varepsilon/100)$-well-discovered terminal $u$ and any other Steiner
vertex $v$, the probability that $u$ is a special terminal in the same $S_{j}$
group as $u^{*}$ and $(u,v)$ is a crucial edge is at most $2/k^{7/5}$.

###### Proof.

Let $I,I^{\prime}$ be instances in ${\mathcal{I}}_{\sf N}$, let $u^{*}$ be a
special terminal that is either settled or $(\varepsilon/200)$-well discovered
in both $I$ and $I^{\prime}$, let $u$ be a special vertex in the same $S_{j}$
group as $u^{*}$ in $I$, and let $v$ be a Steiner vertex such that $(u,v)$ is
a crucial edge in $I$. We say $I^{\prime}$ is _host_ by $I$, iff there are two
terminals $u^{\prime},u^{\prime\prime}$, such that $u^{\prime}$ is special and
$u^{\prime\prime}$ is regular, and $I^{\prime}$ can be obtained from $I$ by
giving the role of $u^{\prime}$ to $u$, giving the role of $u$ to
$u^{\prime\prime}$ and giving the role of $u^{\prime\prime}$ to $u^{\prime}$.
The vertex $u^{\prime}$ can be any not-$(\varepsilon/100)$-well-discovered
terminal in $S_{j}$ with no edge to $V(u)$ discovered. Since $u$ is not
$(\varepsilon/100)$-well-discovered, and we have assumed that each secret
Steiner vertex has at most $\varepsilon k/10^{4}$ of its incident edges
discovered, there are at least $0.99k$ choices for $u^{\prime}$. On the other
hand, $u^{\prime\prime}$ can be any terminal that has no edge discovered to
$V(u^{\prime})$ and the secret Steiner node of group $S_{j}$ in $I$. By the
same arguement, there are at least $0.99k$ such terminal. Since we have
assumed that at most $\varepsilon k^{1/5}/10^{4}$ special terminals are
$(\varepsilon/100)$-well-discovered, an instance $I$ hosts at least
$0.99^{2}k^{2}\cdot(k^{2/5}/\varepsilon)>0.98k^{12/5}/\varepsilon$ instances
$I^{\prime}$. On the other hand, for any instance $I^{\prime}$, the terminal
$u^{\prime}$ must be the terminal such that $v\in V_{u^{\prime}}$, and the
terminal $u^{\prime\prime}$ must in the same group as $u^{*}$. So there are at
most $k/\varepsilon$ instance $I$ that hosts $I^{\prime}$. Altogether, the
probability that all events happend is at most
$(k/\varepsilon)/(0.98k^{12/5}/\varepsilon)\leq 2/k^{7/5}$. ∎

######  Claim 7.6.

Let $u$ be a not-$(\varepsilon/100)$-well-discovered terminal and let $v$ be a
Steiner vertex. Then the probability that $(u,v)$ is a crucial (weight-$1$)
edge and $v$ is an secret vertex is at most $2/k^{8/5}$.

###### Proof.

Recall that we have assumed that $v$ has at most one crucial edge connecting
to a settled or a well-discovered terminal discovered. By definition, any
$(\varepsilon/100)$-well discovered terminal is also a well discovered
terminal. So there $v$ $v$ has at most one crucial edge connecting to a
settled or a $(\varepsilon/100)$-well-discovered terminal discovered. We
distinguish between the following two cases.

Case 1: There does not exist a settled or $(\varepsilon/100)$-well discovered
terminal $u^{\prime}$, such that $(u^{\prime},v)$ is a crucial edge and has
been discovered. For any consistent instance $I$ such that $u$ and $v$ has
weight $1$ and $v$ is an secret Steiner node. Suppose $u\in S_{i}$ and let
$S_{i}=\\{s_{i,1},\dots,s_{i,1/\varepsilon}\\}$, and suppose $v\in
V(s_{i,1})$. By assumption, no terminal in $S_{i}$ is $(\varepsilon/100)$-well
discovered. We say an instance $I^{\prime}$ is hosted by $I$ if all special
terminals not in $S_{i}$ and their weights to the Steiner nodes are the same
as $I$, and the set $V(s_{i,t})$ in $I^{\prime}$ is identical to the set
$V(s_{i,t})$ in $I$ for all $1\leq t\leq 1/\varepsilon$.

We first count the number of such consistent instances $I^{\prime}$. For each
$1\leq t\leq 1/\varepsilon$, we define $T^{*}_{t}$ as the set of regular
terminals that with no edges to $V(s_{i,t})$ discovered. Since no terminal in
$S_{i}$ is $(\varepsilon/100)$-well discovered, every set $T^{*}_{t}$ has size
at least $(1-\varepsilon/100)k$. For each $1\leq t\leq 1/\varepsilon$,
consider any group of terminals $t_{1}\dots,t_{1/\varepsilon}$ such that
$t_{j^{\prime}}\in T^{\prime}_{j^{\prime}}\cap T^{\prime}_{j}$. Any
$t_{j^{\prime}}$ can have weight one to all Steiner nodes in
$V_{s_{j^{\prime}}}$ and $V_{s_{j}}$, which means we can make any terminal in
$V_{s_{j}}$ an secret terminal. Thus such group can construct at least
$k^{3/5}/\varepsilon$ consistent instances $I^{\prime}$. On the other hand,
since any $|T_{j^{\prime}}|\geq(1-\varepsilon/100)k$, the number of such group
is at least $((1-49\varepsilon/50)k)^{1/\varepsilon}>(49/50)\cdot
k^{1/\varepsilon}$. Thus, $I$ hosts at least
$(49/50)k^{1/\varepsilon}\cdot(k^{3/5}/\varepsilon)$ instances $I^{\prime}$.

Now we count how many instance can host an instance $I^{\prime}$. For any
instance $I^{\prime}$, an instance $I$ that hosts it can only change the
terminals in $S_{i}$ that has weight $1$ to $v$, and so one of the terminal in
$S_{i}$ should be $u$. Moreover, every terminal in $S_{i}$ should has weight
$1$ to $v$. The total number of such instance is at most
$k^{1/\varepsilon}\cdot 1/\varepsilon$ since $u$ could replace any terminal in
$S_{i}$. Thus, the probability that $v$ and $u$ has weight $1$ and $v$ is an
secret Steiner node is at most
$(k^{1/\varepsilon-1}\cdot(1/\varepsilon))/((49/50)k^{1/\varepsilon}k^{3/5}\cdot(1/\varepsilon))<2/k^{8/5}$.

Case 2: There does not exist a settled or $(\varepsilon/100)$-well discovered
terminal $s_{j^{*}}$, such that $(s_{j^{*}},v)$ is a crucial edge and has been
discovered. Note that $s_{j^{*}}\neq u$. For any instance $I$ such that $u$
and $v$ has weight $1$. We say an instance $I^{\prime}$ is hosted by $I$ as
the same definition as the first case, except that now $u$ must still in
$S_{i}$, and moreover, we exchange one Steiner node in $V_{j^{*}}$ with
$V_{j}$ for some $j$. We first count the number of $I^{\prime}$ hosted by $I$.
We define $T^{\prime}_{j}$ the same as the first case. Suppose $v\in
V_{\ell^{*}}$, for any $1\leq\ell\leq k^{3/5}$ and $\ell\neq\ell^{*}$, we
define $v^{*}_{\ell}$ as the only one vertex in $V_{j}^{*}\cap V_{\ell}$, and
$T^{*}_{\ell}$ as the set of terminals that does not have weight one to
$v^{*}_{\ell}$. We also define $v^{*}{\ell^{*}}=v$ and $T^{*}_{\ell^{*}}$ as
the set of terminals that does not have weight one to $v^{*}_{\ell^{*}}$. Now
for any $1\leq\ell\leq k^{3/5}$, for any group of terminals
$t_{1},\ldots,t_{1/\varepsilon}$ such that for any $j^{\prime}\neq j^{*}$,
$t_{j^{\prime}}\in T^{\prime}_{j^{\prime}}\cap T^{*}_{\ell}$ and
$t_{j^{*}}=s_{j^{*}}$, we can make $v^{*}_{\ell}$ the secret Steiner node of
this group. Moreover, to do so, we can exchange $v^{*}_{\ell}$ from
$V_{s_{j^{*}}}$ with any $V_{s_{j^{\prime}}}$ since we will not change the
weight between any pair of vertices by doing so. Since the algorithm only
perform at most $\varepsilon^{2}k^{6/5}/10^{9}$ queries and settled or
$(\varepsilon/100)$-well discovered at most $O(k^{4/5})$ terminals, there are
$(1-o(1))k^{3/5}$ number of index $\ell$ such that
$|T^{*}_{\ell}|>(1-\varepsilon/100)k$. For such $\ell$, the number of groups
$t_{1},\dots,t_{1/\varepsilon}$ is at least $0.99k^{1/\varepsilon-1}$. So the
total number of instances ${\mathcal{I}}^{\prime}$ hosted by $I$ is at least
$(1-o(1)k^{3/5}\cdot k^{1/\varepsilon-1}\cdot(1/\varepsilon)$. On the other
hand, for any instance $I^{\prime}$, it is hosted by at most
$k^{1/\varepsilon-2}\cdot(1/\varepsilon)$ instance $I$ since we cannot
exchange $s_{\ell^{*}}$ and $u$ must be a special terminal in $S_{i}$. This
implies that $v$ and $u$ has weight $1$ and $v$ is a secret Steiner node is at
most
$(k^{1/\varepsilon-2}\cdot(1/\varepsilon))/((1-o(1))0.99k^{1/\varepsilon-1}k^{3/5}\cdot{1/\varepsilon})<2/k^{8/5}$.
∎

Remember that a special query is called a _good_ query iff it discovers a
crucial edge between a not-well-discovered terminal and a Steiner node. If a
special terminal is ever settled, then it is either due to a good special
query incident to it, or because it becomes well-discovered at some step. We
analyze the probability that a special query $(u,v)$ is a good query, and $u$
is in the same group $S_{i}$ with some terminal $u^{\prime}$ that is already
settled or $(\varepsilon/200)$-well discovered. By 7.6, the probability that
the query is a good query and $v$ is an secret Steiner node is at most
$2/k^{8/5}$. On the other hand, if the query is a good query but $v$ is not an
secret terminal, it means $v\in V(u)$. By 7.5, the probability that it is a
good query and $u$ and a fix settled or $(\varepsilon/200)$-well discovered
$u^{*}$ in the same group $S_{i}$ is at most $2/k^{7/5}$. Since there are at
most $\varepsilon k^{1/5}/10^{4}$ such $u^{*}$. So the probability that a
special is a good query and $u$ is in the same group $S_{i}$ with some
terminal $u^{\prime}$ that is already settled or $(\varepsilon/200)$-well
discovered is at most $\varepsilon/10^{4}k^{6/5}$. With probablity at least
$1-\varepsilon/1000$, there is no such query through out the algorithm by
Markov’s Bound.

Now we consider the well-discovered terminals. When a terminal is well-
discovered but not settled, it is still not $(\varepsilon/100)$-well
discovered. By 7.6, the probability that it is in the same group $S_{i}$ with
some terminal $u^{\prime}$ that is already settled or $(\varepsilon/200)$-well
discovered is at most $(2/k^{8/5})\cdot(\varepsilon k^{1/5}/10^{4})\cdot
k^{3/5}<\varepsilon/100k^{4/5}$. Since there are at most well-discovered
$\varepsilon k^{4/5}/10^{4}$, no well-discovered terminal belongs to the same
group with some terminal $u^{\prime}$ that is already settled or well-
discovered.

Finally, we need to prove the assumption that there is no secret Steiner node
has at least $\varepsilon k/10^{4}$ edges discovered. Since we only performed
at most $\varepsilon^{2}k^{6/5}/10^{9}$ queries, there are at most
$\varepsilon k^{1/5}/10^{4}$ terminals that are queried at least $\varepsilon
k/10^{5}$ times. By 7.6, the probability that such terminal is secret is at
most $2/k^{8/5}\cdot k=2/k^{3/5}$. Thus with proability at least $1-k^{-2/5}$,
all these terminals are not secret. This finishes the proof of Lemma 7.1.

##  Appendix A An $O(nk)$-Query $(5/3)$-Approximation Algorithm

In this section, we explain how the previous work [Zel93] and [Du95] lead to
an $O(nk)$-query algorithm for computing a $(5/3)$-approximate Steiner Tree.
In fact, their results imply the following theorem.

######  Theorem 9.

For any instance $(V,T,w)$ of Steiner Tree problem, there exists a Steiner
tree ${\mathcal{T}}^{*}$ with weight at most $(5/3)\cdot{\mathsf{ST}}(V,T,w)$,
such that every edge in ${\mathcal{T}}^{*}$ is incident on some vertex in $T$.

We refer to such Steiner trees as _good trees_. From the above theorem, it is
not hard to observe that querying all terminal related distances is sufficient
to find a $(5/3)$-approximate Steiner Tree, and the query complexity is
$O(nk)$.

We now explain how the results in previous work [Zel93] and [Du95] imply
Theorem 9.

We start by introducing some definitions. Let ${\mathcal{T}}$ be a tree, let
$v$ be a vertex of ${\mathcal{T}}$, and let $v_{1},\ldots,v_{d}$ be the
neighbors of $v$. For each $1\leq i\leq d$, we delete edges
$(v,v_{1}),\ldots,(v,v_{i-1}),(v,v_{i+1}),\ldots,(v,v_{d})$, and define
${\mathcal{T}}_{i}$ to be the connected component of the remaining graph that
contains $v$, so ${\mathcal{T}}_{i}$ is a subtree of ${\mathcal{T}}$ that
contains $v$. We say that subtrees
${\mathcal{T}}_{1},\ldots,{\mathcal{T}}_{d}$ are obtained by _splitting
${\mathcal{T}}$ at $v$_.

Consider an instance $(V,T,w)$ and let ${\mathcal{T}}$ be a Steiner tree. Let
$c>1$ be an integer. We say that ${\mathcal{T}}$ is a _$c$ -Steiner tree_, iff
when we split ${\mathcal{T}}$ at all terminals, then each resulting subtree
contains at most $c$ terminals. It is easy to verify that any $2$-Steiner Tree
is a terminal spanning tree. We now show that every $3$-Steiner tree can be
converted into a good tree with at most the same cost. Let ${\mathcal{T}}$ be
a $3$-Steiner tree. Assume without loss of generality that every Steiner
vertex has degree at least $3$ (as otherwise we can suppress such a vertex and
get another Steiner tree with at most the same cost). We now claim that
${\mathcal{T}}$ does not contain any Steiner-Steiner edge. Assume not, then
such a pair of Steiner vertices must both belong to some subtree obtained by
splitting ${\mathcal{T}}$ at all terminals, and such a subtree contains at
least $(3+3-1-1)=4$ terminals, a contradiction. It was shown in [Zel93] and
[Du95] that, for any instance $(V,T,w)$, there exists a $3$-Steiner tree with
cost at most $(5/3)\cdot{\mathsf{ST}}(V,T,w)$, and the ratio $5/3$ here cannot
be improved. Theorem 9 now follows.

##  Appendix B Proof of 3.1

Let $v_{1},v_{2},v_{3}$ be three vertices in $V$. Assume $v_{1}\in V_{x_{1}}$,
$v_{2}\in V_{x_{2}}$, and $v_{3}\in V_{x_{3}}$, where $x_{1},x_{2},x_{3}$ are
nodes in tree $\rho$. We denote by $\ell_{1},\ell_{2},\ell_{3}$ the levels of
$x_{1},x_{2},x_{3}$, respectively, and assume w.l.o.g. that
$\ell_{1}\geq\ell_{2}$. Let $x^{\prime}_{1}$ be a leaf of $\rho$ that lies in
the subtree of $\rho$ rooted at $x_{1}$, and we define leaves
$x^{\prime}_{2},x^{\prime}_{3}$ similarly.

We first show that $w_{\sf N}$ is a metric on $V$ by showing that $w_{\sf
N}(v_{1},v_{2})\leq w_{\sf N}(v_{1},v_{3})+w_{\sf N}(v_{2},v_{3})$. By
definition, $w_{\sf
N}(v_{1},v_{2})=\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{2})$.
Let $\hat{x}$ be the lowest common ancestor of nodes $x_{1}$ and $x_{2}$ in
$\rho$. Assume that $y$ is the unique vertex on the
$x^{\prime}_{1}-x^{\prime}_{2}$ path that is closest (under
$\operatorname{dist}_{\rho}$) to $x_{3}$. We distinguish between the following
three cases, depending on the location of $y$.

Case 1: $y$ lies between (excluding) $\hat{x}$ and (including)
$x^{\prime}_{1}$. On the one hand, $w_{\sf
N}(v_{2},v_{3})\geq\operatorname{dist}_{\rho}(x_{2},x_{3})$; on the other
hand, $w_{\sf
N}(v_{1},v_{3})\geq\operatorname{dist}_{\rho}(x_{1},x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}$.

If $y$ lies between (excluding) $\hat{x}$ and (including) $x_{1}$, then

$\begin{split}&w_{\sf N}(v_{1},v_{3})+w_{\sf
N}(v_{2},v_{3})\geq\operatorname{dist}_{\rho}(x_{2},x_{3})+\operatorname{dist}_{\rho}(x_{1},x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(y,x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\operatorname{dist}_{\rho}(y,x_{3})+2\cdot\min\left\\{0,\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})-\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(y,x_{3}),\operatorname{dist}_{\rho}(y,x_{3})+\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})-\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})\right\\}\\\
&\geq\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(y,x_{3}),0\right\\}\\\
&\geq\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})\\\
&=\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{2})=w_{\sf
N}(v_{1},v_{2}).\end{split}$

If $y$ lies between (excluding) $x_{1}$ and (including) $x^{\prime}_{1}$, then

$\begin{split}&w_{\sf N}(v_{1},v_{3})+w_{\sf
N}(v_{2},v_{3})\geq\operatorname{dist}_{\rho}(x_{2},x_{3})+\operatorname{dist}_{\rho}(x_{1},x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(y,x_{1})+2\cdot\operatorname{dist}_{\rho}(y,x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\operatorname{dist}_{\rho}(y,x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(y,x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})-\operatorname{dist}_{\rho}(y,x^{\prime}_{1})\right\\}\\\
&\geq\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(y,x_{3}),\operatorname{dist}_{\rho}(y,x_{3})+\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})-\operatorname{dist}_{\rho}(y,x^{\prime}_{1})\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(y,x_{3}),0\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})\\\
&=\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{2})=w_{\sf
N}(v_{1},v_{2}).\end{split}$

Case 2: $y$ lies between (excluding) $\hat{x}$ and (including)
$x^{\prime}_{2}$. The analysis in this case is symmetric to that of Case $1$,
with an additional observation that
$\operatorname{dist}_{\rho}(x_{1},x^{\prime}_{1})\leq\operatorname{dist}_{\rho}(x_{2},x^{\prime}_{2})$
(as $\ell_{1}\geq\ell_{2}$).

Case 3: $y=\hat{x}$. In this case, from the definition of $w_{\sf N}$, $w_{\sf
N}(v_{2},v_{3})\geq\operatorname{dist}_{\rho}(x_{2},x_{3})$, and $w_{\sf
N}(v_{1},v_{3})\geq\operatorname{dist}_{\rho}(x_{1},x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}$.
Therefore,

$\begin{split}&w_{\sf N}(v_{1},v_{3})+w_{\sf
N}(v_{2},v_{3})\geq\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(\hat{x},x_{3})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})\right\\}\\\
&\geq\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(\hat{x},x_{3}),\operatorname{dist}_{\rho}(x^{\prime}_{3},x_{3})+\operatorname{dist}_{\rho}(\hat{x},x_{3})-\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})\right\\}\\\
&\geq\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+2\cdot\min\left\\{\operatorname{dist}_{\rho}(\hat{x},x_{3}),0\right\\}\\\
&=\operatorname{dist}_{\rho}(x_{1},x_{2})+2\cdot\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})\\\
&=\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{1})+\operatorname{dist}_{\rho}(x^{\prime}_{1},x_{2})=w_{\sf
N}(v_{1},v_{2}).\end{split}$

This completes the proof that $w_{\sf N}$ is a metric on $V$.

We now proceed to show that $w_{\sf Y}$ is a metric on $V$ by showing that
$w_{\sf Y}(v_{1},v_{2})\leq w_{\sf Y}(v_{1},v_{3})+w_{\sf Y}(v_{2},v_{3})$. We
distinguish between the following cases.

Case 1: $v_{1},v_{2},v_{3}\in S$. In this case,

$w_{\sf
Y}(v_{1},v_{2})=\operatorname{dist}_{\rho}(v_{1},v_{2})\leq\operatorname{dist}_{\rho}(v_{1},v_{3})+\operatorname{dist}_{\rho}(v_{2},v_{3})=w_{\sf
Y}(v_{1},v_{3})+w_{\sf Y}(v_{2},v_{3}).$

Case 2: At most one of $v_{1},v_{2},v_{3}$ lies in $S$. In this case,

$w_{\sf Y}(v_{1},v_{2})=w_{\sf N}(v_{1},v_{2})\leq w_{\sf
N}(v_{1},v_{3})+w_{\sf N}(v_{2},v_{3})=w_{\sf Y}(v_{1},v_{3})+w_{\sf
Y}(v_{2},v_{3}).$

Case 3: Exactly two of $v_{1},v_{2},v_{3}$ lie in $S$. We further consider the
following subcases.

Case 3.1: $v_{1},v_{2}\in S$, and $v_{3}\notin S$. In this case,

$w_{\sf Y}(v_{1},v_{2})\leq w_{\sf N}(v_{1},v_{2})\leq w_{\sf
N}(v_{1},v_{3})+w_{\sf N}(v_{2},v_{3})=w_{\sf Y}(v_{1},v_{3})+w_{\sf
Y}(v_{2},v_{3}).$

Case 3.2: $v_{2},v_{3}\in S$, and $v_{1}\notin S$. The analysis in this case
uses almost identical arguments as Case 1 for showing that $w_{\sf N}$ is a
metric (since there we only uses the fact that $w_{\sf
N}(x_{2},x_{3})\geq\operatorname{dist}_{\rho}(x_{2},x_{3})$).

Case 3.3: $v_{1},v_{3}\in S$, and $v_{2}\notin S$. The analysis in this case
uses almost identical arguments as Case 2 for showing that $w_{\sf N}$ is a
metric (since there we only uses the fact that $w_{\sf
N}(x_{1},x_{3})\geq\operatorname{dist}_{\rho}(x_{1},x_{3})$).

This completes the proof that $w_{\sf Y}$ is a metric on $V$.

##  Appendix C Proof of 3.2

Let ${\mathcal{T}}^{\prime}$ be an optimal Steiner Tree of instance
$(S,T,w_{\sf N})$, and assume for contradiction that ${\mathcal{T}}^{\prime}$
contains an edge $(u_{x},u_{x^{\prime}})$ where $u_{x},u_{x^{\prime}}\notin T$
(or equivalently $x,x^{\prime}\notin L(\rho)$). Assume without loss of
generality that the level of $x$ in $\rho$ is at least the level of
$x^{\prime}$. Let $\tilde{x}$ be any leaf in $\rho$ that is a descendant of
$x$. Consider now the unique path in ${\mathcal{T}}^{\prime}$ connecting
$u_{\tilde{x}}$ to $u_{x}$, that we denote by $P$.

Assume first that the vertex $u_{x^{\prime}}$ does not belong to $P$. Let
${\mathcal{T}}$ be the tree obtained from ${\mathcal{T}}^{\prime}$ by
replacing the edge $(u_{x},u_{x^{\prime}})$ with edge
$(u_{\tilde{x}},u_{x^{\prime}})$. It is easy to verify that ${\mathcal{T}}$ is
a Steiner Tree. Moreover, from the definition of $w_{\sf N}$,

$w_{\sf
N}(u_{x},u_{x^{\prime}})=\operatorname{dist}_{\rho}(x,x^{\prime})+2\cdot\operatorname{dist}_{\rho}(x,\tilde{x})>\operatorname{dist}_{\rho}(x,x^{\prime})+\operatorname{dist}_{\rho}(x,\tilde{x})=w_{\sf
N}(u_{\tilde{x}},u_{x^{\prime}}),$

which implies that $w({\mathcal{T}})<w({\mathcal{T}}^{\prime})$, a
contradiction to the assumption that ${\mathcal{T}}^{\prime}$ is an optimal
Steiner Tree of the instance $(S,T,w_{\sf N})$.

Assume now that vertex $u_{x^{\prime}}$ belongs to $P$. Similarly, let
${\mathcal{T}}$ be the tree obtained from ${\mathcal{T}}^{\prime}$ by
replacing the edge $(u_{x},u_{x^{\prime}})$ with the edge
$(u_{\tilde{x}},u_{x})$. It is easy to verify that ${\mathcal{T}}$ is a
Steiner Tree. Moreover, from the definition of $w_{\sf N}$,

$w_{\sf
N}(u_{x},u_{x^{\prime}})=\operatorname{dist}_{\rho}(x,x^{\prime})+2\cdot\operatorname{dist}_{\rho}(x,\tilde{x})>\operatorname{dist}_{\rho}(x,\tilde{x})=w_{\sf
N}(u_{\tilde{x}},u_{x}),$

which implies that $w({\mathcal{T}})<w({\mathcal{T}}^{\prime})$, again a
contradiction to the assumption that ${\mathcal{T}}^{\prime}$ is an optimal
Steiner Tree of the instance $(S,T,w_{\sf N})$. This completes the proof of
the observation.

##  Appendix D Proof of 3.3

First of all, it is easy to see that there exists an optimal Steiner Tree such
that every Steiner vertex has degree at least $3$, since we can compress
degree-$2$ Steiner vertices without increasing the cost.

Consider now a tree ${\mathcal{T}}^{\prime}$ such that:

  1. 1.

${\mathcal{T}}^{\prime}$ is an optimal Steiner Tree such that every Steiner
vertex has degree at least $3$;

  2. 2.

on top of 1, ${\mathcal{T}}^{\prime}$ minimizes the number of Steiner
vertices;

  3. 3.

on top of 1 and 2, ${\mathcal{T}}^{\prime}$ maximizes the sum of levels of all
its Steiner vertices; and

  4. 4.

on top of 1, 2, and 3, ${\mathcal{T}}^{\prime}$ minimizes the number of edges
incident to Steiner vertices.

For each Steiner vertex $u_{x}$ in ${\mathcal{T}}^{\prime}$, we denote by
$d_{0}(x)$, $d_{1}(x)$, $d_{2}(x)$ the number of neighbors of $u_{x}$ in sets
$T_{0}(x)$, $T_{1}(x)$, $T_{2}(x)$, respectively. Consider now a Steiner
vertex $u_{x}$ in ${\mathcal{T}}^{\prime}$. Let $u_{x^{\prime}}$ be the parent
of $u_{x}$, and let $u_{x_{1}},u_{x_{2}}$ be the children of $u_{x}$, where
$u_{x_{1}}\in S_{1}(x)$ and $u_{x_{2}}\in S_{2}(x)$. We distinguish between
the following cases.

Case 1: One of $d_{0}(x),d_{1}(x),d_{2}(x)$ is $0$. Assume first that
$d_{0}(x)=0$. Then if $d_{1}(x)\geq d_{2}(x)$, we can replace Steiner vertex
$u_{x}$ with $u_{x_{1}}$ (that is, delete from ${\mathcal{T}}^{\prime}$ the
vertex $u_{x}$ and all its incident edges, and replace them with vertex
$u_{x_{1}}$ and edges in $\left\\{(u,u_{x_{1}})\mid(u,u_{x})\in
E({\mathcal{T}}^{\prime})\right\\}$), without increasing the total cost. In
this way, we either reduce the number of Steiner vertices by $1$, or increase
the sum of levels of all Steiner vertices, a contradiction to either 2 or 3.
The case where $d_{1}(x)\leq d_{2}(x)$ is symmetric. Assume now that
$d_{1}(x)=0$ (the case where $d_{2}(x)=0$ is symmetric). Then if $d_{2}(x)\geq
d_{0}(x)$, we can replace $u_{x}$ with $u_{x_{2}}$ either reducing the number
of Steiner vertices or increasing the sum of levels of all Steiner vertices,
leading to a contradiction to 2 or 3; if $d_{2}(x)<d_{0}(x)$, we can replace
$u_{x}$ with $u_{x^{\prime}}$, reducing the total cost, leading to a
contradiction to 1.

Case 2: One of $d_{1}(x),d_{2}(x)$ is at least $2$. Assume w.l.o.g. that
$d_{1}(x)\geq 2$. Let $u,u^{\prime}$ be two vertices of $T_{1}(x)$ that are
adjacent to $u_{x}$ in ${\mathcal{T}}^{\prime}$. We can replace the edge
$(u,u_{x})$ with edge $(u,u^{\prime})$, and it is easy to verify from the
definition of $w_{\sf N}$ that this does increase the total cost, leading to a
contradiction to 4.

Case 3: $d_{1}(x)=d_{2}(x)=1$ and $d_{0}(x)>2$. In this case, we can replace
$u_{x}$ with $u_{x^{\prime}}$, reducing the total cost, leading to a
contradiction to 1.

Altogether, we get that $d_{1}(x)=d_{2}(x)=1$ and $d_{0}(x)$ is either $1$ or
$2$, completing the proof of property (i) in the observation. We now focus on
proving property (ii). Let ${\mathcal{T}}^{\prime}$ be the tree defined above.
Let $u_{1}$ ($u_{2}$, resp.) be the neighbor of $u_{x}$ in $T_{1}(x)$
($T_{2}(x)$, resp.). Assume for contradiction that in there exists some vertex
$u\in T_{1}(x)$ such that $u\notin W_{1}$. From similar arguments in the proof
of 3.2, we can replace the edge $(u_{1},u_{x})$ with edge $(u_{1},u)$,
obtaining another optimal Steiner Tree with less edges incident to Steiner
vertices, a contradiction to 4. Assume for contradiction that in there exists
some vertex $u\notin T_{1}(x)$ such that $u\in W_{1}$. We root tree $W_{1}$ at
$u_{1}$, and it is easy to see that there exists some pair
$u^{\prime},u^{\prime\prime}$ of vertices in $W_{1}$, such that $u^{\prime}\in
T_{1}(x)$, $u^{\prime\prime}\notin T_{1}(x)$ and $u^{\prime}$ is the parent of
$u^{\prime\prime}$. Similarly, we can replace the edge
$(u^{\prime},u^{\prime\prime})$ with edge $(u_{x},u^{\prime\prime})$,
obtaining another Steiner Tree with strictly lower cost, a contradiction to 1.
Therefore, $T_{1}(x)\subseteq V(W_{1})\subseteq S_{1}(x)$. The proof of
$T_{2}(x)\subseteq V(W_{2})\subseteq S_{2}(x)$ is symmetric.

Last, we prove property (iii) in the observation. Let ${\mathcal{T}}^{\prime}$
be the tree defined above. Consider a Steiner vertex $u_{x}$ in
${\mathcal{T}}^{\prime}$. We denote by $u_{x^{\prime}}$ the parent of $u_{x}$,
and denote by $u_{\hat{x}}$ the other child of $u_{x^{\prime}}$. Assume for
contradiction that both $u_{x}$ and $u_{x^{\prime}}$ belong to
${\mathcal{T}}^{\prime}$. From property (i), $u_{x^{\prime}}$ has a neighbor
in $T(x)$, that we denote by $u$. From property (ii), since $u\in T(x)$,
vertex $u$ belongs to either $W_{1}$ or $W_{2}$. However,
$u_{x^{\prime}}\notin R(x)$, so $u$ does not belong to either $W_{1}$ or
$W_{2}$, a contradiction to the fact that $u_{x^{\prime}}$ and $u$ are
connected by an edge. Assume for contradiction that both $u_{x}$ and
$u_{\hat{x}}$ belong to tree ${\mathcal{T}}^{\prime}$. Let $u$ be the neighbor
of $u_{x}$ that belongs to the same connected component of
${\mathcal{T}}^{\prime}\setminus\left\\{u_{x}\right\\}$ as $u_{\hat{x}}$. From
property (i) and (ii) on $u_{\hat{x}}$, $u$ does not belong to the
corresponding subgraphs $\hat{W}_{1},\hat{W}_{2}$ for $u_{\hat{x}}$. Let
$\hat{u}$ be any leaf of $T(\hat{x})$. Via similar arguments, we can replace
the edge $(u_{x},u)$ with the edge $(u_{x},\hat{u})$, obtaining another
Steiner Tree with strictly lower cost, a contradiction to 1. Assume for
contradiction that none of $u_{x},u_{x^{\prime}},u_{\hat{x}}$ belongs to
${\mathcal{T}}^{\prime}$. Via similar arguments, it is easy to verify that we
can add either $u_{x}$ or $u_{\hat{x}}$ to ${\mathcal{T}}^{\prime}$ and
deleting some edges, obtaining another Steiner Tree with strictly lower cost,
a contradiction to 1.

##  Appendix E Analysis of the Algorithm in Section 6.1

In this section, we show that the spanning tree ${\mathcal{T}}$ output by the
algorithm in Section 6.1 is with high probability an $\alpha$-approximate
Steiner Tree. We denote by ${\mathsf{MST}}$ the minimum spanning tree cost on
$T$. Therefore, it suffices to show that, with high probability,
$w({\mathcal{T}})\leq(\alpha/2)\cdot{\mathsf{MST}}$, as ${\mathsf{MST}}$ is at
most twice the minimum Steiner Tree cost. Recall that $\beta=\alpha/(100\log
n)$.

Let ${\mathcal{T}}^{*}$ be a minimum spanning tree on $T$. Let
$\pi=(u_{1},u_{2},\ldots,u_{2k-2})$ be an Euler-tour of ${\mathcal{T}}^{*}$,
and for each $1\leq t\leq 2k-2$, we let $R_{\pi,t}=\left\\{u_{i}\mid t\leq
i\leq t+20\beta\log n\right\\}$. We define a bad event $\xi$ as follows.

##### Bad event $\xi$.

Let $\xi$ be the event that there exists some $t$, such that $R_{\pi,t}\cap
T^{\prime}=\emptyset$. We now show that $\Pr[\xi]=O(n^{-9})$. Since each edge
of ${\mathcal{T}}^{*}$ appears at most twice in the set
$\left\\{(u_{i},u_{i+1})\mid u_{i}\in R_{\pi,t}\right\\}$, $R_{\pi,t}$
contains at least $10\beta\log n$ distinct vertices. Therefore, the
probability that a random subset of $\left\lceil n/\beta\right\rceil$ vertices
in $V$ does not intersect with $R_{\pi,t}$ is at most $(1-(10\beta\log
n/k))^{k/\beta}\leq n^{-10}$. Taking the union bound over all $1\leq t\leq
2k-2$, we get that $\Pr[\xi_{1}]=O(n^{-9})$. Note that, if the event $\xi$
does not happen, then every consecutive window of $\pi$ of length $20\beta\log
n$ contains at least one element of $T^{\prime}$.

Let $u_{i_{1}},u_{i_{2}},\ldots,u_{i_{t^{\prime}}}$ be the vertices of $\pi$
that belongs to $T^{\prime}$ ($t^{\prime}$ may be larger than $|T^{\prime}|$
since we keep all copies of the same vertex), then for each $1\leq j\leq
t^{\prime}$, $|i_{j}-i_{j+1}|\leq 20\beta\log n$.

Let $u$ be any terminal in $T\setminus T^{\prime}$. Assume that the first
appearance of $u$ in $\pi$ is between $u_{i_{j}}$ and $u_{i_{j+1}}$, so
$w(u,T^{\prime})\leq\min\left\\{w(u,u_{i_{j}}),w(u,u_{i_{j+1}})\right\\}\leq
w(u_{i_{j}},u_{i_{j+1}})$, which is at most the total weight of all edges in
$\pi$ between $u_{i_{j}}$ and $u_{i_{j+1}}$. So from triangle inequality,
$\operatorname{dist}_{\pi}(u,T^{\prime})\leq\sum_{i_{j}\leq t\leq
i_{j+1}-1}w(v_{t},v_{t+1})$. As $|i_{j}-i_{j+1}|\leq 20\beta\log n$ holds for
all $1\leq j\leq t^{\prime}$, $\sum_{u\in T\setminus T^{\prime}}w(u,f(u))\leq
20\beta\log n\cdot w({\mathcal{T}}^{*})\leq 20\beta\log n\cdot{\mathsf{MST}}$.
Finally, since $w({\mathcal{T}}^{\prime})\leq{\mathsf{MST}}$, we conclude that
$w({\mathcal{T}})\leq 21\beta\log
n\cdot{\mathsf{MST}}\leq(\alpha/2)\cdot{\mathsf{MST}}$. Altogether, we
conclude that, with probability $1-O(n^{-9})$, the spanning tree
${\mathcal{T}}$ output by the algorithm in Section 6.1 is an
$\alpha$-approximate Steiner Tree.

## Acknowledgements

We thank anonymous reviwers for helpful comments and for pointing to us the
previous work [Du95] and [Zel93].

## References

  * [ACK19] Sepehr Assadi, Yu Chen, and Sanjeev Khanna.  Sublinear algorithms for ($\delta$\+ 1) vertex coloring.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 767–786. SIAM, 2019.
  * [BD97] Al Borchers and Ding-Zhu Du.  The k-steiner ratio in graphs.  SIAM Journal on Computing, 26(3):857–869, 1997.
  * [Beh21] Soheil Behnezhad.  Time-optimal sublinear algorithms for matching and vertex cover.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 873–884. IEEE, 2021.
  * [BGRS10] Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanita.  An improved lp-based approximation for steiner tree.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 583–592, 2010.
  * [CC08] Miroslav Chlebík and Janka Chlebíková.  The steiner tree problem on graphs: Inapproximability results.  Theoretical Computer Science, 406(3):207–214, 2008.
  * [CKT22] Yu Chen, Sanjeev Khanna, and Zihan Tan.  Sublinear algorithms and lower bounds for estimating mst and tsp cost in general metrics.  arXiv preprint arXiv:2203.14798, 2022.
  * [CRT05] Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan.  Approximating the minimum spanning tree weight in sublinear time.  SIAM Journal on computing, 34(6):1370–1379, 2005.
  * [CS09] Artur Czumaj and Christian Sohler.  Estimating the weight of metric minimum spanning trees in sublinear time.  SIAM Journal on Computing, 39(3):904–922, 2009.
  * [DP09] Devdatt P Dubhashi and Alessandro Panconesi.  Concentration of measure for the analysis of randomized algorithms.  Cambridge University Press, 2009.
  * [Du95] Ding-Zhu Du.  On component-size bounded steiner trees.  Discrete applied mathematics, 60(1-3):131–140, 1995.
  * [FN20] Manuela Fischer and Andreas Noever.  Tight analysis of parallel randomized greedy MIS.  ACM Trans. Algorithms, 16(1):6:1–6:13, 2020.
  * [GGR98] Oded Goldreich, Shari Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Journal of the ACM (JACM), 45(4):653–750, 1998.
  * [GJ79] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [GMRV20] Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, and Ali Vakilian.  Improved local computation algorithm for set cover via sparsification.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2993–3011. SIAM, 2020.
  * [GORZ12] Michel X Goemans, Neil Olver, Thomas Rothvoß, and Rico Zenklusen.  Matroids and integrality gaps for hypergraphic steiner tree relaxations.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1161–1176, 2012.
  * [GP68] Edgar N Gilbert and Henry O Pollak.  Steiner minimal trees.  SIAM Journal on Applied Mathematics, 16(1):1–29, 1968.
  * [GR97] Oded Goldreich and Dana Ron.  Property testing in bounded degree graphs.  In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 406–415, 1997.
  * [HK13] Mathias Hauptmann and Marek Karpiński.  A compendium on Steiner tree problems.  Inst. für Informatik, 2013.
  * [HPIMV16] Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian.  Towards tight bounds for the streaming set cover problem.  In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 371–383, 2016.
  * [IMR+18] Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee.  Set cover in sub-linear time.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2467–2486. SIAM, 2018.
  * [KZ97] Marek Karpinski and Alexander Zelikovsky.  New approximation algorithms for the steiner tree problems.  Journal of Combinatorial Optimization, 1(1):47–65, 1997.
  * [RZ05] Gabriel Robins and Alexander Zelikovsky.  Tighter bounds for graph steiner tree approximation.  SIAM Journal on Discrete Mathematics, 19(1):122–134, 2005.
  * [TZ22] Vera Traub and Rico Zenklusen.  Local search for weighted tree augmentation and steiner tree.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3253–3272. SIAM, 2022.
  * [Yao77] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222–227. IEEE Computer Society, 1977.
  * [Zel93] Alexander Z Zelikovsky.  An 11/6-approximation algorithm for the network steiner problem.  Algorithmica, 9(5):463–470, 1993.
  * [Zel96] Alexander Zelikovsky.  Better approximation bounds for the network and euclidean steiner tree problems.  Technical report, CS-96-06, Department of Computer Science, University of Virginia, 1996.