Finding an exact optimal solution is NP-Complete. However, there is polynomial time approximation algorithm that yields a factor 2 approximation. We say that a solution $S$ is 2-approximation for the problem if $w\left(S\right)\le2\cdot w\left(S^{*}\right)$ for some optimal solution $S^{*}$ .

Fix some $T\subseteq V\left(G\right)$ , we will show that the weight of any optimal solution for the original instance $\left(G,w\right)$ is exactly the same weight as of any optimal solution for $\left(\tilde{G},\tilde{w}\right)$ . We will do that by showing two inequalities: let $S^{*},\tilde{S}^{*}$ be optimal solutions for the original and the modified instances respectively. Then $w\left(S^{*}\right)\le w\left(\tilde{S}^{*}\right)$ and $w\left(\tilde{S}^{*}\right)\le w\left(S^{*}\right)$ .

Obviously, the inequality $w\left(\tilde{S}^{*}\right)\le w\left(S^{*}\right)$ holds, because $\tilde{G}$ contains all the edges of $G$ and for any edge $e$ in $G$ its weight over the modified instance $\tilde{G}$ have $\tilde{w}\left(e\right)\le w\left(e\right)$ , by the definition of $\tilde{w}$ . Therefore, the optimal weight over $\tilde{G}$ can only be equal to or smaller than the one of $G$ .

The other direction is less trivial. Take any $\tilde{S}^{*}$ and convert it to be a valid solution over the original $G$ as follows: for any $e\in\tilde{S}^{*}$ , if $e\in E\left(G\right)$ and $w\left(e\right)\le\tilde{w}\left(e\right)$ then add $e\in S^{*}$ . Otherwise, take all the edges along the shortest path connecting the endpoints of $e$ other the original graph $G$ and add them to $S^{*}$ . Note that the entire weight of that path cannot exceeds $\tilde{w}\left(e\right)$ by the definition of $\tilde{w}$ . Therefore we end up with a valid solution $S^{*}$ , that also have $w\left(S^{*}\right)\le w\left(\tilde{S}^{*}\right)$ . In conclusion, $w\left(S^{*}\right)=w\left(\tilde{S}^{*}\right)$ .

The proof above gave us a concrete polynomial-time procedure to convert any valid solution $\tilde{S}$ over $\tilde{G}$ to a valid solution $S$ over $G$ such that $w\left(S\right)\le w\left(\tilde{S}\right)$ . From that we can conclude that it is suffice to find a 2-approximation for the “easier” instance $\left(\tilde{G},\tilde{w}\right)$ and then converts it to a 2-approximation solution for the original instance $\left(G,w\right)$ , note also that the construction of $\tilde{G},\tilde{w}$ from $G,w$ can be done in polynomial time (for example use Dijkstra's algorithm for computing the shortest paths).

In other words, we can assume for free (i.e. without losing anything) that $G$ is a clique and $w$ have the triangle inequality, and design an approximation algorithm that deals only with such instances.

Putting it differently, we claim that $w\left(S\right)\le2w\left(S^{*}\right)$ , when $S^{*}$ is some optimal solution for the Steiner Tree problem for that “easier” instance.

And now we will prove that.

Let $S^{*}$ be some optimal solution for the Steiner Tree problem. It must be a tree because otherwise we have a redundant edge such that removing it will decrease the weight of the solution and keep it valid (the terminals will stay connected); in contradiction to the optimality of $S^{*}$ . Run a Depth First Search (DFS) at the root of $S^{*}$ , traverse all the nodes in the tree and return back to the root. Memorize all the nodes traversed that way (with repetitions) and denote that sequence $P$ . By the way we build $P$ , it is a cycle that touches all the vertices of $T$ (and maybe also others) and uses twice any edge of $S^{*}$ , once for the forward pass and once for the backward pass, so it has a length $k:=2\left|S^{*}\right|$ . Suppose that $P=\left(u_{1},...,u_{k}\right)$ , then we conclude that $$w\left(P\right)=\sum_{i=1}^{k-1}w\left(\left(u_{i},u_{i+1}\right)\right)=2\cdot w\left(S^{*}\right)$$

Define the following order on $T$ : for any two terminals $t_{1},t_{2}\in T$ , we say that $t_{1}$ comes before $t_{2}$ if the first appearance of $t_{1}$ in $P$ comes before the first appearance of $t_{2}$ in $P$ . Let $\left(t_{1},...,t_{\left|T\right|}\right)$ be the sequence of ordered terminals, note that it is also defines a path because $G$ is a clique, that is, $\left(t_{i},t_{i+1}\right)\in E\left(G\right)$ for any $i$ . Denote that path $\tilde{P}$ .

By the triangle inequality, for any pair $t_{i},t_{i+1}\in T$ the weighed subpath in $\tilde{P}$ , which is the weight of a single edge, is less or equal to the weighted length in $P$ (which may use more than one edge), thus $w\left(\tilde{P}\right)\le w\left(P\right)$ .

Since $\tilde{P}$ touches all the terminals in $T$ exactly once, it has no cycles, hence it is also a spanning tree over the vertices $T$ and edges of the clique. Recall that the proposed solution $S$ is a minimum spanning tree on $T$ , therefore $w\left(S\right)\le w\left(\tilde{P}\right)$ . We conclude that $$w\left(S\right)\le w\left(\tilde{P}\right)\le w\left(P\right)=2\cdot w\left(S^{*}\right)$$ as required.