# The bottleneck selected-internal and partial terminal Steiner tree problems

Research paper by **Yen Hung Chen**

Indexed on: **20 Oct '16**Published on: **19 Oct '16**Published in: **Networks**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

#### Abstract

Given a complete graph G = ( V , E ) , a positive length function on edges, and two subsets R of V and R ′ 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 in R ′ is a leaf of the subgraph. The bottleneck selected-internal Steiner tree problem is to find a selected-internal Steiner tree T for R and R ′ 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 in R ′ is a leaf of the subgraph. The bottleneck partial terminal Steiner tree problem is to find a partial terminal Steiner tree T for R and R ′ 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, 2016