Hardness of Approximation for Shortest Path with Vector Costs

We obtain hardness of approximation results for the ℓp-Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer p ∈ [2, ∞), 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 < ∞. We also present results for the case where p is a function of n.

For p = ∞, we establish a hardness of Ω(log 2 n), improving upon the previous Ω(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.