[#P3144] Is there a truly subcubic algorithm for weighted APSP?

All-pairs shortest paths filling a distance matrix. — A structural graph diagram of the statement's mathematical objects.

Problem. Does there exist \(\varepsilon>0\) and an \(O(n^{3-\varepsilon})\)-time algorithm for all-pairs shortest paths in directed \(n\)-vertex graphs with integer edge weights of polynomial magnitude and no negative cycle?

1Context

Known frontier: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Open boundary: A fixed positive exponent saving remains unknown.

2Problem setup

Definition 1 (APSP). Compute the shortest-path distance for every ordered pair of vertices.

Definition 2 (truly subcubic). O(n^{3−ε}) for one fixed ε>0.

Remark 1. The standard dynamic-programming and min-plus product approaches are cubic up to lower-order improvements. The target fixes polynomially bounded weights so bit complexity is explicit.

3What counts as a solution

Give a correct truly subcubic algorithm in the stated word-RAM or bit model.
Or prove an n^{3−o(1)} lower bound in a clearly specified standard model.

1Status

Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.^[1][2]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.^[1][2] Relevance to this problem This is the dated publication status for the canonical target Is there a truly subcubic algorithm for weighted APSP?. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. The exact unresolved remainder is: A fixed positive exponent saving remains unknown. A complete resolution must meet the following acceptance conditions: - Give a correct truly subcubic algorithm in the stated word-RAM or bit model. - Or prove an n^{3−o(1)} lower bound in a clearly specified standard model. Open full record →
	Result	Supported
claim · Claim 2 The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.^[1][2] Relevance to this problem Locates the present research frontier immediately below Is there a truly subcubic algorithm for weighted APSP?. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. This leaves the following boundary unresolved: A fixed positive exponent saving remains unknown. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Unresolved remainder: A fixed positive exponent saving remains unknown.^[1][2] Relevance to this problem Documents why Is there a truly subcubic algorithm for weighted APSP? was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - truly subcubic APSP open problem 2026 - weighted all pairs shortest paths n 3 epsilon The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Unresolved remainder: A fixed positive exponent saving remains unknown. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 A fixed positive exponent saving remains unknown. Relevance to this problem Turns the remaining uncertainty in Is there a truly subcubic algorithm for weighted APSP? into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: A fixed positive exponent saving remains unknown. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - Give a correct truly subcubic algorithm in the stated word-RAM or bit model. - Or prove an n^{3−o(1)} lower bound in a clearly specified standard model. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.

Equivalent-formulation queries: truly subcubic APSP open problem 2026; weighted all pairs shortest paths n 3 epsilon
Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.
Exact unresolved remainder: A fixed positive exponent saving remains unknown.

How the 4 records connectTyped relations and evidence flow

ProblemIs there a truly subcubic algorithm for weighted APSP?

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Is VP equal to VNP?theoretical computer science
Strong Exponential Time Hypothesistheoretical computer science
Polynomial-time recovery of planted cliques below the square-root scaletheoretical computer science

How to cite

TheoremDB contributors, “Is there a truly subcubic algorithm for weighted APSP?,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/truly-subcubic-apsp

This page as plain text: truly-subcubic-apsp.md

This problem includes 4 records joined by 3 typed links, sourced from arxiv.org^[1], current as of August 1, 2026.

1References

Packet source. R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 2014. main theorem. ↗preprint · primary source · arXiv:1312.6680, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Gives a subcubic improvement by a subpolynomial factor and explains the circuit connection.Also cited at R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 2014. main theorem.Source used to assess the problem's recorded status.For Is there a truly subcubic algorithm for weighted APSP?: This is the dated publication status for the canonical target Is there a truly subcubic algorithm for weighted APSP?.Source named by the research packet.
Virginia Vassilevska Williams and Ryan Williams, “Subcubic Equivalences between Path, Matrix and Triangle Problems”. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (2010), 645-654. DOI 10.1109/FOCS.2010.67. subcubic equivalence theorems. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Shows that a breakthrough would transfer to several central weighted graph problems.Source used to assess the problem's recorded status.For Is there a truly subcubic algorithm for weighted APSP?: Shows that a breakthrough would transfer to several central weighted graph problems.

Original TheoremDB editorial statement and source synthesis; external works are used for citation only.

[#P3144] Is there a truly subcubic algorithm for weighted APSP?

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance