{"id":"d3c063b0-639a-4d85-ad74-d74337e65639","arxiv_id":"2501.03363","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The submodularity ratio of the effective graph resistance under link addition can be made arbitrarily close to zero, so generalized submodularity provides no greedy guarantee for k-GRIP.","lead":"Adding links to a network to minimize its effective graph resistance is a hard optimization problem where greedy heuristics are common. This paper shows that the known performance guarantee framework for greedy fails badly: for a family of graphs the submodularity ratio tends to zero, so no approximation guarantee can be derived from it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 9's bound does not follow from Theorem 8: the quoted ratio of gains tends to 6, not 0, so the construction does not establish gamma -> 0.","rationale":"I followed the paper's central argument from Definition 5 through Theorem 9. The construction aims to exhibit one pair (S, R, v) for which the submodularity-ratio condition forces gamma to be small. For any such pair, the definition gives gamma <= (marginal gain on S)/(marginal gain on R). The paper's own Theorem 8 supplies the two marginal gains as Eq. (6) and Eq. (7), but their quotient is asymptotically 6, not 6/N. The Eq. (8) bound printed in Theorem 9 appears to contain an extra factor 1/N, so it cannot be derived from the stated equations. This is load-bearing because the entire contribution of the paper is the claim that gamma -> 0 for this family; if the quotient is merely about 6, the example gives no upper bound below 1 and does not contradict generalized submodularity. The reader's weakest assumption pointed to sign and arithmetic errors in Appendix A, and those are indeed present, but the more decisive issue is the algebraic gap between Theorem 8 and Theorem 9: even a fully corrected Appendix A, holding Eqs. (6) and (7) fixed, cannot yield Eq. (8) as stated. A symbolic simplification of the quotient is the cleanest test, with a small-N Laplacian inversion as an independent numeric check. Because the main theorem is unsupported as written, the appropriate verdict moves from conditional to reject, unless the authors supply a corrected ratio or a different construction.","tokens_in":14523,"tokens_out":19042,"duration_ms":157410,"concrete_test":"Use a computer algebra system to simplify the quotient of Eq. (6) by Eq. (7) and compare it exactly with Eq. (8). Independently, for the Fig. 2 graph with N = 6, compute the four effective resistances R_G(G), R_G(G union v), R_G(G union R), R_G(G union R union v) by inverting the 12 x 12 Laplacian, form the marginal-gain ratio, and compare it with the right-hand side of Eq. (8). If the ratio is approximately 3.22 rather than at most 0.537, the proof of Theorem 9 is invalid and the construction fails to show gamma -> 0.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim rests on Theorem 9, which upper-bounds gamma by Eq. (8) and concludes gamma ~ 6/N -> 0. But for the particular S, R, v used, Definition 5 gives gamma <= [r_G(G union v) - r_G(G)] / [r_G(G union R union v) - r_G(G union R)] = [R_G(G) - R_G(G union v)] / [R_G(G union R) - R_G(G union R union v)]. Substituting the two quantities proved in Theorem 8, namely Eq. (6) = 4/(N-2) and Eq. (7) = 2(N+3)(N+4)(N+5) / [3(N+1)(N+2)(N^2+N-4)], the quotient simplifies to 6(N+1)(N+2)(N^2+N-4) / [(N-2)(N+3)(N+4)(N+5)], which tends to 6 as N grows, not to 0. The printed Eq. (8) contains an extra factor 1/N in the denominator and is not a consequence of Eqs. (6)-(7). For N = 6 the quotient is about 3.22, so the displayed example imposes no nontrivial constraint on gamma (gamma can be 1 for this pair). The sign errors in omega_jk noted by the reader are real symptoms of unreliable algebra, but even after correcting those signs the ratio mismatch remains. As written, the paper does not establish its headline result.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the k-GRIP problem of adding links to minimize effective graph resistance. It claims that for a family of graphs on 2N nodes, the submodularity ratio γ of the normalized effective graph resistance is upper-bounded by a quantity of order 6/N, so γ tends to 0 and the known greedy performance guarantees for generalized submodular functions give no bound. The paper also reports exhaustive and sampled experiments for small graphs, finding greedy solutions with efficiency as low as 0.878. The central theoretical claim rests on Theorem 8, which computes two resistance differences algebraically, and Theorem 9, which combines them into a bound on γ.","tokens_in":14779,"tokens_out":9653,"duration_ms":88259,"significance":"If correct, the result would be a useful strengthening of the known non-submodularity of the k-GRIP objective: it would show that γ-based performance guarantees degrade to zero on a natural graph family. The paper is transparent in giving explicit algebraic expressions and a checkable construction, and the small-graph brute-force comparison is a reasonable empirical contribution. However, the main theorem is invalid as stated: the quotient obtained from the paper's own Eqs. (6) and (7) tends to 6, not 0, so the construction does not establish γ→0. The central claim is therefore unsupported, and the paper would need a substantially different construction or a corrected analysis to make its stated contribution.","major_comments":[{"comment":"The upper bound in Eq. (8) does not follow from Theorem 8. Substituting Eq. (6) and Eq. (7) into the ratio that bounds γ gives 6(N+1)(N+2)(N^2+N-4) / ((N-2)(N+3)(N+4)(N+5)), which tends to 6 as N grows, not to 0. Eq. (8) contains an extra factor N in the denominator. For the displayed graph with N=6, this ratio is about 3.22, so it imposes no constraint on γ, which is at most 1. Thus the family of graphs in Fig. 2 does not establish γ→0, and the paper's headline claim is not supported.","section":"Theorem 9 and Eq. (8)"},{"comment":"The printed formula for ω_jk below Fig. 14 yields a negative effective resistance for admissible parameters, for example N=6, k=1 gives approximately -1.05, which is impossible for a resistance. The formula is also inconsistent with the subsequently claimed difference ω_ik - ω_jk = 2(2k-N-3)/(N^2+N-4); substituting N=6, k=1 into the two printed expressions gives a different value. Since this difference is used to derive Eq. (19) and hence Eq. (7), the proof of Theorem 8 must be redone before Eq. (7) can be accepted.","section":"Appendix A, expression for ω_jk"},{"comment":"As printed, Eq. (3) uses the path-graph resistance value (N-1 choose 3), but the Kirchhoff index of the path graph P_N is (N^3-N)/6 = (N+1 choose 3). With the printed constant, the denominator of Eq. (3) vanishes for N=5 and the normalized resistance is not bounded between 0 and 1. This normalization is used throughout the paper; it should be corrected, even though the ratio argument is unaffected by the linear rescaling.","section":"Eq. (3) and surrounding text"}],"minor_comments":[{"comment":"The algorithm initializes r_G,opt to +∞ and then updates only when r_G(G_i ∪ W_j) > r_G,opt; since no finite value exceeds ∞, the algorithm never selects a link. The sentinel should be -∞ for a maximization problem. Line 12 also uses the undefined variable Vopt instead of Wopt.","section":"Algorithm 1, lines 3 and 8"},{"comment":"The caption calls the N=9 and N=10 entries 'lower bounds', but if those values were obtained from a random subset of graphs, the reported minimum efficiency over the sample is an upper bound on the true minimum, not a lower bound. In addition, the text says only N≤8 graphs were checked exhaustively while the table header lists exact counts for N=9 and N=10; the distinction between exhaustive and sampled results should be stated clearly.","section":"Table 1 and Section 5"},{"comment":"There are several small presentation issues: the normalization constant in Eq. (3) appears to be a typo for (N+1 choose 3); the phrase 'for all k ≤ i' in the proof of Eq. (6) should presumably read 'for all k ≠ i,j'; and the variable name Vopt in Algorithm 1 should be Wopt.","section":"Notation and typos"}],"recommendation":"reject","confidential_remarks":"The paper's main contribution is invalid as written: Theorem 9's bound is not a consequence of Theorem 8, and the actual quotient for the proposed graph family tends to 6, so the construction gives no information about γ. This is a load-bearing error, not a local typo, and re-establishing γ→0 would require a different construction or a substantially corrected proof. The empirical small-graph results might be salvageable as a separate experimental note, but they do not compensate for the failure of the central theoretical claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper's claimed gamma -> 0 result is not established by its own equations. Divide Eq. (6) by Eq. (7) and you get 6(N+1)(N+2)(N^2+N-4) / [(N-2)(N+3)(N+4)(N+5)], which tends to 6, not 0. The printed Eq. (8) has an extra N in the denominator. So for the specific S, R, v in Fig. 2, gamma is only shown to be <= about 3.2 at N=6 and <= ~6 asymptotically, which is vacuous. The stress-test note is correct.\n\nAppendix A also has real sign errors. The printed omega_jk is negative for N=6, k=1, and it is inconsistent with the omega_ik - omega_jk formula used in the sum. These look mechanical, but they sit directly under the main theorem.\n\nCredit where due: the paper frames the right question — prior work only showed gamma<1, so strengthening to gamma->0 is the natural next step. The graph family is a plausible construction, and the small-graph brute-force comparison is an honest sanity check. The literature review is competent and cites the right results (Das-Kempe, Bian et al., Liu et al.).\n\nSoft spots: the empirical section is a lower-bound anecdote without code or data; the 0.878 efficiency is not connected to the gamma argument. But the main problem is the algebra. If the authors can correct the computation and find a family where the ratio of gains genuinely decays, the paper could be a useful short contribution. As written, the central claim is unsupported.\n\nRecommendation: I would not send this to peer review in its current form. It deserves a desk reject with an invitation to resubmit after fixing the appendix and the Theorem 9 derivation. I would not cite it.","headline":"The claimed gamma->0 result is not supported by the paper's own equations: dividing Eq. (6) by Eq. (7) gives a ratio tending to 6, not 0, and the appendix has sign errors under the main proof.","tokens_in":15311,"tokens_out":4779,"would_cite":false,"duration_ms":41700,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C82","05C50","90C27","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs a graph family on 2N nodes for which the submodularity ratio of normalized effective graph resistance tends to zero, so greedy link addition has no guaranteed approximation quality.","keywords":["effective graph resistance","Kirchhoff index","network augmentation","submodularity ratio","generalized submodularity","greedy algorithm","k-GRIP","graph robustness"],"falsifier":"Compute the four effective graph resistances in Theorem 8 for N=6 directly from the Laplacian eigenvalues using R_G = N * sum_{i=2}^N 1/mu_i, and form the ratio of the two gains. If the ratio does not match the right-hand side of Eq. (8), or if for larger even N the ratio does not tend to zero, the claimed collapse of the greedy guarantee is not established.","tokens_in":14308,"feed_emoji":"📉","tokens_out":6427,"duration_ms":58840,"temperature":0.7,"pith_summary":"The paper tries to establish that the problem of choosing k links to minimize effective graph resistance, already known to be NP-hard, is not merely non-submodular but fails generalized submodularity in a way that destroys the standard greedy performance guarantees. It builds a family of graphs on 2N nodes where the submodularity ratio gamma is at most roughly 6/N, hence approaches zero; at gamma equal to zero, known bounds only say the greedy solution is nonnegative, which is no guarantee at all. The same family shows that the greedy algorithm can be suboptimal, and exhaustive and random experiments on small graphs find an efficiency as low as 0.878 already for N=10 and k=3. A reader should care because greedy is the practical method for this NP-hard augmentation problem, and the result shows its worst-case behavior is not controlled by submodularity-based theory.","feed_headline":"Greedy network hardening can lose its quality guarantee","feed_subtitle":"A constructed graph family drives the submodularity ratio to zero, erasing approximation bounds; greedy is already suboptimal at 10 nodes.","key_machinery":"The central object is the submodularity ratio gamma, the largest constant such that the marginal gain of adding an element v to a small set S is at least gamma times the marginal gain of adding v to a larger set R. For f equal to the normalized effective graph resistance r_G, the paper computes the ratio of two marginal gains for one specific triple (S empty, v, R) on a family of graphs. The computation is carried by electrical-network reductions: Theorem 11 of the cited resistance-distance paper gives the change in effective graph resistance under an edge-weight change, and series, parallel, and $\\Delta$-Y transformations on the planar augmented graph produce closed forms for the resistances omega_ij, omega_ik, and omega_jk. The identity doing the work is the exact quotient of the two resistance differences in Theorem 8, which yields the upper bound on gamma.","core_discovery":"The central claim is that k-GRIP for the normalized effective graph resistance is not generalized submodular. For the graph formed by taking a complete bipartite graph K_{2,N-2}, choosing nodes i and j in the two-node part, and attaching a path of length N/2 to each of two selected nodes in the other part, the paper proves, with S empty, v equal to the edge (i,j), and R the two edges that connect the far ends of the paths back to i and j, that the gain from adding v alone is 4/(N-2) while the gain from adding v after R is 2(N+3)(N+4)(N+5)/(3(N+1)(N+2)($N^{2}$+N-4)). The quotient of these gains gives an upper bound gamma <= 6(N+1)(N+2)($N^{2}$+N-4)/[(N-2)N(N+3)(N+4)(N+5)] ~ 6/N, which tends to zero. Since the performance bounds in the paper depend directly on gamma, a gamma arbitrarily close to zero implies that the greedy algorithm's solution quality cannot be guaranteed. The paper additionally reports small-graph experiments where the greedy efficiency eta = R_G(optimal)/R_G(greedy) reaches a minimum of 0.878 for N=10 and k=3.","pith_inferences":["The same counterexample construction could plausibly transfer to other Laplacian-spectrum-based robustness metrics, since the added edge (i,j) has a small effect on the original graph but a large effect after the set R is present; testing gamma for algebraic connectivity or spanning-tree counts would be a direct extension.","A natural next step is to scale up the N=10 worst-case graph to see whether the greedy efficiency eta continues to drop; the gamma-to-zero family suggests arbitrarily bad greedy behavior may be constructible, though the paper does not prove it.","Even though worst-case guarantees vanish, average-case or instance-specific performance may still be acceptable; the paper's experiments do not rule that out, so a distributional analysis of greedy errors would be a useful test.","The paper's counterexample uses only one triple (S empty, v, R) to bound gamma, so computing the exact gamma for larger instances might reveal even stronger non-submodularity, which would further narrow the space of possible guarantees."],"forward_implications":["For k-GRIP with effective graph resistance, the greedy algorithm has no guaranteed approximation ratio derived from submodularity or generalized submodularity; only problem-specific bounds could apply.","As the constructed graph family grows, gamma becomes arbitrarily small, so the practical heuristic's worst-case performance is not controlled by the existing gamma-dependent bounds.","The small-graph experiments show that greedy solutions are already suboptimal at modest sizes, so exact methods or alternative heuristics may be needed when solution quality matters.","Any future guarantee for greedy link addition must exploit structure beyond set-function submodularity, such as spectral properties of the Laplacian or electrical-network structure.","The efficiency value 0.878 provides a concrete benchmark: any proposed improvement to the greedy rule must be tested against this known worst case for N=10 and k=3."],"supporting_citations":[{"why":"Shows the normalized effective graph resistance is not submodular, the starting point this paper strengthens.","marker":"[34]"},{"why":"Introduces the submodularity ratio gamma used to define generalized submodularity.","marker":"[10]"},{"why":"Supplies the gamma- and curvature-dependent greedy bound that the counterexample invalidates.","marker":"[2]"},{"why":"Supplies the improved gamma-dependent greedy bound that also gives no guarantee when gamma tends to zero.","marker":"[21]"},{"why":"Provides the resistance-change formulas used in Appendix A to compute the gains in Theorem 8.","marker":"[40]"},{"why":"Justifies the Delta-Y reduction used to compute one of the effective resistances in the planar augmented graph.","marker":"[36]"},{"why":"Proves NP-hardness of k-GRIP for effective graph resistance, motivating the greedy heuristic.","marker":"[19]"},{"why":"Gives the original (1 - 1/e) greedy guarantee for submodular functions, the benchmark the paper compares against.","marker":"[24]"},{"why":"Defines effective graph resistance and its Laplacian eigenvalue formula used for computations.","marker":"[11]"}],"fun_headline_variants":["Greedy link addition loses quality bound in new graph family","Submodularity ratio crashes, greedy link addition unguaranteed","Greedy for minimal resistance? Even 10 nodes break it","Link addition optimization: submodularity ratio approaches zero","Greedy link addition: performance bound vanishes on constructed graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper bound on gamma rests on the closed-form effective-resistance formulas in the appendix being correct; the printed derivation of one intermediate resistance contains sign inconsistencies, so the conclusion holds only if the corrected algebra reproduces those formulas.","fun_headline_variants_meta":{"raw":{"variants":["Greedy link addition loses quality bound in new graph family","Submodularity ratio crashes, greedy link addition unguaranteed","Greedy for minimal resistance? Even 10 nodes break it","Link addition optimization: submodularity ratio approaches zero","Greedy link addition: performance bound vanishes on constructed graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2907,"prompt_tokens":1074,"completion_tokens":1833,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":690,"completion_tokens_details":{"reasoning_tokens":1745}},"tokens_in":690,"tokens_out":1833,"duration_ms":10340,"temperature":1.0,"reasoning_tokens":1745,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:52:17.796174+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the four effective graph resistances in Theorem 8 for N=6 directly from the Laplacian eigenvalues using R_G = N * sum_{i=2}^N 1/mu_i, and form the ratio of the two gains. If the ratio does not match the right-hand side of Eq. (8), or if for larger even N the ratio does not tend to zero, the claimed collapse of the greedy guarantee is not established.","supporting_citations":[{"cited_title":"Topology design for optimal network coherence","cited_arxiv_id":null,"evidence_quote":"Shows the normalized effective graph resistance is not submodular, the starting point this paper strengthens."},{"cited_title":"Guarantees for Greedy Maximization of Non-submodular Functions with Applications","cited_arxiv_id":"1703.02100","evidence_quote":"Supplies the gamma- and curvature-dependent greedy bound that the counterexample invalidates."},{"cited_title":"original graph","cited_arxiv_id":null,"evidence_quote":"Provides the resistance-change formulas used in Appendix A to compute the gains in Theorem 8."},{"cited_title":"Truemper","cited_arxiv_id":null,"evidence_quote":"Justifies the Delta-Y reduction used to compute one of the effective resistances in the planar augmented graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves NP-hardness of k-GRIP for effective graph resistance, motivating the greedy heuristic."},{"cited_title":"Ellens, F","cited_arxiv_id":null,"evidence_quote":"Defines effective graph resistance and its Laplacian eigenvalue formula used for computations."}],"review_version":1}