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(n2) for the Star p-Hub Routing Cost Problem.