{"id":"20ff8521-172b-4fc5-8533-c92a0cc07fea","arxiv_id":"1908.06798","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"PSTw adapts the authors' unweighted PST idea to weighted graphs, adds a waiting mechanism to avoid deadlock, and reports CPU-time and edge-access advantages over Dijkstra and Peng on several synthetic graph classes.","lead":"PSTw is a new all-pairs shortest-path algorithm for weighted graphs that prunes searches using the shortest path trees of neighboring vertices. On synthetic dense and hypercube graphs it reports speedups over Dijkstra and Peng, but on sparse scale-free graphs Peng is up to five times faster.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The deadlock-free proof in §3.3 relies on an inequality between final shortest distances that priority-queue order cannot supply, so the paper's only formal guarantee for PSTw is unproved.","rationale":"The reader's weakest-assumption analysis identifies the same spot I would: the unsupported inequality in the deadlock-free proof. I agree. I considered whether the deeper issue might be output correctness (PSTw could terminate with wrong distances), and that is a real additional gap since §3.3 only targets deadlock and the evaluation never verifies D against a reference. But the most load-bearing single point is still the theorem's inequality, because the theorem is the only formal argument that the waiting mechanism cannot stall forever; without it the algorithm's central operational guarantee is missing, and even the empirical runtime comparisons lose their meaning if runs may not terminate. This is not a disagreement with community consensus; it is an internal gap: §3.3's own variables d_i are defined as distances, while the algorithm's queue stores tentative upper bounds, so the proof moves between two different quantities without a lemma connecting them. The proposed instrumentation directly checks whether the inequality holds in actual executions. A single violation would confirm the proof gap; absence in small exhaustive search would make the theorem plausible again and show the proof needs repair rather than rejection. Therefore I leave the reader's REJECT verdict unchanged.","tokens_in":13056,"tokens_out":17732,"duration_ms":182114,"concrete_test":"Implement the §3.2 algorithm exactly (resolving undefined w'' and x' as w'.cor and w'.vertex), instrument the waiting branch at (*) to record for every requeue the final all-pairs distances d_{i+1}, d_{i+2} and the path length e_{i+1}+d_{i+2}, and exhaustively run all connected undirected graphs with n<=5 and edge weights in {1,2,3}. If any waiting event has e_{i+1}+d_{i+2} > d_{i+1} with final distances, the key inequality in §3.3 is not a consequence of priority order, and the deadlock-free proof as written fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The keystone of the paper is the Theorem in §3.3: if all edge weights are positive, PSTw is deadlock-free. The proof's only nontrivial step is the inequality e_{i+1}+d_{i+2} <= d_{i+1}, justified because 'x_{i+2} should have been enqueued before x_{i+1}' in v_{i+1}'s priority queue. This justification does not work. The queue orders by tentative keys, which are upper bounds, not by the true shortest distances d_{i+1}, d_{i+2} that the proof inserts into the inequality. A vertex whose own entry is not determined may still have a smaller true distance than the entry ahead of it, so the waiting configuration described in the proof does not imply e_{i+1}+d_{i+2} <= d_{i+1}. The summation that follows, giving sum e_i <= 0 and the contradiction with positive weights, collapses once that inequality is removed. The same gap also leaves the stronger central claim unaddressed: even if PSTw always terminates, §3 proves neither that the computed D matrix equals the true all-pairs shortest distances nor that children are never generated after a vertex has been settled. The evaluation reports CPU time and alpha only, so it supplies no independent check of output correctness. The undefined identifiers near the waiting code (w'' and x' in the 'else' branch of extend) are additional obstacles to verifying the intended algorithm, but the unsupported inequality is the decisive flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes PSTw, a weighted all-pairs shortest path algorithm that prunes the search space by using the shortest path trees of adjacent vertices. It presents a deadlock-freeness theorem in §3.3, and reports an experimental comparison against Dijkstra's algorithm and Peng's algorithm on hypercube-shaped and scale-free graphs, measuring wall-clock time and an average adjacency-access count alpha. The central claims are that PSTw is correct (deadlock-free and computes all shortest paths) and that it outperforms Dijkstra in most cases and Peng on hypercube and dense scale-free graphs.","tokens_in":13388,"tokens_out":3536,"duration_ms":36081,"significance":"If PSTw were correct and as fast as reported, it would be a valuable alternative for all-pairs shortest path computation on large graphs, achieving alpha values close to 1 in several graph families. The experimental design covers multiple graph shapes and sizes, and the authors honestly discuss the space-complexity overhead and the deadlock risk. However, the correctness of the distance matrix is never proven, and the only formal guarantee attempted, the deadlock-freeness theorem, relies on an unjustified inequality. The contribution is therefore not established at the level expected for an algorithms paper.","major_comments":[{"comment":"The proof of deadlock-freeness uses the inequality e_{i+1}+d_{i+2} <= d_{i+1}, justified by the claim that x_{i+2} was enqueued before x_{i+1} in the priority queue. The priority queue orders by tentative (known) distances, which are upper bounds, not by the true final distances d_{i+1} and d_{i+2} that appear in the inequality. The path from v_{i+1} to x_{i+2} through v_{i+2} can be longer than the true distance to x_{i+1}. Without this inequality, the summation argument that yields sum e_i <= 0 collapses, so the theorem is not proved.","section":"§3.3"},{"comment":"The pseudo-code for extend() contains undefined identifiers in the else branch: w'' is used before any definition (presumably w'.cor), and the re-enqueued pair at the marked line (*) uses edge_len, which is not the distance that was dequeued, instead of the correct variable. Additionally, the loop iterates over x'' in w''.children but references x'.vertex before x' has been assigned in the NOT_SEARCHED branch, making the code ambiguous and not directly executable.","section":"§3.2"},{"comment":"The paper proves only deadlock-freeness, but it does not prove that PSTw terminates with D[i,j] equal to the true shortest distance from v_i to v_j, nor does it prove that the pruning by shortest path trees never discards a necessary path. Even if the deadlock argument were repaired, the key property of an all-pairs shortest path algorithm, correctness of the returned distances, remains unproven.","section":"§3 overall"},{"comment":"The evaluation reports a single CPU time and a single alpha value for each combination of algorithm, graph family, and size, with no repeated runs, no variance measures, and no check that the computed distances match the outputs of a reference implementation such as Dijkstra. Without a correctness check, the reported speedups could in principle come from an algorithm that sometimes returns incorrect distances.","section":"§4"}],"minor_comments":[{"comment":"The manuscript has many typos and grammatical errors, such as 'childeren' instead of 'children', 'algorithm' missing a period, and inconsistent spacing; a careful proofreading is needed before resubmission.","section":"Throughout"},{"comment":"Figure 3.3, which illustrates the waiting configuration and the distances used in the proof, is referenced but not included in the text, making the argument harder to follow.","section":"§3.3"},{"comment":"The abstract begins by referring to a previous submission, which is an unusual style for a self-contained paper, and several references cite Wikipedia entries without full bibliographic details.","section":"Abstract and references"}],"recommendation":"reject","confidential_remarks":"The core algorithmic claim is not established: the only formal proof in the paper, the deadlock-freeness theorem, hinges on an invalid inference, and no correctness proof for the computed distances is provided. The pseudo-code is ambiguous, and the experimental section lacks basic statistical rigor and output verification. These are load-bearing issues that go beyond local presentation and require a fundamental revision of the manuscript's technical content."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a plausible engineering extension of their unweighted PST idea to weighted graphs, and the reported speedups on hypercube and dense scale-free graphs are worth a look. But the only formal guarantee they claim is not proved, and correctness of the algorithm is not proved at all. I would not accept it in this form, but I would engage with the idea.\n\nWhat's new: the waiting and suspension mechanism is a real adaptation to weighted graphs, and the deadlock problem is a genuine issue that does not arise in PSTu. The empirical comparison is honest—they report losing to Peng by 5x on sparse scale-free graphs as well as winning elsewhere—and the α metric is a useful diagnostic. The paper also correctly notes the space complexity disadvantage of storing full trees per source.\n\nWhere it comes apart: the stress-test note is right. The deadlock-free proof in §3.3 rests on the inequality e_{i+1}+d_{i+2} ≤ d_{i+1}, justified by enqueue order. But the priority queue orders by tentative keys, which are upper bounds, not final distances. Since the algorithm allows updates to already-enqueued vertices, a vertex can be dequeued with a key that is not its true distance. So the inequality does not follow, and the summation argument gives no contradiction. Separately, even if PSTw always terminates, the paper never proves that the computed D matrix equals the true all-pairs distances, or that a vertex's children are never generated after it has been settled. The pseudo-code also has undefined identifiers (w'' and edge_len in the waiting branch) and inconsistent use of x' vs x''. Those are fixable, but they make verification harder.\n\nThe evaluation is a real soft spot in a different way: no error bars, no repeated runs, no code release. The CPU times are plausible, but we only have the reported numbers. For a paper claiming both correctness and speed, a correctness check against a known implementation would be a minimal addition.\n\nWho this is for: someone working on practical all-pairs shortest paths for dense or regular graphs might get useful ideas, especially the α metric and the observation about where Peng's sorting-by-degree trick pays off. But a reader needs to treat the performance claims as provisional.\n\nMy recommendation: this deserves a serious referee, not a desk rejection, because the core idea is novel and the flaw in the proof is specific and possibly repairable. But in the current form I would not accept it; the authors need to fix the deadlock-freeness proof or replace it with a termination/correctness argument, clean up the pseudo-code, and release code or at least add verification runs.","headline":"A genuine weighted-graph adaptation of the authors' PST pruning idea with honest experiments, but the deadlock-freeness proof is flawed and correctness is never established.","tokens_in":13883,"tokens_out":7585,"would_cite":false,"duration_ms":67716,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A tree-pruned all-pairs shortest path algorithm for weighted graphs cuts average vertex scans to near one and is proven deadlock-free under positive edge weights.","keywords":["all-pairs shortest paths","weighted graphs","shortest path trees","pruning","deadlock-freeness","priority queues","scale-free graphs","hypercube graphs"],"falsifier":"Run PSTw on a small positive-weight graph with a three-vertex cycle where each vertex waits on the next, choosing edge weights and target vertices so that the key inequality $e_{i+1}+d_{i+2}\\le d_{i+1}$ fails for every $i$ in the cycle; if the graph computation still terminates, the theorem is true but the stated proof reason is not the right one, and if it does not terminate, the theorem is false.","tokens_in":12840,"feed_emoji":"🕸️","tokens_out":8246,"duration_ms":83057,"temperature":0.7,"pith_summary":"PSTw is a proposed all-pairs shortest path algorithm for positive-weight undirected graphs. It claims that when a search from a source reaches a neighboring vertex w, only w's shortest path tree needs to be traversed, not all of w's incident edges; by generating all root-to-vertex shortest path trees synchronously, the average number of adjacent-vertex accesses per vertex drops from about the graph's average degree to roughly 2, and close to 1 when trees are deep. The paper proves that despite the waiting steps needed for synchronization, the algorithm cannot deadlock if all edge weights are positive. On hypercube-shaped and dense scale-free graphs the paper reports PSTw faster than the standard all-pairs method, with much smaller average vertex access counts; against the reuse-based variant, PSTw wins on hypercube-shaped and dense scale-free graphs but loses on sparse scale-free graphs.","feed_headline":"Tree-pruned search cuts weighted all-pairs scans to about two","feed_subtitle":"A new algorithm prunes each source search to its neighbors' shortest path trees and proves it cannot deadlock","key_machinery":"The object that carries the argument is the shortest path tree of an adjacent vertex, stored as a network of t-vertices. A t-vertex represents one vertex in one source's tree and carries a parent, children, an 'is_determined' flag, and a 'cor' pointer to the corresponding t-vertex in the neighboring source's tree; when extending from source $v_i$ through neighbor $w$, the loop reads only the children of the counterpart of $w$ in $T(w)$, pruning everything else. Synchrony is enforced by giving every vertex a priority queue: a dequeued t-vertex whose counterpart in the neighbor tree is not yet determined is enqueued again later, and the tree is extended only when the counterpart's children exist. The deadlock-freeness proof is carried by a summation identity around any purported waiting cycle, $\\sum e_i \\le 0$, which is impossible for positive weights.","core_discovery":"The paper's central claim is that the all-pairs shortest path problem on positive-weight undirected graphs can be solved by a synchronous, tree-pruned extension of the standard label-setting algorithm. For a source $v_i$, the algorithm does not scan every edge of every settled vertex; when the search passes through a neighbor $w$, it traverses only the children of the corresponding node in $w$'s shortest path tree $T(w)$, using a 'cor' pointer that links each node in $v_i$'s tree to its counterpart in $w$'s tree. Because these trees are generated together in rounds, a vertex may find the needed children not yet built and must re-enqueue the waiting vertex, which raises the question of deadlock. The paper's Theorem states that if all edge weights are positive, no deadlock can occur: a cycle of waiting vertices would imply the sum of edge weights around the cycle is $\\le 0$, contradicting positivity. Empirically the paper reports that this construction reduces the average number of adjacent-vertex accesses to about 2 on hypercube graphs and close to 1 on sparse scale-free graphs, and that it is faster than the two comparison algorithms on hypercube-shaped and dense scale-free graphs, though not on sparse scale-free graphs.","pith_inferences":["The synchronous wait-and-re-enqueue structure suggests the algorithm would map naturally onto parallel or distributed execution, with each source's tree advancing in rounds; the paper only reports serial runs.","The reported comparison metric counts adjacent-vertex accesses differently across algorithms (the comparison variant's $\\alpha$ is reported as low as 0.02), so the $\\alpha$ comparisons are not directly interpretable as 'work per vertex' without accounting for the definition.","A natural extension is to directed graphs or zero-weight edges; zero-weight edges would break the strict positivity used in the deadlock proof, so such cases need separate treatment."],"forward_implications":["On graphs with deep shortest path trees, the average number of adjacent-vertex accesses per source becomes near 2, close to the information-theoretic minimum for traversing a tree.","At the largest tested size ($n=4096$), the paper reports speedups of about 2.0 times over the standard all-pairs method on hypercube graphs and about 5.4 times on dense scale-free graphs.","The deadlock-free property means the wait-and-retry scheduling needs no timeout or rollback mechanism for positive weights.","In sparse scale-free graphs, the paper reports the reuse-based variant retains a large advantage (at $n=4096$, factor 5 in CPU time), so the new algorithm is not uniformly dominant.","The extra tree and per-vertex queue storage makes the algorithm's space usage larger than the two comparison methods, which need only the distance and parent matrices."],"supporting_citations":[{"why":"Introduces PSTu, the unweighted pruning-by-shortest-path-tree algorithm that PSTw extends to weighted graphs.","marker":"[Yamane19]"},{"why":"Supplies the standard single-source shortest path algorithm that PSTw modifies and uses as baseline for CPU time and $\\alpha$.","marker":"[Dijkstra]"},{"why":"Describes the reuse-based all-pairs algorithm used as the second baseline in the comparisons.","marker":"[Peng12]"},{"why":"Cited to establish that the Peng algorithm is a state-of-the-art comparison point.","marker":"[Kim18]"}],"fun_headline_variants":["Tree-pruned search cuts weighted all-pairs scans to about two","Deadlock-free tree pruning speeds weighted all-pairs paths","Weighted APSP via tree pruning: scans drop to near two","Pruned shortest path trees reduce weighted APSP vertex accesses","Tree-pruned APSP beats Dijkstra and Peng on dense graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The deadlock-freeness proof relies on the assumption that if one vertex is enqueued before another in a neighbor's priority queue, the path through the first vertex is no longer than the distance to the second; priority-queue order does not actually guarantee that, so the key inequality is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Tree-pruned search cuts weighted all-pairs scans to about two","Deadlock-free tree pruning speeds weighted all-pairs paths","Weighted APSP via tree pruning: scans drop to near two","Pruned shortest path trees reduce weighted APSP vertex accesses","Tree-pruned APSP beats Dijkstra and Peng on dense graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00038,"raw_usage":{"total_tokens":2116,"prompt_tokens":1144,"completion_tokens":972,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":760,"completion_tokens_details":{"reasoning_tokens":885}},"tokens_in":760,"tokens_out":972,"duration_ms":10222,"temperature":1.0,"reasoning_tokens":885,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:34:51.880532+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PSTw on a small positive-weight graph with a three-vertex cycle where each vertex waits on the next, choosing edge weights and target vertices so that the key inequality $e_{i+1}+d_{i+2}\\le d_{i+1}$ fails for every $i$ in the cycle; if the graph computation still terminates, the theorem is true but the stated proof reason is not the right one, and if it does not terminate, the theorem is false.","supporting_citations":[],"review_version":1}