Hardness of Approximation for Shortest Path with Vector Costs

Abstract

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 $\hat{I}\text{c◯}(p(\log n/{\log }^2\log n{)}^{1-1/p})$ for both polynomial- and quasi-polynomial-time approximation algorithms. This nearly matches the approximation factor of $O(p(\log n/\log \log n{)}^{1-1/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<\infty$. We also present results for the case where $p$ is a function of $n$. For $p=\infty$, we establish a hardness of $\tilde{\hat{I}}\text{c◯}({\log }^{2}n)$, improving upon the previous $\tilde{\hat{I}}\text{c◯}(\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.

33 pages, 1 figure, to be published in SODA 2026