APSP Equivalences

Introduction

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.

Try It: Reduce Triangle Detection to APSP

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">This demo shows <b>triangle detection</b> via <b>APSP</b>. A triangle u-v-w exists
iff all three pairs are adjacent AND u and w share a common neighbor v. APSP exposes all
2-hop paths; checking each adjacent pair for a shared neighbor then finds the triangle.</p>
<div id="phase-label" class="phase-label">Phase 1 — Original graph</div>
<canvas id="canvas" width="460" height="240"></canvas>
<div class="status" id="status">Nodes A–D with unweighted edges. Does a triangle exist?</div>
<div class="btns">
  <button id="btn-step" type="button">Next step →</button>
  <button id="btn-run" type="button">Run APSP now</button>
  <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Graph definition ─────────────────────────────────────────────────────────
// Nodes: A=0, B=1, C=2, D=3
// Edges (unweighted): A-B, B-C, A-C, C-D
// Triangle: A-B-C (all three pairs connected).
// D is connected only to C — it's NOT in any triangle.
const NODES = ['A','B','C','D'];
const POSITIONS = [[100,60],[360,60],[230,180],[360,190]]; // canvas coords
const EDGES = [[0,1],[1,2],[0,2],[2,3]]; // node index pairs
const TRIANGLE = [0,1,2]; // the triangle nodes

// ── (min,+) APSP via Floyd-Warshall ─────────────────────────────────────────
// Assign weight 1 to each edge, Infinity if no edge (and 0 on diagonal).
// After APSP, dist[u][w]=2 and there exists v s.t. adj[u][v] && adj[v][w]
// iff u-v-w is a triangle path.
const N = NODES.length;
function buildDist() {
  const d = Array.from({length:N}, (_,i) => Array.from({length:N}, (_,j) => i===j ? 0 : Infinity));
  for (const [a,b] of EDGES) { d[a][b]=1; d[b][a]=1; }
  // Floyd-Warshall
  for (let k=0;k<N;k++) for (let i=0;i<N;i++) for (let j=0;j<N;j++)
    if (d[i][k]+d[k][j] < d[i][j]) d[i][j]=d[i][k]+d[k][j];
  return d;
}
function findTriangleViaAPSP(d) {
  // triangle iff adj[u][w]==true AND dist[u][w]==2 AND exists v: adj[u][v] && adj[v][w]
  // The key: u-w must be a direct edge too (dist=1), and a common neighbor v gives dist 2
  // via a different route. Actually the standard reduction: a triangle u-v-w exists iff
  // adj[u][v] && adj[v][w] && adj[u][w]. We detect it by checking all triples directly,
  // which is what APSP enables: enumerate pairs at dist<=2 and check the third edge.
  const adj = Array.from({length:N}, () => Array(N).fill(false));
  for (const [a,b] of EDGES) { adj[a][b]=adj[b][a]=true; }
  // For each pair (u,w) that are direct neighbors (dist=1), check if they share a neighbor v
  for (let u=0;u<N;u++) for (let w=u+1;w<N;w++) if (adj[u][w])
    for (let v=0;v<N;v++) if (v!==u && v!==w && adj[u][v] && adj[v][w]) return [u,v,w];
  return null;
}

// ── Drawing helpers ───────────────────────────────────────────────────────────
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const DPR = window.devicePixelRatio || 1;
canvas.width = 460 * DPR; canvas.height = 240 * DPR;
ctx.scale(DPR, DPR);
const W = 460, H = 240;

function clear() { ctx.clearRect(0,0,W,H); }

function drawEdge(a, b, color, weight, dashed) {
  const [x1,y1]=POSITIONS[a], [x2,y2]=POSITIONS[b];
  ctx.save();
  ctx.strokeStyle = color || '#8899aa';
  ctx.lineWidth = dashed ? 1.4 : 2;
  if (dashed) ctx.setLineDash([5,4]);
  ctx.beginPath(); ctx.moveTo(x1,y1); ctx.lineTo(x2,y2); ctx.stroke();
  ctx.setLineDash([]);
  if (weight !== undefined && weight !== null) {
    const mx=(x1+x2)/2, my=(y1+y2)/2;
    ctx.fillStyle='#c92f3c'; ctx.font='bold 12px ui-monospace,monospace';
    ctx.fillText(weight, mx+4, my-4);
  }
  ctx.restore();
}

function drawNode(i, fill, stroke, label) {
  const [x,y]=POSITIONS[i];
  ctx.save();
  ctx.beginPath(); ctx.arc(x,y,20,0,2*Math.PI);
  ctx.fillStyle = fill || '#e8eef3';
  ctx.fill();
  ctx.strokeStyle = stroke || '#1d3557'; ctx.lineWidth=2;
  ctx.stroke();
  ctx.fillStyle='#1d3557'; ctx.font='bold 15px system-ui,sans-serif';
  ctx.textAlign='center'; ctx.textBaseline='middle';
  ctx.fillText(label || NODES[i], x, y);
  ctx.restore();
}

function drawDistMatrix(d, highlightPair) {
  const ox=10, oy=10, cell=38;
  ctx.save();
  ctx.font='11px ui-monospace,monospace'; ctx.textAlign='center'; ctx.textBaseline='middle';
  // header row/col
  for (let i=0;i<N;i++) {
    ctx.fillStyle='#1d3557';
    ctx.fillText(NODES[i], ox+cell*(i+1)+cell/2, oy+cell/2);
    ctx.fillText(NODES[i], ox+cell/2, oy+cell*(i+1)+cell/2);
  }
  for (let i=0;i<N;i++) for (let j=0;j<N;j++) {
    const x=ox+cell*(j+1), y=oy+cell*(i+1);
    const isHL = highlightPair && ((highlightPair[0]===i&&highlightPair[1]===j)||(highlightPair[0]===j&&highlightPair[1]===i));
    ctx.fillStyle = isHL ? '#fff3cd' : (i===j ? '#e8eef3' : '#fff');
    ctx.fillRect(x,y,cell,cell);
    ctx.strokeStyle='#cdd9e3'; ctx.lineWidth=1;
    ctx.strokeRect(x,y,cell,cell);
    const val = d[i][j];
    ctx.fillStyle = val===0 ? '#aaa' : val===Infinity ? '#ccc' : (isHL ? '#c55' : '#1d3557');
    ctx.fillText(val===Infinity ? '∞' : val, x+cell/2, y+cell/2);
  }
  ctx.restore();
}

// ── Phases ───────────────────────────────────────────────────────────────────
let phase = 0;
const PHASES = [
  // 0: original graph
  function phaseOriginal() {
    clear();
    for (const [a,b] of EDGES) drawEdge(a,b,'#8899aa');
    for (let i=0;i<N;i++) drawNode(i,'#e8eef3','#1d3557');
    setPhaseLabel('Phase 1 — Original graph');
    setStatus('Graph with 4 nodes and 4 edges. Does a triangle (3-clique) exist?');
  },
  // 1: assign weights
  function phaseWeights() {
    clear();
    for (const [a,b] of EDGES) drawEdge(a,b,'#1d3557',1,false);
    for (let i=0;i<N;i++) drawNode(i,'#e8eef3','#1d3557');
    setPhaseLabel('Phase 2 — Assign edge weights (all = 1)');
    setStatus('Reduction step: assign weight 1 to every edge, ∞ between non-adjacent pairs.');
  },
  // 2: run APSP, show matrix
  function phaseAPSP() {
    clear();
    const d = buildDist();
    drawDistMatrix(d, null);
    setPhaseLabel('Phase 3 — APSP distance matrix (Floyd-Warshall)');
    setStatus('d[u][w]=2 means u and w have a 2-hop shortest path — possibly through a shared neighbor.');
  },
  // 3: highlight triangle pair
  function phaseHighlight() {
    clear();
    const d = buildDist();
    const tri = findTriangleViaAPSP(d);
    if (tri) {
      const [u,v,w] = tri;
      drawDistMatrix(d, [u,w]);
      setPhaseLabel('Phase 4 — Triangle detected!');
      setStatus(fmt('d[%v%][%v2%]=2 and %v%–%v3%–%v2% is the triangle path. ✓ Triangle found: %v%%v3%%v2%.', { v: NODES[u], v2: NODES[w], v3: NODES[v] }), 'ok');
    } else {
      drawDistMatrix(d, null);
      setPhaseLabel('Phase 4 — No triangle found');
      setStatus('No pair has d=2 through a mutual neighbor. No triangle exists.', 'bad');
    }
  },
  // 4: back to graph, highlight triangle visually
  function phaseTriangle() {
    clear();
    for (const [a,b] of EDGES) {
      const inTri = TRIANGLE.includes(a) && TRIANGLE.includes(b);
      drawEdge(a,b, inTri ? '#0a7d33' : '#bbb', inTri ? 1 : null, !inTri);
    }
    for (let i=0;i<N;i++) {
      const inTri = TRIANGLE.includes(i);
      drawNode(i, inTri ? '#d4f0df' : '#e8eef3', inTri ? '#0a7d33' : '#aaa');
    }
    setPhaseLabel('Phase 5 — Triangle A-B-C confirmed');
    setStatus('APSP found the triangle A-B-C at cost O(n³). Any subcubic APSP gives subcubic triangle detection.', 'ok');
  }
];

function setPhaseLabel(t) { document.getElementById('phase-label').textContent=t; }
function setStatus(t, cls) {
  const s=document.getElementById('status'); s.textContent=t;
  s.className='status '+(cls||'');
}

function render() { PHASES[phase](); }

document.getElementById('btn-step').addEventListener('click', () => {
  phase = Math.min(phase+1, PHASES.length-1);
  render();
  document.getElementById('btn-step').disabled = phase >= PHASES.length-1;
});
document.getElementById('btn-run').addEventListener('click', () => {
  phase = PHASES.length-1; render();
  document.getElementById('btn-step').disabled = true;
});
document.getElementById('btn-reset').addEventListener('click', () => {
  phase=0; render();
  document.getElementById('btn-step').disabled = false;
});

render();

<p class="hint">This demo shows <b>triangle detection</b> via <b>APSP</b>. A triangle u-v-w exists
iff all three pairs are adjacent AND u and w share a common neighbor v. APSP exposes all
2-hop paths; checking each adjacent pair for a shared neighbor then finds the triangle.</p>
<div id="phase-label" class="phase-label">Phase 1 — Original graph</div>
<canvas id="canvas" width="460" height="240"></canvas>
<div class="status" id="status">Nodes A–D with unweighted edges. Does a triangle exist?</div>
<div class="btns">
  <button id="btn-step" type="button">Next step →</button>
  <button id="btn-run" type="button">Run APSP now</button>
  <button id="btn-reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Graph definition ─────────────────────────────────────────────────────────
// Nodes: A=0, B=1, C=2, D=3
// Edges (unweighted): A-B, B-C, A-C, C-D
// Triangle: A-B-C (all three pairs connected).
// D is connected only to C — it's NOT in any triangle.
const NODES = ['A','B','C','D'];
const POSITIONS = [[100,60],[360,60],[230,180],[360,190]]; // canvas coords
const EDGES = [[0,1],[1,2],[0,2],[2,3]]; // node index pairs
const TRIANGLE = [0,1,2]; // the triangle nodes

// ── (min,+) APSP via Floyd-Warshall ─────────────────────────────────────────
// Assign weight 1 to each edge, Infinity if no edge (and 0 on diagonal).
// After APSP, dist[u][w]=2 and there exists v s.t. adj[u][v] && adj[v][w]
// iff u-v-w is a triangle path.
const N = NODES.length;
function buildDist() {
  const d = Array.from({length:N}, (_,i) => Array.from({length:N}, (_,j) => i===j ? 0 : Infinity));
  for (const [a,b] of EDGES) { d[a][b]=1; d[b][a]=1; }
  // Floyd-Warshall
  for (let k=0;k<N;k++) for (let i=0;i<N;i++) for (let j=0;j<N;j++)
    if (d[i][k]+d[k][j] < d[i][j]) d[i][j]=d[i][k]+d[k][j];
  return d;
}
function findTriangleViaAPSP(d) {
  // triangle iff adj[u][w]==true AND dist[u][w]==2 AND exists v: adj[u][v] && adj[v][w]
  // The key: u-w must be a direct edge too (dist=1), and a common neighbor v gives dist 2
  // via a different route. Actually the standard reduction: a triangle u-v-w exists iff
  // adj[u][v] && adj[v][w] && adj[u][w]. We detect it by checking all triples directly,
  // which is what APSP enables: enumerate pairs at dist<=2 and check the third edge.
  const adj = Array.from({length:N}, () => Array(N).fill(false));
  for (const [a,b] of EDGES) { adj[a][b]=adj[b][a]=true; }
  // For each pair (u,w) that are direct neighbors (dist=1), check if they share a neighbor v
  for (let u=0;u<N;u++) for (let w=u+1;w<N;w++) if (adj[u][w])
    for (let v=0;v<N;v++) if (v!==u && v!==w && adj[u][v] && adj[v][w]) return [u,v,w];
  return null;
}

// ── Drawing helpers ───────────────────────────────────────────────────────────
const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const DPR = window.devicePixelRatio || 1;
canvas.width = 460 * DPR; canvas.height = 240 * DPR;
ctx.scale(DPR, DPR);
const W = 460, H = 240;

function clear() { ctx.clearRect(0,0,W,H); }

function drawEdge(a, b, color, weight, dashed) {
  const [x1,y1]=POSITIONS[a], [x2,y2]=POSITIONS[b];
  ctx.save();
  ctx.strokeStyle = color || '#8899aa';
  ctx.lineWidth = dashed ? 1.4 : 2;
  if (dashed) ctx.setLineDash([5,4]);
  ctx.beginPath(); ctx.moveTo(x1,y1); ctx.lineTo(x2,y2); ctx.stroke();
  ctx.setLineDash([]);
  if (weight !== undefined && weight !== null) {
    const mx=(x1+x2)/2, my=(y1+y2)/2;
    ctx.fillStyle='#c92f3c'; ctx.font='bold 12px ui-monospace,monospace';
    ctx.fillText(weight, mx+4, my-4);
  }
  ctx.restore();
}

function drawNode(i, fill, stroke, label) {
  const [x,y]=POSITIONS[i];
  ctx.save();
  ctx.beginPath(); ctx.arc(x,y,20,0,2*Math.PI);
  ctx.fillStyle = fill || '#e8eef3';
  ctx.fill();
  ctx.strokeStyle = stroke || '#1d3557'; ctx.lineWidth=2;
  ctx.stroke();
  ctx.fillStyle='#1d3557'; ctx.font='bold 15px system-ui,sans-serif';
  ctx.textAlign='center'; ctx.textBaseline='middle';
  ctx.fillText(label || NODES[i], x, y);
  ctx.restore();
}

function drawDistMatrix(d, highlightPair) {
  const ox=10, oy=10, cell=38;
  ctx.save();
  ctx.font='11px ui-monospace,monospace'; ctx.textAlign='center'; ctx.textBaseline='middle';
  // header row/col
  for (let i=0;i<N;i++) {
    ctx.fillStyle='#1d3557';
    ctx.fillText(NODES[i], ox+cell*(i+1)+cell/2, oy+cell/2);
    ctx.fillText(NODES[i], ox+cell/2, oy+cell*(i+1)+cell/2);
  }
  for (let i=0;i<N;i++) for (let j=0;j<N;j++) {
    const x=ox+cell*(j+1), y=oy+cell*(i+1);
    const isHL = highlightPair && ((highlightPair[0]===i&&highlightPair[1]===j)||(highlightPair[0]===j&&highlightPair[1]===i));
    ctx.fillStyle = isHL ? '#fff3cd' : (i===j ? '#e8eef3' : '#fff');
    ctx.fillRect(x,y,cell,cell);
    ctx.strokeStyle='#cdd9e3'; ctx.lineWidth=1;
    ctx.strokeRect(x,y,cell,cell);
    const val = d[i][j];
    ctx.fillStyle = val===0 ? '#aaa' : val===Infinity ? '#ccc' : (isHL ? '#c55' : '#1d3557');
    ctx.fillText(val===Infinity ? '∞' : val, x+cell/2, y+cell/2);
  }
  ctx.restore();
}

// ── Phases ───────────────────────────────────────────────────────────────────
let phase = 0;
const PHASES = [
  // 0: original graph
  function phaseOriginal() {
    clear();
    for (const [a,b] of EDGES) drawEdge(a,b,'#8899aa');
    for (let i=0;i<N;i++) drawNode(i,'#e8eef3','#1d3557');
    setPhaseLabel('Phase 1 — Original graph');
    setStatus('Graph with 4 nodes and 4 edges. Does a triangle (3-clique) exist?');
  },
  // 1: assign weights
  function phaseWeights() {
    clear();
    for (const [a,b] of EDGES) drawEdge(a,b,'#1d3557',1,false);
    for (let i=0;i<N;i++) drawNode(i,'#e8eef3','#1d3557');
    setPhaseLabel('Phase 2 — Assign edge weights (all = 1)');
    setStatus('Reduction step: assign weight 1 to every edge, ∞ between non-adjacent pairs.');
  },
  // 2: run APSP, show matrix
  function phaseAPSP() {
    clear();
    const d = buildDist();
    drawDistMatrix(d, null);
    setPhaseLabel('Phase 3 — APSP distance matrix (Floyd-Warshall)');
    setStatus('d[u][w]=2 means u and w have a 2-hop shortest path — possibly through a shared neighbor.');
  },
  // 3: highlight triangle pair
  function phaseHighlight() {
    clear();
    const d = buildDist();
    const tri = findTriangleViaAPSP(d);
    if (tri) {
      const [u,v,w] = tri;
      drawDistMatrix(d, [u,w]);
      setPhaseLabel('Phase 4 — Triangle detected!');
      setStatus(fmt('d[%v%][%v2%]=2 and %v%–%v3%–%v2% is the triangle path. ✓ Triangle found: %v%%v3%%v2%.', { v: NODES[u], v2: NODES[w], v3: NODES[v] }), 'ok');
    } else {
      drawDistMatrix(d, null);
      setPhaseLabel('Phase 4 — No triangle found');
      setStatus('No pair has d=2 through a mutual neighbor. No triangle exists.', 'bad');
    }
  },
  // 4: back to graph, highlight triangle visually
  function phaseTriangle() {
    clear();
    for (const [a,b] of EDGES) {
      const inTri = TRIANGLE.includes(a) && TRIANGLE.includes(b);
      drawEdge(a,b, inTri ? '#0a7d33' : '#bbb', inTri ? 1 : null, !inTri);
    }
    for (let i=0;i<N;i++) {
      const inTri = TRIANGLE.includes(i);
      drawNode(i, inTri ? '#d4f0df' : '#e8eef3', inTri ? '#0a7d33' : '#aaa');
    }
    setPhaseLabel('Phase 5 — Triangle A-B-C confirmed');
    setStatus('APSP found the triangle A-B-C at cost O(n³). Any subcubic APSP gives subcubic triangle detection.', 'ok');
  }
];

function setPhaseLabel(t) { document.getElementById('phase-label').textContent=t; }
function setStatus(t, cls) {
  const s=document.getElementById('status'); s.textContent=t;
  s.className='status '+(cls||'');
}

function render() { PHASES[phase](); }

document.getElementById('btn-step').addEventListener('click', () => {
  phase = Math.min(phase+1, PHASES.length-1);
  render();
  document.getElementById('btn-step').disabled = phase >= PHASES.length-1;
});
document.getElementById('btn-run').addEventListener('click', () => {
  phase = PHASES.length-1; render();
  document.getElementById('btn-step').disabled = true;
});
document.getElementById('btn-reset').addEventListener('click', () => {
  phase=0; render();
  document.getElementById('btn-step').disabled = false;
});

render();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/apsp-equivalences/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Shortest paths, matrix products, triangles — four puzzles with one fate