New Approximation Algorithms and Reductions for n-Pairs Shortest Paths and All-Nodes Shortest Cycles

In this paper, we focus on two related problems, the n-Pairs Shortest Paths (n-PSP) problem and the All-Nodes Shortest Cycles (ANSC) problem. In the n-PSP problem, given a graph G with n vertices and m edges, as well as a set P ⊆ V × V consisting of at most n pairs of vertices, our objective is to estimate the distances between each pair (u,v ) in P. In the ANSC problem, the objective is to find for each node the shortest cycle that includes that particular node. In both problems, we present new algorithms and reductions that enhance the existing solutions in terms of both time complexity and approximation factor.