Bottleneck Steiner tree with bounded number of Steiner vertices ?
Given a complete graph G=(V,E) G = ( V , E ) , where each vertex is labeled either terminal or Steiner, a distance function (i.e., a metric) d:E?R+ d : E ? R + , and a positive integer k, we study the problem of finding a Steiner tree T spanning all terminals and at most k  Steiner vertices, such that the length of the longest edge is minimized. We first show that this problem is NP-hard and cannot be approximated within a factor of 2?? 2 ? ? , for any ?>0 ? > 0 , unless P=NP P = NP . Then, we present a polynomial-time 2-approximation algorithm for this problem.
bottleneck steiner tree np-hardness approximation algorithms