The Steiner tree problem is to find a tree in a connected undirected distance graph G = (V, E, d) which spans a given set S V. The minimum Steiner tree for G and S is a tree which spans S with a minimum total distance on its edges. In this paper we consider a special case of the Steiner tree problem in graphs. For this problem we assume that the underlying graph G does not have any direct edge between the vertices in S V. The problem is to find a tree in G which spans the vertices in S and uses minimum number of vertices in V - S.
