Hardness and Approximation for the Star \(\beta \) -Hub Routing Cost Problem in  \(\varDelta _\beta \) -Metric Graphs

Minimizing transportation costs through the design of a hub-and-spoke network is a crucial concern in hub location problems (HLP). Within the realm of HLP, the \(\varDelta _\beta \) -Star p -Hub Routing Cost Problem ( \(\varDelta _\beta \) -SpHRP) represents an open problem stemming from the Star p -Hub Routing Cost Problem (SpHRP) discussed in a publication by [Yeh et al., Theoretical Computer Science, 2022]. The \(\varDelta _\beta \) -SpHRP deals with a specific vertex c, a positive integer p, and a \(\varDelta _\beta \) -metric graph denoted as G, which is an undirected, complete, and weighted graph adhering to the \(\beta \) -triangle inequality. The objective is to identify a spanning tree T that satisfies the following conditions: it is rooted at c, contains exactly p hubs adjacent to c, and assigns each remaining vertex to a hub while minimizing the routing cost of T. This paper expands the input instances from metric graphs to \(\varDelta _{\beta }\) -metric graphs. Our research demonstrates that SpHRP is NP-hard for any \(\beta >\frac{1}{2}\) , indicating that SpHRP remains NP-hard for various subclasses of metric graphs. For approximation algorithms, we introduce two approaches that improve upon previous results, particularly when \(\beta \) is close to \(\frac{1}{2}\) .