On the Internal Steiner Tree Problem.

Given a complete graph G = (V,E)with a cost function c : E →ℝ +  and a vertex subset R ⊂ V, an internal Steiner tree is a Steiner tree which contains all vertices in R such that each vertex in R is restricted to be an internal vertex. The internal Steiner tree problem is to find an internal Steiner tree T whose total costs ∑ (u,v) ∈ E(T)c(u,v) is minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present an approximation algorithm with approximation ratio 2ρ + 1 for the problem, where ρ is the best known approximation ratio for the Steiner tree problem. [ABSTRACT FROM AUTHOR]