In the MINIMUM STEINER TREE problem, the input consists of: a complete graph G = (V, E) wi...

In the MINIMUM STEINER TREE problem, the input consists of: a complete graph G = (V, E) with distances duv between all pairs of nodes; and a distinguished set of terminal nodes V' ⊆ V. The goal is to find a minimum-cost tree that includes the vertices V'. This tree may or may not include nodes in V –V'.

Suppose the distances in the input are a metric (recall the definition on page 279). Show that an efficient ratio-2 approximation algorithm for MINIMUM STEINER TREE can be obtained by ignoring the nonterminal nodes and simply returning the minimum spanning tree on V'. (Hint: Recall our approximation algorithm for the TSP.)