Hardness of Approximation for Shortest Path with Vector Costs

2025/10/24 by Carlson, Charlie, Makarychev, Yury, Mosenzon, Ron
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2510.21058

Abstract

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²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 / loglog 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² n), improving upon the previous Ω(log n) hardness result. Our result nearly matches the O(log² 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.

Citations

• Approximation Algorithms for ℓ_p-Shortest Path and ℓ_p-Group Steiner Tree

Related

• Approximation Schemes for the Restricted Shortest Path Problem
• Improved hardness results for unique shortest vector problem
• Hardness of Approximate Nearest Neighbor Search under L-infinity
• Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
• Approximation Algorithms for ℓ_p-Shortest Path and ℓ_p-Group Steiner Tree