APSP Equivalences

How long does it take to find the shortest path between every pair of cities in a road network? The naive answer is $O(n^{3})$: run Dijkstra from each of the n nodes, and each run costs $O(n^{2})$ on a dense graph. For decades, computer scientists chipped at that cube — shaving log factors here, exploiting structure there — but the fundamental $O(n^{3})$ wall never broke.

What they eventually discovered is more surprising than a faster algorithm: several completely different problems are secretly the same difficulty. Improving all-pairs shortest paths (APSP) to truly subcubic — say $O(n^{2.99})$ — would automatically speed up (min,+) matrix multiplication and triangle detection, and vice versa. The problems are fine-grained equivalent under reductions that preserve the polynomial exponent.

This web of equivalences, formalized by Virginia Vassilevska Williams and Ryan Williams in 2010, is one of the founding results of fine-grained complexity theory: the study of the exact running-time barriers for problems that are already known to be solvable in polynomial time.

The key idea of a fine-grained reduction is to transform one problem into another so efficiently that any speedup for the target immediately transfers back.

Here we reduce triangle detection (does the graph contain three mutually connected nodes?) to APSP. The construction assigns edge weights so that a triangle exists if and only if some pair has a shortest path of length exactly 2 through a shared neighbor. Step through the reduction below:

<p class="hint">{{hint}}</p>
<div id="phase-label" class="phase-label">{{phase1_label}}</div>
<canvas id="canvas" width="460" height="240"></canvas>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; background: #f4f6f8; border: 1px solid #cdd9e3; border-radius: 10px; width: 100%; max-width: 460px; }
.phase-label { font-size: .8rem; font-weight: 700; color: #1d3557; letter-spacing: .06em; text-transform: uppercase; margin-bottom: .3rem; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.5em; color: #1d3557; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice the core asymmetry: running APSP on the constructed graph costs the same as the original APSP instance — no extra overhead. So any algorithm faster than $O(n^{3})$ for APSP would detect triangles faster than $O(n^{3})$ too.

APSP is not believed to be NP-hard — we can solve it exactly in polynomial time. The open question is sharper: can we do it in truly subcubic time, or is $O(n^{3})$ essentially optimal?

The equivalence cluster. Vassilevska Williams and Williams (2010) proved that the following problems are subcubic equivalent — any truly subcubic algorithm for one gives a truly subcubic algorithm for all:

• APSP: compute d(u,v) for all pairs in a weighted graph.
• (min,+) matrix multiplication: compute $C[i][j] = \min_k(A[i][k] + B[k][j])$ — the "tropical" matrix product.
• Triangle detection: does a graph contain three mutually adjacent vertices?
• Graph radius: find the node minimizing the maximum distance to any other node.

Why this is hard. Each reduction is a subcubic-time construction — it turns an n-node input into an equivalent n-node input for the target. Because the construction is faster than the alleged bottleneck $O(n^{3})$, any speedup propagates back. The circular chain means that either all four admit a subcubic algorithm, or none do.

Status: open since the 1960s. The fastest known APSP algorithm for dense graphs runs in $O(n^{3} / \log n)$ time (Fredman 1976, later improved). Whether a genuinely subcubic $O(n^{3-\varepsilon})$ algorithm exists for any $\varepsilon > 0$ is one of the central open problems in algorithms research — directly analogous to how P vs NP structures the NP-complete world, but inside the polynomial hierarchy.

The (min,+) bottleneck. Because APSP reduces to (min,+) matrix multiplication and vice versa, a subcubic APSP would give subcubic (min,+) matrix multiplication. But (min,+) multiplication is conjectured to be fundamentally harder than ordinary matrix multiplication — we cannot use fast linear-algebra tricks like Strassen here.

The APSP barrier is not just a theoretical curiosity. It shows up wherever you must compute or approximate distances between all pairs of entities:

• Network routing: internet routers run distributed shortest-path protocols (OSPF, BGP). Full recomputation of all-pairs distances after a topology change costs $O(n^{3})$ — the equivalence explains why every practical system uses approximations or incremental updates instead. See also dynamic shortest paths.
• Social network analysis: "closeness centrality" and "betweenness centrality" of all nodes both reduce to APSP. For billion-node graphs, the cubic barrier forces heuristic approaches.
• Compiler optimization: data-flow analyses such as dominance and reaching definitions can be cast as shortest-path problems on control-flow graphs. The APSP wall motivates approximate or incremental methods.
• Computational biology: sequence alignment and phylogenetic distance matrices are shortest-path problems in disguise, and the APSP bound governs their scalability.
• Fine-grained complexity itself: the APSP cluster is the canonical example of a conditional lower bound — "if APSP needs $\Omega(n^3)$ time, then so does X" is now a standard proof technique, replacing ad-hoc per-problem arguments.

Understanding APSP equivalences tells algorithm designers exactly where the wall is — and why every $O(n^{2} \cdot \text{something})$ shortcut they find is meaningful.

All-pairs shortest paths looks like a workhorse routing problem. What fine-grained complexity reveals is that it sits at the center of a web of equivalences: beat APSP and you simultaneously beat (min,+) matrix multiplication, triangle detection, and graph radius. Fail on one, fail on all.

The $O(n^{3})$ wall has held since the 1960s. Not because researchers haven't tried — decades of clever algorithms have shaved polylogarithmic factors — but because the equivalences suggest that a true polynomial improvement may be as deep a question as P vs NP itself, just one level down, inside the polynomial-time world. Fine-grained complexity gives us the language to say precisely how hard "already easy" problems really are.