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 $Ω(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Ω(\log^2 n)$, improving upon the previous $\tildeΩ(\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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.