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

Nick Fischer · 2026

Read Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses by Nick Fischer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-27736.txt.

Introduction

Fischer proves three hardness guesses for shortest paths are one and the same. The APSP hypothesis says all-pairs paths need near-cubic time. Stronger forms cover small weights and unweighted graphs. A universe reduction links all three claims. The proof assumes fast matrix products and a combinatorics premise. Many side problems gain matching lower bounds. Node-weighted paths and bottleneck paths are among them.

Catalog record

CREATORNick Fischer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43931
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.27736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses Nick Fischer Abstract The APSP Hypothesis states that the All-Pairs Shortest Paths (APSP) problem requires time n 3 − o ⁡ ( 1 ) 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 \omega=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. 1 Introduction The overarching goal of fine-grained complexity is to pinpoint the exact complexity of polynomial-time problems conditioned on a small set of believable core assumptions. Over the years, three such hypotheses have crystallized: SETH [ ImpagliazzoP01 , ImpagliazzoPZ01 ] , the 3SUM Hypothesis [ GajentaanO95 ] , and the APSP Hypothesis [ VassilevskaW18 ] . In this modern view, a problem is considered “closed” when we can establish both an n^{c+o(1)} upper bound and a matching n^{c-o(1)} lower bound conditioned on one of these three assumptions. The framework has become a major success story, resolving the exact complexity of numerous important problems in P. Yet many other central problems currently resist lower bounds under these “primary” assumptions. A common workaround is to resort to stronger “secondary” hypotheses (such as Quantified SETH [ BringmannC20 ] , Strong 3SUM [ AmirCLL14 ] , and Minimum-Weight k -Clique [ AbboudVW14 ] , to name a few). Often, these secondary assumptions postulate that the primary problems are hard even on restricted instances (as is the case for Strong 3SUM and Minimum-Weight k -Clique). On the one hand, these variants are extremely helpful: they are typically easier to reduce from, and we still regard them as “morally equivalent” to their primary counterparts. On the other hand, these secondary hypotheses are, of course, less convincing. Unlike the three core assumptions, they often lack decades of effort dedicated to breaking them. As a result, while conditional lower bounds based on secondary hypotheses are still seen as strong hardness barriers, they must be taken with a grain of salt. Another drawback is conceptual: With every new hypothesis we move a little further away from the dream goal of classifying the complexity in P conditioned on a small set of core assumptions. This naturally raises an important quest in fine-grained complexity: to relate our primary and secondary hypotheses to each other, ideally reducing all of our secondary assumptions back to the original three primary ones. Unfortunately, so far there has been little progress in this direction. In this paper, we take one of the first significant steps. We consider the APSP Hypothesis and two of its prominent secondary variants, and prove that these three hypotheses are not only morally related but are in fact equivalent , modulo the assumption \omega=2 and some plausible additive combinatorics assumption. Along the way we derive strong APSP-based lower bounds—many of which resolve long-standing open problems. 1.1 All-Pairs Shortest Paths The All-Pairs Shortest Paths (APSP) problem is to compute all pairs of distances in an edge-weighted graph. Few other graph problems have sparked as much attention as the quest for fast algorithms for APSP. Yet in the 60 years since the classic O(n^{3}) -time Floyd–Warshall algorithm [ Floyd62 , Warshall62 ] , a long line of improvements [ Floyd62 , Warshall62 , Fredman76 , Dobosiewicz90 , Takaoka92 , Han04 , Takaoka04 , Zwick04 , Takaoka05 , Chan08 , Han08 , Chan10 , HanT16 ] only shaved off polylogarithmic factors, culminating in Williams’ [ Williams18 , ChanW21 ] current best bound of n^{3}/2^{O(\sqrt{\log n})} . Whether this can be improved to truly subcubic time O(n^{2.99}) , say, remains a major open question. With the rise of fine-grained complexity in the 2010s, this barrier was reinterpreted as a hardness assumption [ VassilevskaW18 ] , which has since evolved into one of the three primary hypotheses of the area: {hypothesis} [APSP] For every constant \epsilon>0 there is a constant c such that APSP on graphs with weights in \{0,\dots,n^{c}\} cannot be solved in time O(n^{3-\epsilon}) . 1 1 1 Unless stated otherwise we assume that graphs are directed. However, it is known that Section 1.1 holds equivalently for directed and undirected graphs [ VassilevskaW18 ] . 2 2 2 Here and throughout we only consider nonnegative weights, although it is equivalent to assume weights in \{-n^{c},\dots,n^{c}\} . Indeed, with Johnson’s trick [ Johnson77 ] , it suffices to solve a Single-Source Shortest Paths instance (e.g., using [ BernsteinNW22 ] ) to compute a potential function that transforms negative weights into nonnegative integers. 3 3 3 In many papers the dependence between \epsilon and c is not made explicit. In particular, another reasonable formulation of the hypothesis is to change the quantifiers, i.e., to postulate that there is some absolute constant c such that for all \epsilon>0 APSP on graphs with weights \{0,\dots,n^{c}\} cannot be solved in time O(n^{3-\epsilon}) . We consider the weaker Section 1.1 throughout (so that our results take the strongest form). In fact, one could weaken the hypothesis further to weights bounded by \exp(n^{o(1)}) and our results would still apply. The APSP Hypothesis forms the basis for fine-grained lower bounds for many important problems, including natural graph and matrix problems [ VassilevskaW18 , BackursDT16 , HenzingerLNV17 , LincolnVW18 , AbboudGV23 , KociumakaP23 ] , tree edit distance [ BringmannGMW18 , NoglerPSVXY25 ] , triangle listing [ VassilevskaX20b ] , as well as approximate [ AbboudBKZ22 , ChanX24 ] and dynamic problems [ AbboudV14 , VassilevskaX20b ] , even in planar graphs [ AbboudD16 ] . In fact, many such problems have been shown not merely to be APSP-hard, but APSP-equivalent. The two secondary hypotheses we consider can both be seen as strengthenings of the APSP hypothesis concerning graphs with small weights and no weights. (In fact, the restriction to small-weight instances is a common secondary pattern, see e.g. the Strong 3SUM [ AmirCLL14 ] , Strong Zero Triangle [ AbboudBKZ22 ] and Strong Min-Plus Convolution [ ChanVX21 ] Hypotheses.) Specifically, the fastest-known algorithm for graphs with weights in \{0,\dots,u\} runs in time \tilde{O}(n^{\omega}u) [ AlonGM97 ] , where 2\leq\omega<2.372 is the matrix multiplication exponent [ AlmanDVXXZ25 ] . Thus, for a universe of size u=n^{3-\omega} the fastest-known algorithms take cubic time n^{3-o(1)} , and it is plausible to hypothesize that this is best-possible. Chan, Vassilevska W., and Xu [ ChanVX23 ] first proposed this as the following hardness assumption, which has become the basis for several conditional lower bounds [ ChanVX23 , HorowiczK25 ] : {hypothesis} [Strong APSP] For every constant \epsilon>0 , APSP on graphs with weights in \{0,\dots,n^{3-\omega}\} cannot be solved in time O(n^{3-\epsilon}) . Conversely, APSP on graphs with weights smaller than n^{3-\omega} and therefore also unweighted directed graphs is known to be in subcubic time. The fastest-known algorithm for

Read the complete text