{"id":"d663441e-3a15-4ad4-900a-976768f767a9","arxiv_id":"2506.20017","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Node-Weighted APSP is solvable in Õ(n^{2.686}) time (n^{2.5} if omega=2), and APSP with at most n^{3-omega-delta} distinct weights per node is solvable in subcubic time.","lead":"This paper gives faster algorithms for computing all-pairs shortest paths in graphs where every node has only a few distinct edge weights. It resolves two open questions about when such graphs become easy, and shows that even a sublinear number of weights per node still permits subcubic-time algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Final parameter choice in Theorem 1.5 makes Delta < 1 and the n^3/Delta term supercubic, so Theorem 1.4 does not follow as written.","rationale":"The reader's weakest-assumption analysis focuses on the quantitative exponents in the external BSG Covering theorem. That is a legitimate concern, but it is not the most load-bearing one: even if Theorem 3.1 is fully correct and exactly as quoted, the proof of Theorem 1.4 fails at its final step because the chosen parameters violate the hypotheses of Lemma 5.15 and produce a supercubic n^3/Delta term. Concretely, with epsilon = delta/14 and Delta = n^{2 - c/epsilon}, for small delta the exponent 2 - c/epsilon is negative, so Delta < 1; the lemma requires Delta >= 1, and its runtime includes n^3/Delta, which is then n^{1 + 14c/delta}, far exceeding n^3. This is not merely a typo in one subscript: the displayed algebra cannot be repaired by changing the constant c while keeping the stated form of Delta. The gap is fixable by choosing a positive and very small exponent beta, and the Remark 5.16 sketch points in the right direction, but the formal theorem as written is not established. Because the flaw is in the proof rather than in a claimed false statement, and because a straightforward parameter correction appears to restore the result, CONDITIONAL is the appropriate recommendation rather than REJECT or UNVERDICTED. The reader's identified Section 5.4 typo is real but secondary; the BSG constant dependence is secondary as well, since generic polynomial exponents would still preserve subcubic behavior. The agreement field is therefore 'disagree' because the reader's nominated weakest assumption is not the assumption on which the central claim currently fails.","tokens_in":46944,"tokens_out":11858,"duration_ms":131863,"concrete_test":"Run the displayed substitution in the proof of Theorem 1.5 with delta = 10^{-3}, c = 10, and n = 2^{100}. Then epsilon = delta/14 and Delta = 2^{100(2 - 140000)} = 2^{-13999800}, which is not >= 1, and the Lemma 5.15 term n^3/Delta equals 2^{100 * 140001}, far above n^3. This settles that the current parameter setting cannot yield O(n^{3-epsilon'}). Then independently verify the corrected choice Delta = n^beta with beta = delta / (28 * 2^{O(1/epsilon)}) and check that every displayed running-time inequality in Theorem 1.5 holds; if so, the central claim is recoverable with exponentially small savings.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing defect is not the external BSG constants but the closing parameter selection in the proof of Theorem 1.5. The proof invokes Lemma 5.15, which explicitly requires Delta >= 1, and then chooses epsilon = delta/14 and Delta = n^{2 - c/epsilon}. For any fixed constant c and all sufficiently small delta, we have c/epsilon = 14c/delta > 2, so Delta = n^{negative}, violating the lemma hypothesis. Worse, the term n^3/Delta contributed by Lemma 5.15 becomes n^{1 + 14c/delta}, which is supercubic for small delta and cannot be absorbed into any O(n^{3-epsilon'}) bound. Thus the displayed proof of Theorem 1.5, and hence of Theorem 1.4, is incomplete as written. This is a genuine correctness gap in the manuscript, although it appears fixable: choosing Delta = n^beta with a positive exponent beta = Theta(delta / 2^{O(1/epsilon)}) would make all three displayed running-time terms subcubic with savings exponentially small in 1/delta. The BSG-Covering constants are a secondary premise: even accepting Theorem 3.1 at face value, the main theorem is not established by the text as it stands.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies All-Pairs Shortest Paths under the restriction that each node has at most d distinct outgoing edge weights. It presents three main algorithmic results: (1) a deterministic Node-Weighted APSP algorithm running in Õ(n^{(3+ω)/2}), improving on the 15-year-old bounds of Chan and Yuster; (2) a deterministic d-Weights APSP algorithm running in Õ(d·n^{(3+ω)/2}); and (3) for d = n^{3−ω−δ}, a subcubic O(n^{3−ε}) deterministic algorithm, obtained through a reduction to All-Edges Exact Triangle and a combination of the Balog–Szemerédi–Gowers covering theorem with new uniformization and regularization steps. The paper also gives a Few-Weights Exact Triangle algorithm and conditional lower bounds showing that undirected APSP with two distinct weights is as hard as n^{2.5−o(1)} under the Bounded Min-Plus Hypothesis.","tokens_in":47182,"tokens_out":8902,"duration_ms":92423,"significance":"If the technical gaps identified below are repaired, this is a strong and important paper. The results positively resolve two stated open questions of the area: with ω = 2, Node-Weighted APSP becomes an intermediate problem at n^{2.5+o(1)}, and APSP with any sublinear number of distinct weights per node becomes truly subcubic. The paper also gives a rare application of additive combinatorics to graph algorithms, extends Chan–Lewenstein Clustered 3SUM ideas to the matrix/graph setting, and includes deterministic derandomization and explicit hardness reductions. The proof structure is ambitious and mostly detailed; several lemmas (deterministic almost-linear hashing, rectangular Boolean min-plus products, the approximation of popular sums) are self-contained and useful beyond this paper.","major_comments":[{"comment":"The final parameter choice is invalid. The text says 'Picking ϵ = δ/14 and Δ = n^{2−c/ϵ} for some sufficiently large constant c', but Lemma 5.15 explicitly requires Δ ≥ 1. For every fixed c and all sufficiently small δ, c/ϵ = 14c/δ > 2, so Δ = n^{negative} < 1. With such Δ, the term eO(n^3/Δ) in the displayed running time is supercubic and cannot be absorbed into any O(n^{3−ϵ'}) bound. Thus the proof of Theorem 1.5, and consequently of Theorem 1.4, is incomplete as written. This appears fixable by choosing Δ = n^β with a positive exponent β = Θ(δ / 2^{O(1/ϵ)}) (or an equivalent reparameterization), giving subcubic time with exponentially small savings.","section":"§5.5, proof of Theorem 1.5"},{"comment":"There is a sign inconsistency in the uniformization construction. The definitions state A_g[i,k] = A[i,k] + s_{i,g}, B_h[k,j] = B[k,j] + t_{j,h}, and C_{g,h}[i,j] = C[i,j] + s_{i,g} + t_{j,h}, which does preserve exact triangles. But the uniformity claim immediately after reads 'A_g[i,k] = A[i,k] − s_{i,g} ∈ X_{i,g} − s_{i,g} ⊆ S_g'. With the plus definitions, each A_g entry lies in X_{i,g} + s_{i,g} ⊆ 2s_{i,g} + S_g, and the union over i of these shifted sets need not have size O(d). Therefore the assertion that the constructed instances are d-uniform is not established. The intended construction is presumably A_g = A − s, B_h = B − t, C_{g,h} = C − s − t, and the text should be corrected accordingly.","section":"§5.4, Lemma 5.13, ordinary case"},{"comment":"The popular exceptional case contains a condition that contradicts the running-time analysis. The text says 'we enumerate all (i,j) ∈ [n]^2 with C[i,j] ∉ P_{i,j}' immediately after defining popular exact triangles by C[i,j] ∈ P_{i,j}. The bound O(n^3/∆) that follows is valid only when enumerating the popular pairs, because Property (2) of Lemma 3.3 bounds the number of pairs with nonempty P_{i,j}. This is presumably a typo ('∉' should be '∈'), but as written the analysis of the popular case is not justified.","section":"§5.4, Lemma 5.13, Step 1.2"}],"minor_comments":[{"comment":"The text says 'We compute a size-O(n log n/2^L) hitting set H of P', but the set P is not defined at that point; it should read 'of Q', the set of paths constructed in Step 2.","section":"§4.3, Step 3"},{"comment":"In the unpopular ordinary case, the phrase 'all representations C_{g,h}[i,j] = a+b for (a,b) ∈ S_j × T_j' should presumably be 'S_g × T_h'; the row/column indices j and h are mixed, which makes the statement hard to parse.","section":"§5.4, Step 2.1"},{"comment":"In the base case 'If d = 0 then stop', it would be helpful to state explicitly that this is correct because the d-weights promise implies that at least one of the matrices has no non-⊥ entries, so no exact triangle can exist.","section":"§5.5, Algorithm 1"},{"comment":"The quantitative claims depend on the exact constants and exponents in the quoted BSG Covering theorem (Theorem 3.1). Since the theorem is quoted rather than re-proved, the paper should at least point to the exact statement in [CL15] that yields the displayed bounds, so that the reader can verify the constants are not weaker than needed.","section":"§3.2 and §5.3"}],"recommendation":"major_revision","confidential_remarks":"The two main proof gaps (the Δ parameter selection in Theorem 1.5 and the sign inconsistency in Lemma 5.13) look like fixable typos rather than conceptual barriers; I recommend major revision rather than rejection because the central algorithmic ideas appear sound and the results are significant. I see no problematic circularity: the use of [FJX25] is a published external tool, and the self-citation is not load-bearing in an improper way. Once the proofs are repaired, this paper would be a strong contribution to the field."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper is worth reading: it improves 15-year-old bounds for Node-Weighted APSP and pushes the d-Weights threshold to d ≤ n^{3-ω-δ}, plausibly resolving the two open questions. Second, the proof of the main Few-Weights theorem (Theorem 1.5) has a concrete error in the closing parameter choice, and the stress-test note is right: as written, the theorem does not follow.\n\nWhat is actually new: the multi-level pivot / Boolean min-plus framework for Node-Weighted APSP is clean and gives the intermediate runtime, and the BSG-based uniformization–regularization pipeline is a genuine new combination. The paper is honest about its debt to Chan–Lewenstein and about the exponentially small savings in ϵ′. The hardness part (Theorem 1.6) is a nice complement.\n\nNow the soft spots, in proportion. The displayed proof of Theorem 1.5 sets ε = δ/14 and ∆ = n^{2−c/ε}. For sufficiently small δ, c/ε > 2, so ∆ < 1, violating the hypothesis ∆ ≥ 1 in Lemma 5.15, and the n^3/∆ term becomes supercubic. That is a load-bearing flaw, not a typo. It looks fixable — for instance, choosing ∆ = n^β with β = Θ(δ^2/2^{O(1/δ)}) should balance the three terms — but a referee needs to see the corrected choice before the theorem is established. The paper also leans on external BSG constants without re-proving them; I agree that is normal practice, but since the final runtime is sensitive to those constants, the referee should spot-check the arithmetic. There is a smaller textual issue in Section 5.4, Step 1.2, where the popular case says “C[i,j] ∉ P_{i,j}” when it must mean “∈”; on a literal reading the case split breaks, though the intent is clear.\n\nEverything else holds up: the Node-Weighted APSP section is well structured, the derandomization is careful, and the hardness reductions check out. No code or machine-checked proofs, but that is not unusual for this area and the algorithms are described at implementation level.\n\nWho is this for: anyone in fine-grained complexity or additive-combinatorics-in-algorithms, plus people who teach APSP algorithms. I would send it to a serious referee, not desk-reject it, but the revision must fix the parameter gap or explicitly acknowledge the incompleteness and correct the choice of ∆.","headline":"Strong results and mostly clean proofs, but the final parameter choice in Theorem 1.5 is wrong as written — the error is load-bearing, probably fixable, and the paper deserves a serious referee with requests for revision.","tokens_in":47799,"tokens_out":2969,"would_cite":true,"duration_ms":30667,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W40","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Node-Weighted APSP runs in $\\tilde{O}(n^{(3+\\omega)/2})$; Few-Weights APSP is subcubic for $d\\leq n^{3-\\omega-\\delta}$.","keywords":["APSP","node-weighted APSP","few-weights APSP","all-edges exact triangle","Balog-Szemerédi-Gowers theorem","additive combinatorics","min-plus product","fine-grained complexity"],"falsifier":"Run the BSG covering construction on explicit families of $d$-element integer sets $X,Y$ together with a target sumset $Z$, using $K=(n^{3-\\omega}/d)^{1/7}$, and check whether every covering must have some $|X_k+Y_k|=\\Omega(K^5 d)$ or $|R|=\\Omega(d^2/K)$; if any family forces bounds worse than $O(K^5 d)$ and $O(d^2/K)$, the balancing argument breaks and the claimed $O(n^{3-\\epsilon})$ time for $n^{3-\\omega-\\delta}$-Weights APSP does not follow from this proof.","tokens_in":46734,"feed_emoji":"🧮","tokens_out":15531,"duration_ms":136873,"temperature":0.7,"pith_summary":"This paper studies All-Pairs Shortest Paths (APSP) when each node has at most $d$ distinct outgoing edge weights, a parameter that interpolates between node-weighted APSP ($d=1$) and unrestricted APSP ($d=n$). It proves two things. First, Node-Weighted APSP can be solved deterministically in $\\tilde{O}(n^{(3+\\omega)/2})=\\tilde{O}(n^{2.686})$ time, which is $n^{2.5+o(1)}$ if $\\omega=2$, placing the problem in the intermediate class just above the conditional $n^{2.5-o(1)}$ lower bound. Second, for every $\\delta>0$, instances with $d\\leq n^{3-\\omega-\\delta}$ distinct weights per node can be solved in $O(n^{3-\\epsilon})$ time for some $\\epsilon>0$. If matrix multiplication is optimal, this means APSP with any sublinear number of distinct weights per node is subcubic, so the hardest instances must use $n^{1-o(1)}$ weights per node. The proof routes Few-Weights APSP through All-Edges Exact Triangle and applies the Balog-Szemerédi–Gowers covering theorem from additive combinatorics, together with new uniformization and regularization reductions.","feed_headline":"All-pairs shortest paths become subcubic for sublinear weights per node","feed_subtitle":"If matrix multiplication is optimal, even n^{1−ε} distinct weights per node admit an O(n^{3−ε'}) shortest-path algorithm.","key_machinery":"The load-bearing object is the Balog-Szemerédi–Gowers (BSG) Covering Theorem (Theorem 3.1), an additive-combinatorics statement: any two integer sets $X,Y$ of size at most $d$ can be decomposed into $K$ pairs of subsets $X_k,Y_k$ whose sumsets are small, $|X_k+Y_k|\\leq O(K^5 d)$, plus a small remainder $R$ with $|R|\\leq O(d^2/K)$. The paper uses this decomposition to solve Few-Weights Exact Triangle after reductions: triangles whose weights fall in a structured piece are detected by fast matrix multiplication together with sparse hashing, while remainder triangles are enumerated by brute force, and the two costs are balanced by choosing $K=(n^{3-\\omega}/d)^{1/7}$. For Node-Weighted APSP the mechanism is different: multi-level pivot sets (bridging sets) combined with rectangular Boolean min-plus products are iterated level by level, with a derandomization by greedy hitting sets.","core_discovery":"On the paper's own terms, the discovery is that neither the node-weighted case nor any sublinear-weight case of APSP is as hard as unrestricted APSP. Theorem 1.2 gives a deterministic algorithm for Node-Weighted APSP in $\\tilde{O}(n^{(3+\\omega)/2})$ time, improving the fifteen-year-old $\\tilde{O}(n^{(9+\\omega)/4})$-type bounds and showing that at $\\omega=2$ the problem runs in $n^{2.5+o(1)}$ time, matching a conditional lower bound. Theorem 1.4 gives, for every $\\delta>0$, a deterministic $O(n^{3-\\epsilon})$ algorithm for $n^{3-\\omega-\\delta}$-Weights APSP; with $\\omega=2$ this tolerates $d=n^{1-\\epsilon}$ weights per node, positively answering the question of whether APSP-hard instances must exhaust a linear number of weights per node. The same framework solves Few-Weights All-Edges Exact Triangle in subcubic time. A complementary hardness result shows that under the Bounded Min-Plus Hypothesis, undirected $d$-Weights APSP requires $\\sqrt{d}\\,n^{2.5-o(1)}$ time, so the complexity jumps sharply from $n^{\\omega}$ at $d=1$ to $n^{2.5-o(1)}$ at $d=2$.","pith_inferences":["The uniformization step suggests the true obstruction is not the count of distinct weights but the additive doubling of the weight sets; a testable extension is a $d$-Weights APSP algorithm whose running time is governed by a doubling constant rather than by $d$ itself.","The reduction chain from APSP through Min-Plus and All-Edges Exact Triangle to uniform-and-regular instances may transfer to other all-pairs problems with equality constraints, such as exact-sum triangle counting or clustered variants of min-plus convolution on matrices.","The undirected hardness result draws a sharp phase transition at $d=2$ that the paper does not try to match algorithmically; one open test is whether undirected $2$-Weights APSP admits an $O(n^{2.5+o(1)})$ algorithm when $\\omega=2$, which would show the $n^{2.5-o(1)}$ lower bound is tight.","The framework's dependence on the BSG constants is explicit: if the covering theorem's sumset and remainder bounds were improved, the same algorithm would tolerate $d$ closer to $n^{3-\\omega}$ and could turn the exponential-in-$1/\\delta$ savings into a polynomial dependence of $\\epsilon$ on $\\delta$."],"forward_implications":["At $\\omega=2$, Node-Weighted APSP runs in $n^{2.5+o(1)}$ time, matching the conditional $n^{2.5-o(1)}$ lower bound, so the problem sits in the intermediate complexity class.","For every $\\delta>0$, instances with $d=n^{3-\\omega-\\delta}$ distinct weights per node are solvable in $O(n^{3-\\epsilon})$ time for some $\\epsilon>0$; with $\\omega=2$ this covers every $d=n^{1-\\epsilon}$, so any cubic-time-hard APSP instance must use $d=n^{1-o(1)}$ weights per node.","With current matrix multiplication constants, the algorithm is subcubic for $d\\leq n^{0.628}$, improving the previous threshold $d\\leq n^{0.384}$.","The analogous Few-Weights All-Edges Exact Triangle problem is also subcubic for the same parameter range, generalizing the clustered-3SUM result from arrays to matrices.","Under the Bounded Min-Plus Hypothesis, $d$-Weights APSP in undirected graphs requires $\\sqrt{d}\\,n^{2.5-o(1)}$ time; going from $d=1$ to $d=2$ raises the complexity from $n^{\\omega}$ to $n^{2.5-o(1)}$."],"supporting_citations":[{"why":"Supplies the BSG Covering theorem (Theorem 3.1) used as the main tool for Few-Weights Exact Triangle, and the clustered-3SUM framework the paper generalizes to matrices.","marker":"[CL15]"},{"why":"Provides the prior Node-Weighted APSP algorithm and the Boolean min-plus product operation that the new algorithm refines and improves.","marker":"[Cha10]"},{"why":"Introduces the d-Weights APSP problem, gives the previous subcubic algorithm, and supplies the d-Weights min-plus product method used as a baseline.","marker":"[Yus09]"},{"why":"Contributes the bridging-set multi-level pivot method and rectangular matrix multiplication parameters underlying the deterministic Node-Weighted APSP algorithm.","marker":"[Zwi02]"},{"why":"Establishes the unweighted directed APSP hypothesis and the reduction construction adapted for the undirected d-weights hardness lower bound.","marker":"[CVX21]"},{"why":"Formulates the Strong APSP and u-dir-APSP hypotheses and the Bounded Min-Plus equivalences that the hardness theorem relies on.","marker":"[CVX23]"},{"why":"Gives the reduction from Min-Plus product and APSP to All-Edges Exact Triangle used in Lemma 5.4.","marker":"[VW18]"},{"why":"Provides the deterministic near-linear approximation of popular sums used in the uniformization decomposition.","marker":"[FJX25]"},{"why":"Supplies the current matrix multiplication exponents that determine the quantitative subcubic thresholds quoted in the theorems.","marker":"[ADV+25]"},{"why":"Gives the O(n^omega) algorithm for unweighted undirected APSP that marks the d=1 side of the sharp complexity jump.","marker":"[Sei95]"}],"fun_headline_variants":["Subcubic APSP for sublinear weight diversity per node","Node-weighted APSP falls to n^{2.686}, best bound yet","With optimal matrix multiply, n^{1−ε} weights per node stay subcubic","APSP gets easier when each node has few outgoing weights","New APSP algorithm beats 15-year-old node-weighted runtime"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The Few-Weights subcubic guarantee rests on the exact quantitative bounds of the Balog-Szemerédi–Gowers covering theorem quoted from earlier work — structured pieces with sumset size $O(K^5 d)$ and a remainder of size $O(d^2/K)$ — and the paper does not re-prove those bounds; if the true exponents or constants are worse, the balancing choice $K=(n^{3-\\omega}/d)^{1/7}$ no longer yields subcubic time.","fun_headline_variants_meta":{"raw":{"variants":["Subcubic APSP for sublinear weight diversity per node","Node-weighted APSP falls to n^{2.686}, best bound yet","With optimal matrix multiply, n^{1−ε} weights per node stay subcubic","APSP gets easier when each node has few outgoing weights","New APSP algorithm beats 15-year-old node-weighted runtime"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000568,"raw_usage":{"total_tokens":2865,"prompt_tokens":1293,"completion_tokens":1572,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":909,"completion_tokens_details":{"reasoning_tokens":1478}},"tokens_in":909,"tokens_out":1572,"duration_ms":16487,"temperature":1.0,"reasoning_tokens":1478,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:22:11.410980+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the BSG covering construction on explicit families of $d$-element integer sets $X,Y$ together with a target sumset $Z$, using $K=(n^{3-\\omega}/d)^{1/7}$, and check whether every covering must have some $|X_k+Y_k|=\\Omega(K^5 d)$ or $|R|=\\Omega(d^2/K)$; if any family forces bounds worse than $O(K^5 d)$ and $O(d^2/K)$, the balancing argument breaks and the claimed $O(n^{3-\\epsilon})$ time for $n^{3-\\omega-\\delta}$-Weights APSP does not follow from this proof.","supporting_citations":[],"review_version":2}