{"id":"dc636a64-2bbc-47d1-abca-2ca6d30e1cf4","arxiv_id":"1908.06806","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"PST computes all-pairs shortest paths in unweighted graphs by pruning BFS with the shortest path trees of adjacent vertices, reporting 1.2x to 3.1x speedups over BFS in small experiments.","lead":"This paper presents PST, a breadth-first search variant that prunes work using the shortest path trees of neighboring vertices to compute all-pairs shortest paths in unweighted graphs. It reports up to 3.1x faster runtimes than ordinary BFS on hypercube and scale-free graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3.2's termination condition never exits on disconnected undirected graphs, so the claimed exact all-pairs shortest path algorithm for unweighted graphs is not established as stated.","rationale":"The central claim has two parts: exactness and speed. The empirical speed comparison is under-supported (no code, no repetitions, only synthetic graphs), but that is a strengthening issue, not a flaw in the algorithm's logic. Reading Section 3.2 closely, the pruning invariant appears sound for connected undirected graphs: a vertex x at distance d+1 from v via neighbor w lies at depth d in T(w); if an intermediate vertex on that tree path is discovered earlier through another neighbor, its descendants are found through that neighbor's own shortest path tree at no greater depth. So I would not stake the verdict on the reader's pruning-coverage concern. The decisive flaw is the termination condition: the while loop relies on every source eventually reaching c==n, which only holds for connected graphs. The authors explicitly notice unreachability for directed graphs but not for disconnected undirected graphs, and the abstract makes an unqualified claim for unweighted graphs. A one-line connectedness assumption or per-component handling would repair this, which is why the verdict stays conditional rather than accepting or rejecting. The concrete test on a 3-vertex disconnected graph settles the issue immediately.","tokens_in":9037,"tokens_out":17439,"duration_ms":182332,"concrete_test":"Run the Section 3.2 pseudocode unchanged on the disconnected undirected graph with vertices {a,b,c} and edge set {(a,b)}. If the program does not terminate (d increments past n) and leaves D[*][c]=0.0, the unqualified claim is refuted; if the authors intend a connectedness precondition, the preprint must state it and provide component-level handling.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The outer loop `while 0<|V|` only ends when every source has `c==n`, so `V` becomes empty. On any disconnected undirected graph a source whose component has size C<n never reaches c==n; e.g., with vertices {a,b,c} and edge (a,b), the counters for a and b stay at 2 and the loop increments d forever, while D for c remains at its initial 0.0 instead of infinity. The paper's note in Section 3.2 recognizes the same reachability issue for directed graphs but does not restrict the undirected claim to connected graphs, nor does it initialize distances as infinite or process components separately. Thus the exact-APSP claim for general unweighted graphs is false as written. The pruning coverage invariant for the connected case is also not formally proved, but I do not see a counterexample to it; the connectedness/termination gap is the more decisive issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PST, a new all-pairs shortest path (APSP) algorithm for unweighted graphs. The algorithm maintains a shortest path tree T(v) for every source v, with parent and child pointers. When expanding a vertex w while building T(v), PST does not scan all neighbors of w; instead, it scans only the children of the corresponding t-vertex in the shortest path tree of the appropriate adjacent vertex, relying on the fact that a partial path of a shortest path is itself shortest. The authors argue that this prunes the search so that the average number of adjacency accesses per vertex, denoted α, is close to 1, whereas for BFS α is approximately the average degree. They report experiments on hypercube-shaped and scale-free graphs with n = 64, 256, 1024, 4096, claiming that PST is faster than BFS in CPU time and has smaller α. The paper includes detailed pseudocode and a discussion of the data structures, but no formal correctness proof and no code or seeds are provided.","tokens_in":9242,"tokens_out":11571,"duration_ms":119668,"significance":"If the pruning invariant is correct, PST is an interesting practical idea for exact unweighted APSP: it could reduce the constant factor of BFS-based APSP on dense-enough shortest-path trees, and the α measure provides a clean way to quantify that reduction. The authors are honest about the space overhead of storing all shortest path trees and about the exclusion of initialization time from CPU measurements. However, the significance is currently limited by the absence of a correctness proof, a termination bug on disconnected graphs, and an experimental section with single measurements and no reproducibility artifacts. The paper is more a preliminary algorithmic proposal than a fully established result.","major_comments":[{"comment":"As written, the outer loop `while 0 < |V|` terminates only when every source has `c == n`. On a disconnected undirected graph, a source in a component of size C < n never reaches `c == n`, so the loop increments `d` forever, and the unreachable entries of `D` remain at the initial value 0.0 instead of infinity. The paper's note that the stopping condition cannot be used for directed graphs does not cover this undirected case. The exact-APSP claim for general unweighted graphs is therefore false as stated; the manuscript should either restrict the claim to connected graphs or modify the loop and distance initialization to handle components and unreachable vertices.","section":"§3.2, PST algorithm pseudocode (while loop and extend)"},{"comment":"The paper does not prove the coverage invariant that justifies the pruning: at depth d, every undiscovered vertex x at distance d from v is a child of the cor-vertex of some dequeued t-vertex. Section 3.1's 'partial path of a shortest path is also the shortest' argument shows that a vertex on a shortest path through w lies in T(w), but it does not show that the parent chosen in T(w) coincides with the parent chosen in T(v); if the two trees make different parent choices, the pruning could skip x. A formal invariant over the synchronous generation of all T(u) is needed, or the algorithm's exactness on connected graphs is not established.","section":"§3.1 (Pruning by shortest path trees) and §3.2 (extend)"},{"comment":"The central claim that PST outperforms BFS on speed and α rests on single measurements without error bars, code, seeds, or graph-generation parameters, and the text states that the reported PST CPU time excludes initialization because initialization was bundled with graph creation. Since initialization is excluded only for PST (and for Peng/Dijkstra, not BFS), the speed comparison is not clearly fair; initialization should be included in the reported times or its contribution quantified. The paper should also define α operationally (what exactly counts as one adjacency access) and report multiple runs.","section":"§4, Tables 4.1–4.6"}],"minor_comments":[{"comment":"Figure 4.5 appears twice in the dense scale-free case, and the caption 'Fig.4.5 Comparison in α' should be numbered Fig.4.6; the table labels for this subsection are also duplicated.","section":"§4.2.2, figures and tables"},{"comment":"The text says 'BFS’s α is close to 1 in case of hypercube-shaped and sparse scale-free graphs,' but the data in Tables 4.2 and 4.4 show that it is PST's α that is close to 1; BFS's α is several times larger. This appears to be a typo and should be corrected.","section":"§4.3.1, item 1)"},{"comment":"The note that the stopping condition `c == n` cannot be used for directed graphs should be extended to disconnected undirected graphs, since the same failure occurs there.","section":"§3.2, reachability note"},{"comment":"The reference list includes [Kim18], which is not cited in the text, and the [BFS] and [Dijkstra] entries are Wikipedia pages rather than standard bibliographic sources; these should be replaced with appropriate citations.","section":"References"},{"comment":"The column headers use '/.PSTw' and '/PST' interchangeably; one consistent notation should be used throughout the tables and text.","section":"§4, tables and text"},{"comment":"Inside `extend`, the line `n = len(D)` shadows the outer variable `n`; renaming this local variable would improve readability.","section":"§3.2, pseudocode"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reads like a preliminary technical report rather than a completed journal submission. The core idea is interesting and the pseudocode is reasonably clear, but the missing correctness proof and the disconnected-graph termination bug are serious. The termination bug is easy to fix by assuming connectedness or by handling reachability, and the correctness gap could be closed with an invariant proof, so I do not think rejection is warranted yet. However, the experimental section needs substantial improvement (multiple runs, error bars, code or seeds, inclusion of initialization time, and a definition of α) before the speed claim can be evaluated fairly. The comparison is only against BFS, not against more recent practical APSP methods such as Peng's algorithm, which limits the significance of the empirical claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"PST is a new BFS variant that prunes each source's search using the already-built shortest path trees of adjacent vertices. On hypercube and scale-free graphs it reports 1.4-3.1x speedups over BFS and pushes the average adjacency accesses close to 1. That is genuinely new as far as the cited literature goes, and the basic observation - that a shortest path through a neighbor is a shortest path in that neighbor's tree - is sound.\n\nThe strengths: the synchronous tree generation is a real design choice, and the experiments, while thin, are consistent and match the intuition that pruning helps on sparse deep graphs. The paper also honestly admits the space overhead.\n\nThe soft spots are significant. First, the algorithm as written does not terminate on disconnected undirected graphs. The outer loop 'while 0 < |V|' only ends when every source has c == n, but a source in a component of size C never reaches c == n. The authors note this problem for directed graphs but don't restrict the undirected claim to connected graphs, and they don't initialize distances to infinity. That is a genuine bug, not a nitpick. Second, the core correctness invariant - that the cor/children bookkeeping covers all shortest path choices - is asserted informally and never proved. I don't have a counterexample for the connected case, but the paper needs a real proof. Third, the evaluation has no code, no seeds, no error bars, and only three synthetic graph families; the CPU times exclude initialization, which is fine if stated, but it makes the constant-factor claim fragile. Fourth, the references lean on Wikipedia for BFS and Dijkstra, and Peng is mentioned but not compared.\n\nWho is this for? Someone working on practical APSP for unweighted networks who might reimplement PST and test it against real graphs. The idea is plausible enough that a serious referee should look at it, but this draft is not ready: it needs a termination fix, a correctness proof, and reproducible experiments. I would send it back for major revision rather than desk-reject.","headline":"Clever BFS-pruning idea for unweighted APSP with consistent speedups on synthetic graphs, but no correctness proof and a termination bug on disconnected graphs; worth a serious referee only if the authors fill those gaps.","tokens_in":9692,"tokens_out":2433,"would_cite":false,"duration_ms":25030,"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":"PST, a new all-pairs shortest path algorithm for unweighted graphs, claims that when expanding from a source through a neighbor w the search can traverse only the already-built shortest path tree T(w), reducing average adjacency accesses…","keywords":["all-pairs shortest paths","unweighted graphs","breadth-first search","shortest path tree","pruning","adjacency access count","alpha","hypercube graphs"],"falsifier":"Run PST on a small graph with multiple equal-length shortest paths, such as a 4-cycle with a chord, and compare every entry of the distance matrix $D$ against a plain BFS distance matrix. If any pair has $D[x,v]$ larger than the true distance, or remains marked NOT_SEARCHED, the pruning coverage invariant fails; the same check across many random graphs with heavy tie-breaking would settle whether the tree-based traversal always covers all shortest-path continuations.","tokens_in":8817,"feed_emoji":"⚡","tokens_out":7251,"duration_ms":67204,"temperature":0.7,"pith_summary":"The paper proposes PST, an all-pairs shortest path algorithm for unweighted graphs that is meant to be faster than breadth-first search by exploiting shortest path trees. Its central claim is that when a source vertex $v$ reaches a neighbor $w$, every further vertex on a shortest path from $v$ through $w$ lies in the shortest path tree $T(w)$ already built for $w$; therefore PST can traverse only that tree instead of scanning all of $w$'s adjacency. This drops the average number of adjacency accesses per vertex, denoted $\\alpha$, from about the average degree of the graph to about 1 in tree-like cases, because a tree has average degree near 2 and only one edge is entered and one exited per visited vertex. Experiments on hypercube and scale-free graphs report $\\alpha$ between 1.19 and 1.71 (versus 3.15 to 12.12 for BFS) and CPU time 1.38 to 3.08 times faster at $n = 4096$, with the caveat that dense low-diameter graphs reduce the gain. A sympathetic reader would care because the method is a simple practical improvement for exact distances on unweighted graphs, not a change in worst-case asymptotic complexity.","feed_headline":"Shortest-path-tree pruning beats BFS on unweighted graphs","feed_subtitle":"New algorithm cuts average adjacency accesses per vertex to 1.19-1.71, making it up to 3.1x faster in tests.","key_machinery":"The central object is the cor pointer on each t-vertex: a t-vertex $x'$ on $T(v)$ reached through a neighbor's t-vertex $w'$ stores a reference to the corresponding t-vertex $x''$ on $T(w)$, and when extending $T(v)$ one level the algorithm steps through $x''.children$ instead of the graph adjacency list. The second mechanism is the d-queue, a FIFO queue modified to hold $(vertex, distance)$ pairs and to dequeue only pairs at the currently required depth; this makes all shortest path trees grow synchronously, guaranteeing that the needed part of $T(w)$ already exists when $T(v)$ is extended through $w$.","core_discovery":"PST computes exact all-pairs shortest path distances in unweighted graphs by generating every shortest path tree $T(v)$ synchronously, layer by layer, and using the already-generated tree $T(w)$ of each neighbor $w$ as the only region searched when extending $T(v)$ through $w$. Formally, if $\\sigma_v(x)$ contains edge $(v,w)$, then $\\sigma_v(x)$ can be written as $(v,w)$ plus $\\sigma_w(x)$, so no edge outside $T(w)$ needs to be inspected. The algorithm encodes this with a cor pointer: each t-vertex $x'$ in $T(v)$ that was reached through $w'$ points to the corresponding t-vertex $x''$ in $T(w)$, and extension at the next depth iterates over $x''.children$ rather than over the adjacency list of the underlying graph vertex. The paper claims, and measures, that this reduces the average adjacency-access count $\\alpha$ to values close to 1 and makes PST faster than BFS on the tested hypercube and scale-free graphs while keeping exact shortest paths.","pith_inferences":["A direct testable extension would run PST on random regular graphs with controlled diameter; the paper's $\\alpha$-to-1 mechanism predicts that large-diameter, low-degree graphs give the largest gap over BFS.","The pruning idea could be reused for a few-source or single-source setting after a preprocessing pass builds the needed trees, though the paper only presents the all-pairs version.","The synchronous d-queue is the likely serial bottleneck; a parallel variant would have to coordinate layer-by-layer extensions across sources, which the paper does not discuss.","The cor/children bookkeeping may be sensitive to parent choices inside each $T(w)$; a stress test with many equal-length shortest paths would show whether any tie-breaking regime causes missed vertices."],"forward_implications":["If PST is correct, exact all-pairs shortest paths on unweighted graphs can be computed with far fewer adjacency scans than BFS on graphs with large diameter, since $\\alpha$ approaches 1 rather than the average degree.","The speedup should grow with $n$ on hypercube-like and sparse scale-free graphs; the paper's tables show CPU-time ratios increasing from about 1.6 to about 3.1 as $n$ grows from 64 to 4096.","On dense graphs with small diameter, the advantage shrinks because pruning cannot begin at depth 1; the paper's dense scale-free case shows $\\alpha$ of 6.23 at $n = 4096$, still 1.95 times lower than BFS.","The space cost is higher than BFS: storing t-vertices for every source vertex adds memory beyond the $n \\times n$ distance and parent matrices.","The paper's $\\alpha$-close-to-1 claim is an average over vertices, not a worst-case guarantee, so graph families with many depth-1 vertices will retain a larger constant."],"supporting_citations":[{"why":"Supplies the baseline algorithm, described as a representative fast method for unweighted all-pairs shortest paths with alpha about equal to average degree.","marker":"[BFS]"},{"why":"Defines the weighted single-source algorithm that PST compares against conceptually as AP-Dijkstra with O(n(n log n + m)).","marker":"[Dijkstra]"},{"why":"Defines the Floyd-Warshall all-pairs baseline with O(n^3), which the paper excludes from experiments as slower.","marker":"[Floyd62]"},{"why":"Companion citation for the Floyd-Warshall transitive-closure formulation that the paper cites as the O(n^3) baseline.","marker":"[Warshall62]"},{"why":"Prior all-pairs shortest path method that reuses already computed path lengths to cut alpha; PST is positioned as an unweighted alternative in the same direction.","marker":"[Peng12]"}],"fun_headline_variants":["Tree pruning cuts shortest-path work near 1x","Shortest-path trees turn APSP into near-degree-1 search","PST algorithm: faster exact APSP by reusing neighbor trees","New APSP algorithm prunes BFS by borrowing neighbor's tree","All-pairs shortest paths with near-degree-1 adjacency checks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every shortest path from a source through a neighbor continues along a shortest path from that neighbor, and that the bookkeeping records all those continuations in the neighbor's tree; if the bookkeeping misses one, PST returns a wrong distance.","fun_headline_variants_meta":{"raw":{"variants":["Tree pruning cuts shortest-path work near 1x","Shortest-path trees turn APSP into near-degree-1 search","PST algorithm: faster exact APSP by reusing neighbor trees","New APSP algorithm prunes BFS by borrowing neighbor's tree","All-pairs shortest paths with near-degree-1 adjacency checks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001153,"raw_usage":{"total_tokens":4772,"prompt_tokens":935,"completion_tokens":3837,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":3750}},"tokens_in":551,"tokens_out":3837,"duration_ms":25522,"temperature":1.0,"reasoning_tokens":3750,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:34:38.603972+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PST on a small graph with multiple equal-length shortest paths, such as a 4-cycle with a chord, and compare every entry of the distance matrix $D$ against a plain BFS distance matrix. If any pair has $D[x,v]$ larger than the true distance, or remains marked NOT_SEARCHED, the pruning coverage invariant fails; the same check across many random graphs with heavy tie-breaking would settle whether the tree-based traversal always covers all shortest-path continuations.","supporting_citations":[],"review_version":1}