A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths

Marek Chrobak; Sunny Atalig

REVIEW 3 major objections 2 minor 1 references

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths

T0 review · 3 major / 2 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This note claims that a recent $\tilde{O}(m\sqrt n)$ algorithm for single-source shortest paths actually takes $\Omega(mn)$ time on a constructed weighted graph, refuting the published analysis.

desk verdict The refutation claim is plausible and potentially important, but the manuscript is unreadable mojibake, so the counterexample cannot be checked and the paper is not reviewable as submitted. read the letter →

arxiv 2508.04872 v1 pith:WRN24UNY submitted 2025-08-06 cs.DS

Sunny Atalig , Marek Chrobak This is my paper · ORCID

classification cs.DS MSC 68Q2505C8568R1068W40

keywords single-sourceshortestpathsSSSPBellman-Fordworst-caseanalysiscounterexamplegraphalgorithmsamortizedlowerbound

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The note targets a recent single-source shortest-path algorithm that claims to break the classic Bellman-Ford bound with a running time of $\tilde{O}(m\sqrt n)$. Its thesis is that the published analysis is wrong: the authors construct a weighted graph on which the algorithm, run as specified, takes $\Omega(mn)$ time. If the construction faithfully matches the algorithm, the claimed upper bound is false and the algorithm's worst case is no better than Bellman-Ford's $O(mn)$. The result matters because a genuinely faster generic SSSP algorithm would be a real algorithmic advance, and this note says that particular proposal is not it.

What carries the argument

The counterexample graph, together with a formalization of the algorithm that fixes the vertex-extraction order and edge-relaxation sequence. The graph is laid out so that, under that order, many edges are rescanned over and over, producing $\Omega(mn)$ relaxations and breaking the counting argument behind the claimed bound.

What would settle it

Implement the algorithm from the original paper and run it on the graph constructed here, counting edge relaxations. A count of $o(mn)$ — for instance $O(m\sqrt n)$ — on that graph would falsify the refutation; a count of $\Omega(mn)$ confirms the claimed upper bound is false. Also compare the note's formalization line-by-line with the original pseudocode.

Watch

Extended reading notes

Core claim

The central claim is a refutation by counterexample. The authors say that the algorithm's analysis is incorrect and exhibit an explicit weighted graph on which the algorithm performs $\Omega(mn)$ work. The point is not that the amortized bound is merely loose but that the algorithm can be forced into repeated edge relaxations at the scale of Bellman-Ford.

Load-bearing premise

The graph must faithfully execute the original algorithm as published, including its order of choosing vertices and resolving ties; if the formalization deviates, the $\Omega(mn)$ run is on a strawman. The garbled formalization section in the supplied copy makes this the point to verify.

Editorial extensions

If this is right

The proposed algorithm's published $\tilde{O}(m\sqrt n)$ worst-case bound is false; on the constructed instance its runtime is $\Omega(mn)$.
The analysis in the paper being refuted has a concrete error: its amortized count misses the repeated relaxations forced by this graph.
Whether any algorithm can solve general SSSP in $o(mn)$ time remains open; this particular claimed improvement is ruled out.
Researchers who use or extend the algorithm must check whether changes to extraction order or tie-breaking avoid the counterexample.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The refutation is specific to the algorithm as written; a different priority rule or data structure might still evade the lower-bound instance, so the note is not a general impossibility result for faster SSSP.
Because the supplied copy garbles the section that formalizes the algorithm, the counterexample's validity rests on whether the authors' transcription matches the published pseudocode; that is the first check a reader should make.
A useful extension would run other near-Bellman-Ford SSSP algorithms on the same graph family; any that also show $\Omega(mn)$ behavior would suggest a structural obstacle rather than a proof defect.
The counterexample likely exploits adversarial extraction order, so future amortized SSSP proofs should include explicit worst-case ordering analysis.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the abstract makes a claim that would matter—that Elmasry's recent Õ(m√n) SSSP algorithm is wrong, with a concrete Ω(mn) counterexample—but the manuscript you sent me is unreadable. The full text is mojibake from start to finish, and it even contains an unrelated arXiv identifier (2508.04874v1, eess.SY). I can only judge the abstract, not the construction, the proof, or the transcription of Elmasry's algorithm. So this is not a case where I can say the refutation works; it's a case where the evidence is inaccessible.

What is genuinely new, if the abstract is accurate: a fresh adversarial graph for Elmasry's algorithm, rather than a rehash of prior criticisms. A counterexample is the right way to kill an upper-bound proof, and there's no circularity or parameter fitting on display. The authors are also attacking an external published algorithm, so the stakes are real: if the example is faithful to Elmasry's pseudocode, it restores the Bellman-Ford Ω(mn) barrier for that approach.

The soft spot is not subtle. A counterexample-based refutation is only as strong as the fidelity of the simulation. Differences in relaxation order, tie-breaking, priority-queue behavior, or threshold rules can make the lower bound apply to a strawman. The abstract alone can't establish that fidelity. No code, no original pseudocode side-by-side, no step-by-step execution trace is provided. And the body is so corrupted that I can't even attempt to reverse-engineer the model. That's not a claim of bad faith; it's a claim that the artifact is not reviewable.

Who is this for? People working on single-source shortest paths and on the credibility of published near-linear bounds. If the counterexample checks out, they'll want to know. But as it stands, nobody should cite this or use it to retract Elmasry's result.

My recommendation: desk reject this copy, with an invitation to resubmit a clean, readable paper. At minimum, the authors need to include an exact transcription of Elmasry's algorithm, the construction of the graph, and the runtime accounting. Ideally, they'd include code or a verifiable execution trace. Then it deserves a serious referee. In its current form, it doesn't.

Referee Report

3 major / 2 minor

Summary. The note claims to refute Amr Elmasry's recent SSSP algorithm, which is asserted to run in Õ(m√n), by giving a weighted graph on which the algorithm runs in Ω(mn). The abstract is clear and the claim is concrete. However, the supplied full text is almost entirely unreadable mojibake, and it contains an unrelated arXiv identifier (arXiv:2508.04874v1 [eess.SY]). No graph construction, no formalization of Elmasry's algorithm, no relaxation-order/tie-breaking specification, and no runtime accounting are accessible. The central claim therefore cannot be checked from this manuscript.

Significance. If the Ω(mn) construction were presented and proved, it would be a significant result: it would refute a published Õ(m√n) bound and identify a concrete flaw in Elmasry's analysis. That potential significance is real, but the current manuscript provides no inspectable evidence. There is no machine-checked proof, no executable counterexample, no readable pseudocode, and no line-by-line comparison to the original algorithm. On the submitted text alone, the claim is unsupported.

major comments (3)

[Full text (entire body)] The body of the paper is unreadable character corruption. The reader cannot inspect the formalization of Elmasry's algorithm, the construction of the weighted graph, the claimed Ω(mn) lower-bound argument, or any runtime accounting. These are load-bearing elements of a counterexample refutation. Without a readable proof, the abstract's claim is not verifiable.
[Full text, near 'arXiv:2508.04874v1 [eess.SY] 6 Aug 2025'] The manuscript contains an unrelated arXiv identifier from a different field (eess.SY). This indicates that the submitted text is contaminated or incorrectly assembled. It undermines confidence that the surrounding text is the intended paper and prevents the reviewer from treating any fragment as reliable.
[Abstract vs. missing algorithm specification] The refutation depends on faithfully implementing Elmasry's algorithm exactly, including relaxation order, tie-breaking, and priority-queue behavior. The manuscript provides no pseudocode, no code, and no comparison with the original paper. Without this, any Ω(mn) example might apply to a strawman rather than to the published algorithm. This gap is not a presentation nit; it is the core of a counterexample-based refutation.

minor comments (2)

[General presentation] No section headings, equations, or figures are readable in the supplied text, making even a partial technical review impossible. The paper should be resubmitted in a readable encoding with proper mathematical typesetting.
[References] The only reference mentioned is the target paper by Elmasry, but no bibliographic details or page/algorithm-number citations are recoverable. A revision must cite the exact algorithm and step numbers being refuted.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity identified: the refutation targets an external algorithm and no fitted input, self-referential derivation, or self-citation chain is evident.

full rationale

The paper's claim is a counterexample-based refutation of Elmasry's published algorithm: the abstract states that the authors "show that his analysis is incorrect, by providing an example of a weighted graph on which the running time of his algorithm is Ω(mn)." This is an attack on an external, independently published algorithm and its analysis, not a derivation whose conclusion is presupposed by its own definitions or fitted parameters. The supplied full text is largely unreadable mojibake, and it even contains an unrelated arXiv identifier (2508.04874v1, eess.SY), so no specific equation, definition, or cited theorem can be inspected. Under the hard rules, circularity may only be claimed when the paper itself can be quoted to exhibit a reduction of a claimed result to its inputs; no such exhibited reduction is possible from this artifact. The concern that the example may not faithfully implement Elmasry's algorithm as published is a correctness/verifiability risk, not a circularity concern: a strawman counterexample would be a false or unverified claim, not a self-referential derivation. There is no fitted parameter renamed as a prediction, no self-citation invoked to force a choice, and no known result merely renamed. Accordingly, the appropriate finding is no significant circularity, score 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No data fitting or invented entities are involved; the result is an adversarial construction. The critical unpaid input is the paper's interpretation and transcription of Elmasry's algorithm.

assumptions (3)

domain assumption The runtime lower bound is measured on a faithful implementation of Elmasry's algorithm, including its priority-queue semantics, tie-breaking, and edge relaxation order.
The counterexample only refutes the published algorithm if the simulation matches the algorithm exactly. This is the central modeling assumption of the note.
domain assumption Elmasry's original algorithm is correctly transcribed into the notation used in the note.
Any transcription error would make the Ω(mn) example irrelevant to the claimed refutation.
standard math The standard RAM/pointer-machine cost model is used for priority-queue operations.
Complexity bounds assume unit-cost comparisons and queue operations; an unusual nonstandard operation model would change the runtime accounting.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths." pith.science (2026). https://pith.science/paper/WRN24UNY

@misc{pith2026250804872,
  author       = {Pith},
  title        = {Pith review of: A Refutation of Elmasry's $\tildeO(m \sqrtn)$-Time Algorithm for Single-Source Shortest Paths},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WRN24UNY}},
  note         = {Machine review of arXiv:2508.04872}
}

abstract

In this note we examine the recent paper "Breaking the Bellman-Ford Shortest-Path Bound" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem and claims that its running time complexity is $\tilde{O}(m\sqrt{n})$, where $n$ is the number of vertices and $m$ is the number of edges. We show that his analysis is incorrect, by providing an example of a weighted graph on which the running time of his algorithm is $\Omega(mn)$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

[1]

�� ...

work page Pith review arXiv 2025

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [1]

�� ...

work page Pith review arXiv 2025