Steiner樹問題是一個廣為人知且應用廣泛的領域，在不同的限制條件和有額外的要求時，往往會成為另外一個類似但不同原本的問題。今日我們的研究就屬於其中之一。對於一個完全圖G=(V,E)，V和E個別是G的點集合和邊集合，在圖G中的每一條邊，都帶有一個正實數的值，代表它的成本花費。現在我們從V中取出兩個子集合R和R’，使滿足R’包含於R包含於等於V，我們這個問題的目的在於：從圖G裡面找出一棵總成本花費最少的Steiner樹，並且使得在R中的每一個點都出現在我們所找出來的這棵Steiner樹上，其中，在R’中的每一個點，不僅要出現在這棵樹，還不能是這棵樹的葉點，意即這些在R’中的點，都要是這棵Steiner樹的內部點。在本篇論文中，我們證明了我們的問題是一個NP-complete的問題，而且當每一條邊上所帶有的正實數值，不是1就是2的時候，我們的問題也是一個MAX SNP-hard的問題。最後，我們提出一個演算法，可以在polynomial-time的時間內找到我們所要的一個近似解，並且去分析這個近似解有多靠近真正的解。

　In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V,E) with a cost function c:E->R+ and two subsets R and R' satisfying R' contained in R and R contained in or equal to V, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R' cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is both NP-complete and MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present a polynomial-time approximation algorithm for the problem.

[1] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, "Proof verification and the hardness of approximation problems," Journal of the Association for Computing Machinery, vol. 45, pp. 501--555, 1998.

[2] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamelai, and M. Protasi, Complexity and Approximation-Combinatorial Optimization Problems and Their Approximability Properties, Springer Verlag, Berlin, 1999.

[3] P. Berman and V. Ramaiyer, "Improved approximations for the Steiner tree problem," Journal of Algorithms, vol. 17(3), pp. 381--408, 1994.

[4] M. Bern, "Faster exact algorithms for Steiner tree in planar networks," Networks, vol. 20, pp. 109--120, 1990.

[5] M. Bern and P. Plassmann, "The Steiner problem with edge lengths 1 and 2," Information Processing Letters, vol. 32(4), pp. 171--176, 1989.

[6] A. Borchers and D. Z. Du, "The k-Steiner ratio in graphs," SIAM Journal on Computing, vol. 26(3), pp. 857--869, 1997.

[7] A. E. Caldwell, A. B. Kahng, S. Mantik, I. Markov, and A. Zelikovsky, "On wirelength estimations for row-based placement," in Proceedings of the 1998 International Symposium on Physical Design (ISPD), pp. 4--11.

[8] X. Cheng and D. Z. Du, Steiner Trees in Industry, Kluwer Academic Publishers, Dordrecht, Netherlands, 2001.

[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (Second Edition), MIT Press, Cambridge, 2001.

[10] D. Z. Du, "On component-size bounded Steiner trees," Discrete Applied Mathematics, vol. 60, pp. 131--140, 1995.

[11] D. Z. Du, J. M. Smith, and J. H. Rubinstein, Advance in Steiner Tree, Kluwer Academic Publishers, Dordrecht, Netherlands, 2000.

[12] L. Foulds and R. Graham, "The Steiner problem in phylogeny is NP-complete," Advances in Applied Mathematics, vol. 3, pp. 43--49, 1982.

[13] M. Garey, R. Graham, and D. Johnson, "The complexity of computing Steiner minimal trees," SIAM Journal on Applied Mathematics, vol. 32, pp. 835--859, 1977.

[14] M. Garey and D. Johnson, "The rectilinear Steiner problem is NP-complete," SIAM Journal on Applied Mathematics, vol. 32, pp. 826--834, 1977.

[15] D. Graur and W. H. Li, Fundamentals of Molecular Evolution (Second Edition), Sinauer Publishers, Sunderland, Massachusetts, 2000.

[16] S. Hougardy and H. J. Promel, "A 1.598 approximation algorithm for the Steiner tree problem in graphs," in Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 448--453, 1999.

[17] F. K. Hwang, D. S. Richards, and P. Winter, The Steiner Tree Problem, Annuals of Discrete Mathematics 53, Elsevier Science Publishers, Amsterdam, 1992.

[18] A. B. Kahng and G. Robins, On Optimal Interconnections for VLSI, Kluwer Publishers, 1995.

[19] R. Karp, "Reducibility among combinatorial problems," in R. E. Miller, J. W. Thatcher eds.: Complexity of Computer Computations, Plenum Press, New York, pp. 85--103, 1972.

[20] J. Kim and T. Warnow, "Tutorial on Phylogenetic Tree Estimation," manuscript, Department of Ecology and Evolutionary Biology, Yale University, 1999.

[21] G. H. Lin and G. L. Xue, "On the terminal Steiner tree problem," Information Processing Letters, vol. 84(2), pp. 103--107, 2002.

[22] C. L. Lu, C. Y. Tang, and R. C. T. Lee, "The full Steiner tree problem," Theoretical Computer Science, vol. 306, pp. 55--67, 2003.

[23] C. Papadimitriou and M. Yannakakis, "Optimization, approximation and complexity classes," Journal of Computer and System Science, vol. 43, pp. 770--779, 1991.

[24] G. Robins and A. Zelikovsky, "Improved Steiner tree approximation in graphs," in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 770--779, 2000.

[25] D. B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, Upper Saddle River, 2001.