REVIEW 4 major objections 6 minor 3 references
A New k-Shortest Path Search Approach based on Graph Reduction
T0 review · 4 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proposes and tests a graph-reduction preprocessing pass that lets any loop-less k-shortest-path algorithm run on a much smaller subgraph without losing the correct answers.
desk verdict Primitive graph-reduction idea is sound and the speedups look real, but the speeded-up algorithm's correctness proof has a load-bearing tie-breaking gap and a missing fallback; worth a serious referee, not citable as-is. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key object is the by-way-of shortest path b_i = sp(v_s, v_i) concatenated with sp(v_i, v_t): the shortest v_s-to-v_t path that passes through v_i. GR sorts all n such paths by length, scans them for the first k loop-less ones, and sets V' to the vertices on this scanned prefix. The scanning order carries the argument: the k-th loop-less by-way-of path supplies a distance threshold such that every vertex excluded from V' has by-way-of distance at least that threshold, so no k-shortest path can need it. The speeded-up variant avoids deduplicating equal by-way-of paths by adding only the by-way-of vertex of a looping path and relying on a lemma that all other loop vertices appear earlier.
What would settle it
Construct a small weighted undirected graph where a by-way-of shortest path contains a loop, the detour through the loop is not 'extremely small', and the next by-way-of distance is not 'sufficiently larger', then check whether the k-th loop-less shortest path uses a vertex outside the reduced subgraph; if it does, Theorem 1 fails.
Extended reading notes
Core claim
The central claim is Theorem 1: if G' is the subgraph induced by the vertices lying on the first e by-way-of shortest paths, where e is the index of the k-th loop-less by-way-of shortest path from v_s to v_t, then G' contains all loop-less k-shortest paths from v_s to v_t. The proof argues that any vertex outside V' has a by-way-of shortest path no shorter than the k-th loop-less one, and therefore no path through that vertex can be shorter than the k-th shortest path. On this basis GR becomes a meta-algorithm: any existing k-shortest-path algorithm, such as Yen's, k-Dijkstra, or k-bidirectional Dijkstra, can be applied to G' instead of G.
Load-bearing premise
The correctness of the speeded-up reduction depends on a lemma whose proof assumes that some edge weights are 'extremely small' and that the gap to the next by-way-of distance is 'sufficiently larger' than the cost of a detour; in arbitrary weighted graphs those conditions are not guaranteed, and if a loop vertex were missed, the reduced graph could omit a vertex that a true k-shortest path needs.
Editorial extensions
If this is right
- Any existing loop-less k-shortest-path algorithm can be wrapped by GR and will return the correct k shortest paths on the reduced subgraph.
- The reduction cost O(m + n log n) does not grow with k, so GR is most attractive when k is large relative to n.
- With all-pairs shortest paths precomputed, the reduction step is nearly free and GR(k-biDij) beats the standalone bidirectional variant on every tested graph family.
- The reduced subgraph can be much smaller than the original: for n = 16384 and k = 128, the hypercube reduces to about 1/22 of its vertices.
- GR is a meta-algorithm, so improvements in the inner k-shortest-path algorithm compose with the speedup from reduction.
Reading between the lines
- The proof of Theorem 1 as written rules out paths strictly shorter than spd_k through excluded vertices; if equal-length ties count as distinct k-shortest paths, the reduction may need tie-breaking or a strict-inequality caveat to remain valid.
- GR's effectiveness should transfer to road networks and other graphs with strong shortest-path structure, but the loop lemma suggests adversarial weights can break the reduction guarantee, so a randomized weight perturbation or a direct check on the reduced subgraph's paths could test robustness.
- The O(m + n log n) bound independent of k hints that GR could serve as a preprocessing primitive inside real-time routing engines that precompute all-pairs distances for many source-target queries.
- The speeded-up variant effectively deduplicates equal by-way-of paths by construction; a formal proof that this never adds a vertex that the primitive version would omit would tighten the correctness argument.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a preprocessing scheme, called GR (Graph Reduction), for loopless k-shortest-path search in undirected weighted graphs. GR first computes shortest-path trees from the source and target vertices, forms a 'by-way-of shortest path' through each vertex by concatenating the two tree paths, sorts these by distance, and identifies the k-th loopless one. The primitive version reduces the graph to the vertices lying on the first e by-way-of shortest paths; a speeded-up version tries to avoid duplicate enumeration by deleting all by-way paths of vertices on each loopless by-way path and adding only the vertex of a looping by-way path. The claimed contribution is a meta-algorithm that can wrap any existing k-shortest-path algorithm, with reduction time O(m + n log n) independent of k, and an experimental comparison of GR(k-Dij) and GR(k-biDij) on hypercube-shaped and scale-free graphs.
Significance. If the correctness argument can be made rigorous, GR is an attractive meta-algorithm: the reduction time is independent of k, and the experiments show order-of-magnitude speedups, especially when all-pairs shortest paths are precomputed. The paper makes a concrete falsifiable claim—that the reduced subgraph contains the loopless k-shortest paths—and provides comparative measurements against independently implemented baselines. However, the central proof currently rests on two unproved assertions: the Lemma in Section 3.1 relies on non-rigorous distance assumptions, and the speeded-up algorithm's deletion rule in Section 3.2.2 is not shown to be equivalent to the primitive reduction. These gaps are load-bearing and must be repaired before the main claims can be accepted.
major comments (4)
- [Section 3.1, Lemma and Theorem 1] The Lemma in Section 3.1 is not established for arbitrary graphs. Its proof assumes that d(v_{i_{j1}}, v_{i_{j2}}) is 'extremely small' and that d(b_{i_{j2+1}}) is 'sufficiently larger' than d(b_{i_{j1}}); these are metric assumptions that need not hold in the input graph, and no argument shows that the constructed path p is loopless. Since the Lemma is used to justify that vertices in a looping by-way-of shortest path must belong to V', Theorem 1 does not currently cover all vertices outside V': a looping by-way path b(v) with d(b(v)) < d(b_{j_k}) would not appear among the loopless b_{j1},...,b_{jk}, so the statement 'if d(b) < d(b_jk), b should be one of b_j1,...' is unjustified for looping b. This gap affects both the primitive and the speeded-up versions of GR.
- [Section 3.2.2, Theorem 2] In steps 8-10 of the speeded-up GR algorithm, the algorithm deletes b(v_{j1}),...,b(v_{jh}) from B_s solely because d(b_{ij}) = d(b_{ix}). Equal distances do not imply equal paths; the shortest-path trees computed in Step 1 are arbitrary, and nothing in Steps 3-15 forces sp(v_s, v_{ix}) and sp(v_{ix}, v_t) to coincide with the subpaths of b_{ij}. The proof's statement that 'it is possible or allowed' to select such paths describes a tie-breaking rule that the algorithm does not implement. Unless the algorithm is modified to enforce the needed tie-breaking, or the deletion is proved safe for arbitrary tie-breakings, the equivalence with the primitive reduction, and hence Theorem 2 and the correctness of the speeded-up GR used in the experiments, is unproven. Theorem 3 inherits this gap because it relies on Theorem 2.
- [Section 3.2.2, steps 4-17] The speeded-up GR algorithm has no 'insufficient case'. If the while loop in Steps 5-15 terminates with c < k, the algorithm nevertheless proceeds to Step 16 and applies Ex to G' built from the partial V'. The primitive algorithm, by contrast, explicitly falls back to G in Step 5 of Section 3.2.1. If a graph has fewer than k loopless by-way-of shortest paths, the speeded-up algorithm may omit vertices needed for the actual k-th shortest path and thus return an incorrect result. The pseudocode must add the fallback V' = V when c < k.
- [Section 4, consideration 4)] The claim that proper graph reduction takes O(n log n), and hence total reduction O(m + n log n), is not derived. Step 7 requires loop detection for each processed by-way path, but no algorithm or data structure for loop detection is described, and testing whether a path contains a repeated vertex can cost O(length) per path. Steps 10 and 15 require deleting arbitrary elements from the sorted sequence B_s; if B_s is stored as an array, deletions are not O(1), and no alternative structure is specified. Please provide a detailed complexity analysis covering these operations before claiming that the reduction is independent of k.
minor comments (6)
- [References] Reference [K-shortest] is a Wikipedia article; please replace it with a formal bibliographic source for the k-Dijkstra algorithm.
- [Appendix] The appendix states that details of the improvements to k-biDij will be described in a future paper; for reproducibility, the improvements used in the experiments need either a full specification in this paper or a citable reference.
- [Section 3.2.2, pseudocode] Step 10 uses b_{j1},...,b_{jh} after Step 8 defines v_{j1},...,v_{jh}; make explicit that b_{jl} denotes the by-way-of shortest path of vertex v_{jl}.
- [Section 3.1 and Section 3.2.2, notation] Several subscript expressions such as b_{i_{j2+1}} are ambiguous; use parentheses or clarify the index arithmetic.
- [Figures] Figures 3.1-3.4 and 4.1-4.3 are referenced in the text but are not included in the manuscript text I reviewed; please ensure all figures are present and legible.
- [Section 3.3] There is a typo: 'odify' should be 'modify'. Also, in Section 4.3 the phrase 'dense sparse scale-free graphs' is inconsistent and should be corrected.
Circularity Check
No circularity: GR's graph reduction is derived from shortest-path computations and analyzed independently; the proof gaps identified are correctness concerns, not circular reasoning.
full rationale
The derivation is self-contained. The reduced graph V' is defined from by-way-of shortest paths b_i = sp(v_s, v_i) + sp(v_i, v_t), which are computed directly from two Dijkstra runs in Step 1 of both GR variants. The paper never fits a parameter to the k-shortest paths and never invokes the target k-shortest-path result to choose V'. Theorem 1's proof is a lower-bound argument from shortest-path optimality: for any vertex v outside V', its by-way shortest path b(v) satisfies d(b_jk) <= d(b(v)) by sorted order of loopless by-way paths, and d(b(v)) <= d(p) for any path p through v, so any such p has d(p) >= spd_k. This does not reduce to the conclusion by construction. The Lemma in Section 3.1 and Theorem 2 contain unproven assumptions (e.g., 'extremely small' and 'sufficiently larger' distances, and the freedom to tie-break equal-length shortest paths), and the speeded-up algorithm omits the primitive algorithm's 'insufficient case' fallback; these are correctness gaps that could invalidate the reduction, but they are not circular because they do not assume the target result as input or rename a fitted quantity as a prediction. There are no load-bearing self-citations: the cited references are Yen's algorithm and Zhao's bidirectional variant. The complexity claim is analytic and the experimental comparisons use independently implemented baselines. The paper is therefore free of significant circularity, despite the non-circular proof-quality issues noted by the skeptic.
Assumptions & free parameters
assumptions (4)
- domain assumption Non-negative edge weights so Dijkstra's algorithm computes shortest paths.
- standard math Subpaths of shortest paths are shortest paths.
- ad hoc to paper Shortest path trees from v_s and v_t can be chosen so that the by-way-of path of any vertex on a processed path coincides with the path itself.
- ad hoc to paper The Lemma's constructed path p with d(p) < d(b_{i_e}) exists using 'extremely small' and 'sufficiently larger' distances.
Cite this review
Pith. "Pith review of A New k-Shortest Path Search Approach based on Graph Reduction." pith.science (2026). https://pith.science/paper/SB2KH2CL
@misc{pith2026190806460,
author = {Pith},
title = {Pith review of: A New k-Shortest Path Search Approach based on Graph Reduction},
year = {2026},
howpublished = {\url{https://pith.science/paper/SB2KH2CL}},
note = {Machine review of arXiv:1908.06460}
}
read the original abstract
We present a new approach called GR (Graph Reduction) algorithm for searching loop-less k-shortest paths (1st to k-th shortest paths) in a graph based on graph reduction. Let a source vertex and a target vertex of k-shortest paths be v_s and v_t respectively. First our approach computes shortest paths to every vertex from v_s and v_t respectively, and reduce a graph to a subgraph that contains all vertices and edges of loop-less k-shortest paths using the already computed shortest paths, and apply an existing k-shortest path search algorithm to the reduced graph. A graph can be reduced quickly after computing the shortest paths using them, therefore a very efficient search can be achieved. In an experiment using a hypercube graph which has 16384 vertices where k=128, the number of vertices is reduced to about 1/22, and a variant of Dijkstra algorithm for k-shortest path search were speeded up by about 365 times. We implemented a fast k-shortest path variant of bidirectional Dijkstra algorithm (k-biDij) which is the state-of-the-art algorithm and the fastest as long as we know, GR outperforms k-biDij in dense scale-free graphs. However, k-biDij outperforms GR in hypercube-shaped and sparse scale-free graphs, but even then GR can also speed up it by 12.3 and 2.0 times respectively by precomputing all-pairs shortest paths. We also show the graph reduction can be done in time complexity O(m + n log n). We also introduce our improvements to k-biDij simply.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Pruning by counting the shortest paths at each vertex As mentioned above, 𝑘 -Dijkstra algorithm in [K-shortest] searches beyond a vertex 𝑣 if the number of paths from the source vertex is less than or equal to 𝑘. We improved further so that when searching beyond 𝑣, a new path 𝑝𝑤 which is a path from a starting vertex to 𝑤 adjacent to 𝑣 is added to a prior...
-
[2]
The path from 𝑠 is enqueued into 𝑄
Pruning using priority queues at each vertex A priority que 𝑄 is placed at a starting vertex 𝑠 (a source vertex and a target vertex in case of 𝑘- bidirectional Dijkstra algorithm). The path from 𝑠 is enqueued into 𝑄. It is desirable that the number of paths enqueued to it is as small as possible because the cost to maintain the order becomes smaller. When...
-
[3]
𝑄 only keeps the top-𝑘 shortest paths
Pruning by a terminating condition In our implementation, when at a vertex 𝑣, a path from 𝑝𝑣 𝑠 from 𝑣𝑠 to 𝑣, and 𝑝𝑣 𝑡 from 𝑣𝑡 to 𝑣 conflicts, a path 𝑝 is composed from 𝑝𝑣 𝑠 and 𝑝𝑣 𝑡, and it is enqueued into a priority queue 𝑄. 𝑄 only keeps the top-𝑘 shortest paths. When 𝑄 is full, we utilize the value 𝑙𝑘 which is the length of the 𝑘-th shortest path in 𝑄....
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.