The internal Steiner tree problem: Hardness and approximations

Given a graph G=(V,E)G=(V,E) with a cost function c:E→R+c:E→R+ and a vertex subset R⊂VR⊂V, an internal Steiner tree   is a Steiner tree that contains all the vertices in RR, and such that each vertex in RR must be an internal vertex. The internal Steiner tree problem   involves finding an internal Steiner tree TT whose total cost ∑(u,v)∈E(T)c(u,v)∑(u,v)∈E(T)c(u,v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2ρ+1)(2ρ+1)-approximation algorithm for solving the problem on complete graphs, where ρρ is an approximation ratio for the Steiner tree problem. Currently, the best-known ρρ is ln4+ϵ<1.39ln4+ϵ<1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 97-approximation algorithm for the problem.