給一個任意的無向完全圖，本篇論文所解決的問題是星狀p中繼站最小路由成本問題，我們要找出一棵有根、深度兩層、而根與p個點相鄰的樹，這棵樹所有點到點之間的距離加總必須為最小。我們利用Exact Cover by 3-Sets Problem證明了星狀p中繼站最小路由問題是NP難題，因為NP難題我們無法在多項式時間內求得最佳解，所以我們提出了一個時間複雜度在多項式時間O(n^2)內的4倍近似演算法。

Given a metric graph G = (V,E,w), a center c ∈ V , and an integer p, we discuss the Star p-Hub Routing Cost Problem in this paper. We want obtain a depth-2 tree which has a root and root is adjacent to p vertices called hubs. We call that this tree is a star p-hub tree and let the sum of distance in tree between all pairs of vertices be minimum. We prove the Star p-Hub Routing Cost Problem is NP-hard by reducing the Exact Cover by 3-Sets Problem to
it. The Exact Cover by 3-Sets Problem is a variation of set cover problem and known NP-hard problem. After proving the Star p-Hub Routing Cost Problem is NP-hard, we present a 4-approximation algorithm running in polynomial time O(n^2) for the Star p-Hub Routing Cost Problem.

[1] R. Campos and M. Ricardo, “A fast algorithm for computing minimum routing cost spanning trees,” Computer Networks, vol. 52, no. 17, pp. 3229–3247, 2008.
[2] L. H. Chen, D. W. Cheng, S. Y. Hsieh, L. J. Hung, C. W. Lee, and B. Y. Wu, “Approximation algorithms for single allocation k-hub center problem,” In Proceedings of the 33rd Workshop on Combinatorial Mathematics and Computation Theory (CMCT 2016), pp. 13–18, 2016.
[3] L. H. Chen, D. W. Cheng, S. Y. Hsieh, L. J. Hung, C. W. Lee, and B. Y. Wu, “Approximation algorithms for the star k-hub center problem in metric graphs,” In International Computing and Combinatorics Conference, pp. 222–234. Springer, Cham, August 2016.
[4] L. H. Chen, D. W. Cheng, S. Y. Hsieh, L. J. Hung, C. W. Lee, and B. Y. Wu, “On the complexity of the star p-hub center problem with parameterized triangle inequality,” In International Conference on Algorithms and Complexity, pp. 152–163. Springer, Cham, May 2017.
[5] L. H. Chen, S. Y. Hsieh, L. J. Hung, and R. Klasing, “The Approximability of the p-hub Center Problem with Parameterized Triangle Inequality,” In International
Computing and Combinatorics Conference, pp. 112–123. Springer, Cham, August 2017.
[6] L. H. Chen, D. W. Cheng, S. Y. Hsieh, L. J. Hung, R. Klasing, C. W. Lee, and B. Y. Wu, “Approximability and inapproximability of the star p-hub center problem with parameterized triangle inequality,” Journal of Computer and System Sciences, vol. 92, pp. 92–112, 2018.
[7] R. Dionne and M. Florian, “Exact and approximate algorithms for optimal network design,” Networks, vol. 9, no. 1, pp. 37–59, 1979.
[8] M. Fischetti, G. Lancia, and P. Serafini, “Exact algorithms for minimum routing cost trees,” Networks, vol. 39, no. 3, pp 161–173, 2002.
[9] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco, 1979.
[10] T. C. Hu, “Optimum communication spanning trees,” SIAM Journal on Computing, vol. 3, no. 3, pp. 188–195, 1974.
[11] A. Hochuli, S. Holzer, and R. Wattenhofer, “Distributed approximation of minimum routing cost trees,” In International Colloquium on Structural Information and Communication Complexity, pp. 121–136. Springer, Cham, July 2014.
[12] W. C. Lin and B. Y.Wu, “A 2-approximation algorithm for the clustered minimum routing cost tree problem,” In Intelligent Systems and Applications: Proceedings
of the International Computer Symposium (ICS) Held at Taichung, Taiwan, December 12–14, 2014, vol. 274, pp. 3, IOS Press, April 2015.
[13] M. E. O’Kelly and H. J. Miller, “The hub network design problem: a review and synthesis,” Journal of Transport Geography, vol. 2, no. 1, pp. 31–40, 1994.
[14] K. R. U. K. Reddy, “A survey of the all-pairs shortest paths problem and its variants in graphs,” Acta Universitatis Sapientiae, Informatica, vol. 8, no. 1, pp.
16–40, 2016.
[15] B. Y. Wu, K. M. Chao, and C. Y. Tang, “Approximation algorithms for some optimum communication spanning tree problems,” Discrete Applied Mathematics, vol. 102, no. 3, pp. 245–266, 2000.
[16] B. Y. Wu, G. Lancia, V. Bafna, K. M. Chao, R. Ravi, and C. Y. Tang, “A polynomial-time approximation scheme for minimum routing cost spanning trees” SIAM Journal on Computing, vol. 29, no. 3, pp. 761–778, 2000.
[17] H. Yaman and S. Elloumi, “Star p-hub center problem and star p-hub median problem with bounded path lengths,” Computers & Operations Research, vol. 39, no. 11, pp. 2725–2732, 2012.