{"id":"e5896525-bcb2-4662-ad90-9e59ba9f3f6c","arxiv_id":"1908.06460","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graph reduction using shortest-path distances from source and target can speed up k-shortest loop-less path search, with large reported speedups on some graph families but losses to a bidirectional baseline on others.","lead":"This paper proposes a preprocessing step that shrinks a graph before searching for the k shortest loop-free paths between two vertices: first compute shortest-path distances from both endpoints, then keep only vertices that could lie on a path short enough to matter. The authors report speedups of up to 365x on some graphs, but their method is sometimes slower than their own baseline.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Speeded-up GR's redundancy removal (Theorem 2) discards by-way paths of vertices on a loopless path based only on equal distance, but the computed shortest-path trees may realize distinct paths; the required tie-breaking is not enforced, so the equivalence to the primitive reduction is unproven.","rationale":"The reader's CONDITIONAL verdict points at Section 3.2.2, which is the right neighborhood, but identifies the loop Lemma in Section 3.1 as the weakest assumption. That Lemma is indeed poorly proved, but the speeded-up algorithm's loop handling does not actually depend on it: Theorem 2 gives a separate argument that loop vertices have strictly smaller by-way distances and are already in V'. The more central gap is the redundancy-removal step, where the paper substitutes distance equality for path identity and relies on an unenforced choice of shortest-path trees. This is a correctness risk for the exact algorithm presented: if the computed parent pointers do not make b(v_ix) coincide with the subpath of b_ij, then distinct loopless by-way paths are removed without being counted, and the proof of equivalence to the primitive reduction collapses. The missing insufficient-case fallback in the speeded-up pseudocode is a second, concrete manifestation of the same incompleteness. I do not claim the algorithm is actually wrong; a suitable tie-breaking convention or a different removal rule could repair it. But as written, the central claim is not established, so the manuscript should remain conditional pending a rigorous proof or a counterexample. The primitive version's Theorem 1, by contrast, appears sound by a distance-threshold argument, so the paper's core idea is not fundamentally invalidated.","tokens_in":14094,"tokens_out":20689,"duration_ms":208792,"concrete_test":"Exhaustively enumerate all undirected weighted graphs with n <= 6 and small integer weights, all choices of source and target, and all valid Dijkstra tie-breaking decisions for the two shortest-path trees. For each instance and each k <= n, run the speeded-up GR algorithm exactly as specified, then run a correct loopless k-shortest-path solver on the resulting G' and compare against Yen's algorithm on the original graph. Also compare V' with the primitive GR's V'. If any run returns a missing k-th path or a vertex set that cannot support a valid k-th path, the reduction claim is false as stated. If no counterexample appears, the result would support (but not prove) the claim; the tie-breaking assumption still needs a formal proof, for example by showing the algorithm can be implemented so that parent pointers are chosen consistently with every processed b_ij.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.2.2 (Theorem 2, 'former' part), after processing a loopless by-way path b_ij = sp(v_s, v_ij) + sp(v_ij, v_t), the algorithm removes from B_s the by-way paths b(v_j1), ..., b(v_jh) for every vertex on b_ij and counts only b_ij. The proof argues that for a vertex v_ix on b_ij, d(b(v_ix)) = d(b_ij), so b(v_ix) 'can be removed regarding it as the same one as b_ij', and that the shortest-path computation can be chosen so that the two paths coincide. This is the load-bearing step. Equality of distances does not imply equality of paths: sp(v_s, v_ix) or sp(v_ix, v_t) may use different edges than the corresponding subpaths of b_ij, producing a distinct loopless by-way path with the same length. Step 1 of the algorithm performs one arbitrary shortest-path-tree computation; nothing in Steps 3-15 enforces the tie-breaking needed to make b(v_ix) coincide with the subpath of b_ij. If it does not coincide, the speeded-up algorithm discards a distinct loopless by-way path without counting it, whereas the primitive algorithm would count it. The proof of Theorem 2 therefore does not establish equivalence to the primitive reduction, and the central claim that G' contains the loopless k-shortest paths is not proven for the algorithm as stated. Separately, the speeded-up pseudocode has no 'insufficient case': if fewer than k loopless by-way paths remain after removals, it still reduces to the partial V' instead of falling back to G as the primitive algorithm does in Section 3.2.1, Step 5/6.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14498,"tokens_out":7163,"duration_ms":68628,"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":[{"comment":"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":"Section 3.1, Lemma and Theorem 1"},{"comment":"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":"Section 3.2.2, Theorem 2"},{"comment":"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":"Section 3.2.2, steps 4-17"},{"comment":"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.","section":"Section 4, consideration 4)"}],"minor_comments":[{"comment":"Reference [K-shortest] is a Wikipedia article; please replace it with a formal bibliographic source for the k-Dijkstra algorithm.","section":"References"},{"comment":"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":"Appendix"},{"comment":"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":"Section 3.2.2, pseudocode"},{"comment":"Several subscript expressions such as b_{i_{j2+1}} are ambiguous; use parentheses or clarify the index arithmetic.","section":"Section 3.1 and Section 3.2.2, notation"},{"comment":"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":"Figures"},{"comment":"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.","section":"Section 3.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is rough in presentation, with a Wikipedia reference and an appendix deferring implementation details to a future paper. The proof gaps are substantial, but they appear to be fixable within the paper's scope by adding explicit tie-breaking, a rigorous replacement for the Lemma, and an insufficient-case fallback in the speeded-up algorithm. I therefore recommend major revision rather than rejection. The experimental evaluation is also based on a single source-target pair per graph family; if the correctness issues are repaired, the authors should strengthen the experimental methodology."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The primitive reduction is clean and I think it's correct: compute shortest-path distances from v_s and v_t, build the by-way-of paths b(v)=sp(s,v)+sp(v,t), sort them, and keep the vertex set of everything up to the k-th loopless by-way path. The proof of Theorem 1 has a sloppy sentence—it says a looped b(v) would be among the first k loopless paths, which isn't literally true—but the distance argument is repairable, and the version that keeps every vertex whose b(v) is below the threshold is sound.\n\nThe speeded-up version in Section 3.2.2 is where I stop following. Theorem 2's main step removes b(v_ix) for every vertex v_ix lying on a loopless b_ij, on the grounds that d(b_ix)=d(b_ij) and therefore the two can be regarded as the same path. That equality only licenses the removal if the shortest-path trees from s and t are tie-broken so that sp(s,v_ix) and sp(v_ix,t) are exactly the subpaths of b_ij. The algorithm does not enforce or even mention that tie-breaking. With arbitrary Dijkstra trees, b_ix can be a distinct loopless path of equal length, which the primitive algorithm would count; the speeded-up version silently under-counts and may stop at a smaller e, omitting vertices that the true k-th shortest path needs. The proof's 'we can make the path be the same' is existential, not algorithmic. And there is a concrete bug: unlike the primitive version, the speeded-up pseudocode has no insufficient-case fallback, so if fewer than k loopless by-way paths survive the removals, it reduces to a partial V' and can return a wrong answer.\n\nElsewhere: the Lemma in Section 3.1 leans on 'extremely small' and 'sufficiently larger' without defining them; the O(n log n) reduction claim is asserted, but loop detection and the removal step are never described, so the bound is not derived; the experiments report one run per data point, no code, no randomized s,t pairs (the authors admit this), and the k-biDij 'state of the art' rests on three references. The measured speedups on k-Dij are large and the breakdown is informative, but the comparison with precomputed all-pairs distances is not apples-to-apples.\n\nFor a reader, the primitive reduction is a nice practical trick worth knowing, and the speeded-up algorithm might be fixable with explicit tie-breaking plus a fallback. As written, the paper shouldn't be cited for the speeded-up version. It deserves a serious referee: the core idea is salvageable and the experiments point somewhere interesting. I'd send it out, expecting major revision.","headline":"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.","tokens_in":14979,"tokens_out":7677,"would_cite":false,"duration_ms":74361,"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":"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.","keywords":["k-shortest paths","graph reduction","loop-less paths","by-way-of shortest paths","bidirectional Dijkstra","scale-free graphs","hypercube graph"],"falsifier":"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.","tokens_in":13878,"feed_emoji":"⚡","tokens_out":6068,"duration_ms":53753,"temperature":0.7,"pith_summary":"This paper proposes a preprocessing method, called GR (Graph Reduction), that shrinks a graph before searching for the k shortest loop-less paths between two vertices. The idea is to compute shortest paths from the source and target to every vertex, form each vertex's 'by-way-of' shortest path through it, and keep only the vertices that appear among the first k loop-less by-way-of shortest paths. The paper claims that this reduced subgraph still contains the true loop-less k-shortest paths, so any existing k-shortest-path algorithm can be run on it and return correct answers. The attraction is cost: the reduction itself runs in O(m + n log n) time independent of k, and experiments show large speedups, including 365 times for a k-Dijkstra variant and up to 35 times for a bidirectional variant when shortest paths are precomputed.","feed_headline":"Shrink the graph first: k-shortest paths get up to 365x speedup","feed_subtitle":"Reduction keeps only by-way-of shortest-path vertices, shrinking the search graph to a fraction of its size.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the classic loop-less k-shortest-path algorithm that GR can wrap; the authors exclude it from experiments because their k-Dijkstra variant outperformed it.","marker":"[Yen71]"},{"why":"Proposes the k-bidirectional Dijkstra algorithm that the authors implement, extend with pruning, and use as the state-of-the-art baseline.","marker":"[Zhao14]"},{"why":"Wikipedia's k-shortest-path-routing article is the source of the k-Dijkstra variant the authors adapt to loop-less paths.","marker":"[K-shortest]"}],"fun_headline_variants":["Graph reduction speeds k-shortest paths up to 365x","Cut the graph first to find k-shortest paths fast","Shrink graph, then speed k-shortest path search","Pre-reduce graph for 365x faster k-shortest paths","Graph reduction speeds up k-shortest path search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Graph reduction speeds k-shortest paths up to 365x","Cut the graph first to find k-shortest paths fast","Shrink graph, then speed k-shortest path search","Pre-reduce graph for 365x faster k-shortest paths","Graph reduction speeds up k-shortest path search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001538,"raw_usage":{"total_tokens":6188,"prompt_tokens":1012,"completion_tokens":5176,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":628,"completion_tokens_details":{"reasoning_tokens":5089}},"tokens_in":628,"tokens_out":5176,"duration_ms":31144,"temperature":1.0,"reasoning_tokens":5089,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:47:08.094365+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}