Hardness of Approximation for Shortest Path with Vector Costs

We obtain hardness of approximation results for the \(\ell_p\)-Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer \(p \in [2,\infty)\), we show a hardness of \(\Omega\left( p(\log n / \log^2 \log n)^{1 - 1/p} \right)\) for both polynomial- and quasi-polynomial-time approximation algorithms. This nearly matches the approximation factor of \(O\left( p(\log n / \log \log n)^{1 - 1/p} \right)\) achieved by a quasi-polynomial-time algorithm of Makarychev, Ovsiankin, and Tani (ICALP 2025). No hardness of approximation results were previously known for any \(p \lt \infty\). We also present results for the case where \(p\) is a function of \(n\).