Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein · 2022
We study the approximability of two related problems on graphs with n nodes and m edges: n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O(n) prespecified pairs, and All Node Shortest Cycles (ANSC), where the goal is to find the shortest cycle passing through each node. Approximate n-PSP has been previously studied, mostly in the context of distance oracles. We ask the question of whether approximate n-PSP can be solved faster than by using distance oracles or All Pair Shortest Paths (APSP). ANSC has also been studied previously, but only in terms of exact algorithms, rather than approximation.We provide a thorough study of the approximability of n PSP and ANSC, providing a wide array of algorithms and conditional lower bounds that trade off between running time and approximation ratio.A highlight of our conditional lower bounds results is that for any integer k$\geq$1, under the combinatorial 4k-clique hypothesis, there is no combinatorial algorithm for unweighted undirected n-PSP with approximation ratio better than $1+1/k$ that runs in $O(m^{2-2/(k+1)}n^{1/(k+1)-\varepsilon})$ time. This nearly matches an upper bound implied by the result of Agarwal (2014).Our algorithms use a surprisingly wide range of techniques, including techniques from the girth problem, distance oracles, approximate APSP, spanners, fault-tolerant spanners, and link-cut trees.A highlight of our algorithmic results is that one can solve both n-PSP and ANSC in $O(m+n^{3/2+\in})$ time1with approximation factor $2+\varepsilon$ (and additive error that is function of $\varepsilon$), for any constant $\varepsilon\lt 0$. For n-PSP, our conditional lower bounds imply that this approximation ratio is nearly optimal for any subquadratic-time combinatorial algorithm. We further extend these algorithms for n-PSP and ANSC to obtain a time/accuracy trade-off that includes near-linear time algorithms.1$\tilde{O}$ hides sub-polynomial factors.Additionally, for ANSC, for all integers $k\geq 1$, we extend the very recent almost k-approximation algorithm for the girth problem that works in $\tilde{O}(n^{1+1/k})$ time [Kadria et al. SODA’22], and obtain an almost k-approximation algorithm for ANSC in $\tilde{O}(mn^{1/k})$ time.