Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time

Question

I'm working on a project centered around the All-Pairs Shortest Paths (APSP) problem. Common algorithms to APSP (Floyd-Warshall, Bellman-Ford, Johnson's) work with the standard definition of the problem where we are tasked to output the shortest paths between all nodes in a given directed input graph. We work in the adjacency model for graphs and assume an APSP instance is represented by its weight matrix $W$ s.t. if $w$ is the weight function for our input graph $G=(V,E)$, we have that $W[ij]=w(i,j)$ if there is an edge $(i,j)$ and $W[ij]=\infty$ otherwise. For a graph over $n$ nodes we can solve APSP by outputting $n$ shortest path trees or by outputting a successor matrix. A shortest path tree $T$ is a rooted tree and sub-graph of $G$ such that the paths from the root of $T$ to any other nodes in $V$ are exactly the shortest paths in $G$. A successor matrix $S$ is defined s.t. $S[ij]=k$ iff $k$ is the next node on the shortest path from $i$ to $j$.

In the field of fine-grained complexity where I'm doing my project it is common to work with a version of the problem where we are only tasked to output the shortest distances between all nodes in a graph, see e.g., this excellent overview. This way we can solve APSP by repeated use of the distance product of the weight matrix. We output these distances as a distance matrix $D$ s.t. $D[ij]$ is the length of the shortest path from $i$ to $j$ in $G$.

We work under the conjecture that no $O(n^{3-\epsilon})$ time algorithm exists, for $\epsilon>0$, for APSP and this conjecture seems reasonable for both versions of the problem.

My problem is that I can't find a good source that dives deep into the distinction between these two versions of the problem and most of the works I've read seem to work with their preferred version of the problem without explaining why it is fine to just work with e.g. the distance version of APSP.

The paths version of the problem seems harder than the distance version of the problem; most algorithms for computing the paths between all nodes already keep track of all shorstest distances during their run. Computing the distance matrix from the successor matrix in sub-cubic, i.e. $O(n^{3-\epsilon})$, time should not be too hard. The other direction is not obvious to me at all.

From the facts that the problems have the same common hardness conjecture, and how casually some authors handle the differences, I feel like these two problems should be sub-cubic equivalent: a $O(n^{3-\epsilon})$ time algorithm for one should imply a $O(n^{3-\epsilon})$ time algorithm for the other.

My questions:

1. Does anyone know of a good discussion they could point me to that clarifies the relationship between these two versions of the problem?

2. Is there a sub-cubic time algorithm that solves the paths version of APSP on the condition that we are provided with the distance matrix as input?

Answer 1

1. The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP over the class of three-layered input graphs, but I believe the ideas in this paper and its references should also help in the fully general case.

2. This is not exactly the same as your question, but it follows from this classic paper in fine-grained complexity that there is a subcubic algorithm for distance APSP iff there is a subcubic algorithm for path APSP. For example, this paper proves that there is a subcubic algorithm that solves path APSP iff there is a subcubic algorithm that verifies a proposed solution to path APSP. Verifying a solution to path APSP is trivial if we can efficiently compute the distance matrix.