The relationship among some variables of Steiner tree problem

摘要

Given a weighted complete graph G = (V, E; w) and a subset R⊆V, the Steiner tree problem (STP) is to find a minimum sub-tree of G interconnecting R. In this paper, we consider the relationship among the following 4 variables of STP: terminal Steiner tree problem (TSTP), partial-terminal Steiner tree problem (PTSTP), internal Steiner tree problem (ISTP) and selected-internal Steiner tree problem (SISTP). Firstly, we show that if SISTP has an approximation problem with approximation ratio, then ISTP also has an approximation algorithm with the same ratio. Then, we prove that the same result holds between PTSTP and TSTP.