Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses

The APSP Hypothesis states that the All-Pairs Shortest Paths (APSP) problem requires time n 3-o(1) on graphs with polynomially bounded integer edge weights. Two increasingly stronger assumptions are the Strong APSP Hypothesis and the Directed Unweighted APSP Hypothesis, which state that the fastest-known APSP algorithms on graphs with small weights and unweighted graphs, respectively, are best-possible. In this paper, we design an efficient universe reduction for APSP, which proves that these three hypotheses are, in fact, equivalent, conditioned on ω = 2 and a plausible additive combinatorics assumption.

Along the way, we resolve the fine-grained complexity of many long-standing graph and matrix problems with "intermediate" complexity such as Node-Weighted APSP, All-Pairs Bottleneck Paths, Monotone Min-Plus Product in certain settings, and many others, by designing matching APSP-based lower bounds.