The bottleneck selected‐internal and partial terminal Steiner tree problems

Given a complete graph G = ( V , E ) , a positive length function on edges, and two subsets R of V andR ′of R , the selected‐internal Steiner tree is defined to be an acyclic subgraph of G spanning all vertices in R such that no vertex inR ′is a leaf of the subgraph. The bottleneck selected‐internal Steiner tree problem is to find a selected‐internal Steiner tree T for R andR ′in G such that the length of the largest edge in T is minimized. The partial terminal Steiner tree is defined to be an acyclic subgraph of G spanning all vertices in R such that each vertex inR ′is a leaf of the subgraph. The bottleneck partial terminal Steiner tree problem is to find a partial terminal Steiner tree T for R andR ′in G such that the length of the largest edge in T is minimized. In this article, we show that the bottleneck selected‐internal Steiner tree problem is NP‐complete. We also show that if there is a ( 2 − ε ) ‐approximation algorithm, ε > 0 , for the bottleneck selected‐internal Steiner tree problem on metric graphs (i.e., a complete graph and the lengths of edges satisfy the triangle inequality), then P=NP. Then we extend to show that if there is an ( α ( | V | ) − ε ) ‐approximation algorithm, ε > 0 , for the bottleneck selected‐internal Steiner tree problem, then P=NP, where α ( | V | ) is any computable function of | V | . Moreover, we present an approximation algorithm with performance ratio of 3 for the bottleneck selected‐internal Steiner tree problem on metric graphs. Finally, we present an exact algorithm of O ( | V | 2 log | V | ) time for the bottleneck partial terminal Steiner tree problem. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 331–339 2016