Hardness of Approximation for Shortest Path with Vector Costs

We obtain hardness of approximation results for the ${\mathrm{\ell }}_p$-Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p\in [2,\mathrm{\infty })$, we show a hardness of $\mathrm{\Omega }(p(\log n\mathrm{/}{\log }^2\log n{)}^{1-1\mathrm{/}p})$ for both polynomial- and quasi-polynomial-time approximation algorithms. This nearly matches the approximation factor of $O(p(\log n\mathrm{/}\log \log n{)}^{1-1\mathrm{/}p})$ 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<\mathrm{\infty }$. We also present results for the case where $p$ is a function of $n$. For $p=\mathrm{\infty }$, we establish a hardness of $\tilde{\mathrm{\Omega }}({\log }^{2}n)$, improving upon the previous $\tilde{\mathrm{\Omega }}(\log n)$ hardness result. Our result nearly matches the $O({\log }^{2}n)$ approximation guarantee of the quasi-polynomial-time algorithm by Li, Xu, and Zhang (ICALP 2025). Finally, we present asymptotic bounds on higher-order Bell numbers, which might be of independent interest.