在圖形中，我們研究一個Steiner 樹問題的實用性變形問題。對於一個具有長度函數的完整圖以及兩個節點的子集合R 與R'，可選擇端末節點的Steiner 樹是指一個包含R 中所有節點的Steiner 樹使得在RR' 中的所有節點都是該Steiner 樹中的端末節點。可選擇端末節點的Steiner 樹問題就是去找一個可選擇端末節點的Steiner 樹T 使得這棵樹的長度總和是最小的。在這篇
論文中，我們證明即使邊的長度被限制在1 與2 的時候，這個問題仍然是NP-complete 與MAX SNP-hard。並且，我們提供一個近似演算法來解這個問題。

　We investigate a practical variant of the well-known graph Steiner tree problem. For a complete
graph with length function and two vertex subsets R and R', a selected-leaf-terminal Steiner tree is a Steiner tree which contains all vertices in R such that all vertices in R-R' belong to the leaves of this Steiner tree. The selected-leaf-terminal Steiner tree problem is to find a selected-leaf-terminal Steiner tree T whose total lengths is minimum. In this paper, we show that the problem is both NP-complete and MAX SNP-hard when the lengths of edges are restricted to either 1 or 2. We also provide an approximation algorithm for the problem.

[1] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, "Proof verication and the hardness of approximatiion problems," Journal of the Association for Computing Machinery, vol. 45, pp. 501-555, 1998.
[2] P. Berman and V. Ramaiyer, "Improved approximations for the Steiner tree problem," Journal of Algorithms, vol. 17(3), pp. 381-408, 1994.
[3] M. Bern, "Faster exact algorithms for Steiner tree in planar networks," Networks, vol. 20, pp. 109-120, 1990.
[4] M. Bern and P. Plassmann, "The Steiner problem with edge lengths 1 and 2," Information
Processing Letters, vol. 32(4), pp. 171-176, 1989.
[5] A. Borchers and D. Z. Du, "The k-Steiner ratio in graphs," SIAM Journal on Computing,
vol. 26(3), pp. 857-869, 1997.
[6] A. Caldewll, A. 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.
[7] Y.H. Chen, C.L. Lu, and C.Y. Tang, "On the full and bottleneck full Steiner tree problems,"
in Proceedings of the 9th Annual International Conference on Computing and Combinatorics
(COCOON), LNCS 2697, pp. 122-129, 2003.
[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. B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, Upper Saddle
River, 2001.
[11] D. Z. Du, "On component-size bounded Steiner trees," Discrete Applied Mathematics, vol.60, pp. 131-140, 1995.
[12] D. Z. Du, J. M. Smith, and J. H. Rubinstein, Advance in Steiner Tree, Kluwer Academic Publishers, Dordrecht, Netherlands, 2000.
[13] L. Foulds and R. Graham, "The Steiner problem in phylogeny is NP-complete," Advances
in Applied Mathematics, vol. 3, pp. 43-49, 1982.
[14] 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.
[15] M. Garey and D. Johnson, "The rectilinear Steiner problem is NP-complete," SIAM Journal
on Applied Mathematics, vol. 32, pp. 826-834, 1977.
[16] D. Graur and W. H. Li, Fundamentals of Molecular Evolution (2nd Edition), Sinauer Publishers, Sunderland, Massachusetts, 2000.
[17] S. Hougardy and H. J. Promel, "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.
[18] F. K. Hwang, D. S. Richards, and P. Winter, "The Steiner Tree Problem," Annuals of
Discrete Mathematices 53, Elsevier Science Publishers, Amsterdam, 1992.
[19] A. B. Kahng and G. Robins, On OPtimal Interconnections for VLSI, Kluwer Publishers,
1995.
[20] 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.
[21] J. Kim and T. Warnow, Tutorial on Phylogenetic Tree Estimation, manuscript, Department of Ecology and Evolutionary Biology, Yale University, 1999.
[22] G. H. Lin and G. L. Xue, "On the terminal Steiner tree problem," Information Processing
Letters, vol. 84(2), pp. 103-107, 2002.
[23] C. L. Lu, C. Y. Tang, R. C. T. Lee, "The full Steiner tree problem in phylogeny," Theoretical Computer Science, vol. 306(1-3), pp. 55-67, 2004.
[24] C. H. Papadimitriou and M. Yannakakis, "Optimization, approximation, and complexity classes," in Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 229-234, 1988.
[25] 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.