{"id":"aa35e3b9-1f62-4251-9e3c-782ee2ad421f","arxiv_id":"2506.23638","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Two new algorithms, AugmentedGreedy and RandomizedRounding, give the first unconditional m-approximation and a simple O(n log n)-approximation for the most general decoupled freeform spanner problem.","lead":"This paper presents two simple approximation algorithms for the most general graph spanner problem, where each edge has independent cost and length and each node pair has its own distance requirement. The first gives an unconditional m-approximation, and the second gives an O(n log n)-approximation using far simpler tools than the previous state of the art.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant mathematical objection identified; main theorems are sound, and the alleged exponent typo is not an error.","rationale":"The central claims survive scrutiny. The m-approximation and the O(n log n) randomized rounding are correctly proved, and the only reason the reader gave for CONDITIONAL (an exponent typo in the comparison to [33]) is, on closer calculation, not a typo: the ratio of the new guarantee to the previous one is n^{1/5−ε} log n, which is O(n^{1/5−ε′}) after absorbing the logarithmic factor into a slightly smaller ε′. Since the paper uses ε generically, the sentence 'match it up to a factor of O(n^{1/5−ε})' is acceptable. The polynomial-δ assumption is stated and is inherent to the LP size; it does not undermine Theorem 15. No further load-bearing concern was identified, so the conditional should be lifted.","tokens_in":19649,"tokens_out":38112,"duration_ms":437715,"concrete_test":"Recompute the ratio γ / eO(n^{4/5+ε}) for δ = n^c using γ ≤ ln(n^3(δ+2)^{n−2}); verify that it is O(n^{1/5−ε′}) for some ε′>0, confirming the abstract's comparison. As a secondary check, solve (MCF) on a small random instance (n=4, δ=3), round with γ, and compare empirical infeasibility frequency with the 1/n union-bound estimate.","verdict_should_be":"ACCEPT","load_bearing_attack":"I find no load-bearing flaw in Theorem 3 or Theorem 15. Theorem 3's threshold argument is valid: the minimal feasible weight threshold ŵ satisfies ŵ ≤ OPT, so the final spanner has weight at most |E[ŵ]|·ŵ ≤ m·OPT. Theorem 15's rounding proof is also sound: every ascending u0vδ-cut carries one unit of flow, giving ∑_{e∈E_c} x_e ≥ 1; a union bound over μ|K| cuts with γ = ln(nμ|K|) bounds failure probability by 1/n, and E[w(H)] ≤ γ·OPT follows from LP optimality. The reader's 'exponent typo' does not land: γ / eO(n^{4/5+ε}) = O(n^{1/5−ε} log n), and since log n is absorbed by slightly reducing ε, the abstract's 'up to a factor O(n^{1/5−ε})' is standard, not a sign error. The polynomial-δ assumption is explicit and only affects the O(n log n) regime, not the m-approximation.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the decoupled freeform spanner problem, in which a directed or undirected graph has independent edge weights and edge lengths and arbitrary pairwise distance demands, and the goal is to find a minimum-weight feasible subgraph. It presents two approximation algorithms. AugmentedGreedy first binary-searches for the smallest weight threshold w_hat such that the weight-restricted subgraph G[w_hat] is feasible, then runs the classic Greedy algorithm on G[w_hat]. Theorem 3 proves an unconditional m-approximation for all decoupled freeform spanner problems, and Corollaries 5, 7, and 8 argue that known Greedy size and lightness guarantees are retained for coupled multiplicative, geometric, and unit-length additive spanners. RandomizedRounding solves a standard multicommodity flow LP on a layered delta-extension of the graph and rounds the fractional solution with probabilities proportional to gamma times the LP values. Theorem 15 gives an expected ln(n mu |K|) in O(n log n) approximation under integer lengths and polynomially bounded distance demands, and Corollary 18 gives an O(log n) approximation for constant-bounded demands on bounded-degree graphs.","tokens_in":19829,"tokens_out":25465,"duration_ms":277348,"significance":"If the results stand, they substantially simplify the state of the art for the most general spanner formulation. The m-approximation is the first unconditional guarantee that places no restrictions on weights, lengths, or distance demands, and it is obtained by a very simple modification of Greedy. The O(n log n) randomized rounding result matches the only previous sublinear approximation for this setting up to lower-order factors, while replacing a pipeline of heavy subroutines with a single LP plus a direct rounding argument. The paper also provides the first logarithmic approximation for constant-distance-demand instances on bounded-degree graphs, including directed graphs. The proofs of the two main theorems are clear, self-contained, and involve no fitted parameters; the integer-length and polynomially-bounded-demand assumptions for RandomizedRounding are explicitly stated and coincide with the assumptions of the prior work it improves on. The main limitation that the O(n log n) ratio depends on polynomially bounded delta is properly declared in Section 4 and in Tables 2, so it does not undermine the contribution.","major_comments":[],"minor_comments":[{"comment":"The comparison statement 'match it up to a factor of O(n^{1/5-eps})' is easy to misread, because the prior guarantee is written as eO(n^{4/5+eps}) and the new ratio is O(n log n); reusing epsilon on both sides makes the exponent appear to have the wrong sign. Please rephrase, for example by writing O(n^{1/5+eps}) or by explicitly saying that epsilon is re-parameterized to absorb the logarithmic factor.","section":"Abstract and Section 4"},{"comment":"In Eq. (8), the inequality d_H0(u,z)+d_H0(z,v) > delta(u,v)+2 is presented as a consequence of the violated demand d_H0(u,v) > delta(u,v), but the triangle inequality alone gives only d_H0(u,z)+d_H0(z,v) > delta(u,v). The extra '+2' needs a justification using z's adjacency to the added path and the order in which demands were processed; please expand this step.","section":"Appendix B, Eq. (8)"},{"comment":"In the proof of Observation 2, the assertion that a minimum st-path P in the demand graph can be chosen with P subset of K' is not immediate; a short explanation, for instance by replacing each non-metric demand edge with its witnessing path in D, would improve readability.","section":"Observation 2 proof"},{"comment":"The phrase 'expected approximation ratio gamma' is slightly ambiguous, since Algorithm 3 may return an infeasible subgraph with probability at most 1/n. Please state explicitly that E[w(H)] <= gamma * OPT and that H is feasible with probability at least 1 - 1/n.","section":"Theorem 15 and Algorithm 3"},{"comment":"The abstract contains a typo: 'two surprisingly simple approximations algorithms' should read 'two surprisingly simple approximation algorithms'.","section":"Abstract"}],"recommendation":"minor_revision","confidential_remarks":"The two main theorems are, in my reading, correct, and the comparison with Grigorescu et al. is fair. The manuscript fits the scope of the journal well. My substantive requests are local: clarifying the appendix potential step and the abstract's comparison exponent. These should not require new technical ideas, so I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper is sound, and the reader's CONDITIONAL is too cautious. I read Theorems 3 and 15 closely; both proofs hold. The flagged \"exponent typo\" does not land. Their ratio is O(n log n) against the previous Õ(n^{4/5+ε}), a gap of n^{1/5}·polylog; claiming to match \"up to O(n^{1/5−ε})\" is the standard epsilon-absorption convention. Loose shorthand, maybe; an error, no.\n\nWhat is actually new: Theorem 3 is the first approximation guarantee of any kind for the fully general decoupled freeform spanner problem — arbitrary weights and lengths, directed or undirected, no integrality. It is non-trivial: taking all edges is not an m-approximation when weights are unbounded relative to OPT, and the threshold argument is what fixes it. The idea (binary search the smallest weight threshold whose filtered graph is feasible; that threshold is a lower bound on OPT; the filtered graph weighs at most m·OPT) is simple enough to look like folklore, but it is absent from the literature, and keeping Greedy's structural guarantees via the second phase is a real addition. Section 4's layered-graph rounding is a genuine generalization of Dodis-Khanna: putting lengths into layer jumps rather than subdividing edges is exactly what handles freeform demands, and the ascending-cut argument is cleaner than the original. Appendix A's counterexample to the DK decoupled extension is useful scholarship. Corollaries 4-8 inherit from Althöfer, Coppersmith-Elkin, and Knudsen; I did not re-derive them, but they are secondary and not load-bearing.\n\nSoft spots, in proportion: the O(n log n) bound is asymptotically worse than Grigorescu et al.'s n^{4/5+ε} in the general case; the wins are simplicity, running time, and the first O(log n) on constant-degree, constant-demand instances. The integer-length / polynomially-bounded-δ assumption is load-bearing for the LP size, but it is explicit and shared with prior work — not a defect. The m-ratio is a foothold, not a strong bound, and the paper says so, even sketching tightness. The constant comparison with [33] (n ≤ 248,000, etc.) is heuristic; read it as motivation.\n\nAudience: spanner and network-design people, plus anyone who likes a clean proof that takes a general problem down from \"no guarantee\" to \"something.\" The citation pattern looks honest — the paper corrects an error in the work it builds on. It deserves a serious referee. My recommendation: send it to review; accept after minor polish (fix \"approximations algorithms\"; spell out the epsilon-absorption so the next reader does not trip the way this one did).","headline":"The main theorems hold up, the flagged 'exponent typo' is standard epsilon-absorption, and this is a clean paper that deserves real review.","tokens_in":20369,"tokens_out":26010,"would_cite":true,"duration_ms":241386,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"General spanner problems now have their first unconditional m-approximation.","keywords":["spanner","approximation algorithm","decoupled weight and length","freeform distance demands","greedy algorithm","randomized rounding","multicommodity flow","layered graph"],"falsifier":"Take a family of undirected decoupled freeform instances from the distance-preserver construction of [17] with m edges and run AugmentedGreedy: if the returned weight ever exceeds m times the optimum, Theorem 3 is false; conversely, the paper itself shows the analysis is tight on such instances. For RandomizedRounding, run Algorithm 3 on integer-length instances with delta = 2^n and a single terminal pair, and check whether the delta-extension LP can be formulated and solved in polynomial time; failure to scale to super-polynomial delta would confirm the polynomial-boundedness restriction is genuine.","tokens_in":19433,"feed_emoji":"📐","tokens_out":4568,"duration_ms":49017,"temperature":0.7,"pith_summary":"This paper attacks the most general spanner problem: edges may have independent weights and lengths, and every node pair may demand its own maximum distance. Previously, no nontrivial approximation was known for this full setting. The authors give two simple algorithms. AugmentedGreedy binary-searches the cheapest weight threshold that still permits a feasible spanner, then runs the classic Greedy heuristic on that subgraph; it achieves an unconditional m-approximation, where m is the number of edges, while preserving all of Greedy's known size and lightness guarantees. RandomizedRounding builds a layered graph extension, solves a standard multicommodity flow LP, and rounds it, yielding an O(n log n)-approximation for integer lengths and polynomially bounded distance demands, and an O(log n)-ratio on constant-bounded instances with bounded degree.","feed_headline":"First m-approximation for general spanner problems","feed_subtitle":"A two-phase greedy and layered-LP rounding nearly match the best known ratio with standard, implementable tools.","key_machinery":"Two mechanisms carry the results. First is a weight-threshold search: binary search over the distinct edge weights finds the smallest weight hat-w such that the subgraph consisting of edges of weight at most hat-w is already a feasible spanner; since hat-w lower-bounds the optimum, the at most m edges in that subgraph give the m-ratio, and running Greedy on it preserves Greedy's known guarantees. Second is the delta-extension, a layered graph with delta+1 copies of V in which arcs advance by l(e) layers and self-arcs advance one layer; distance demands become reachability between specified layer-copies, a multicommodity flow LP is solved and independently rounded with factor gamma, and feasibility is certified by a union bound over ascending cuts.","core_discovery":"The paper's central claim is that the most general spanner problem is approximable by elementary means. Theorem 3 states that AugmentedGreedy is an m-approximation for all (un)directed decoupled freeform spanner problems, with no restrictions on weights, lengths, or demands, and that it simultaneously retains the size and lightness guarantees Greedy enjoys for coupled multiplicative and basic additive spanners. Theorem 15 states that randomized rounding of a multicommodity flow LP on the delta-extension returns a feasible spanner with high probability, with expected approximation ratio gamma = ln(n·mu·|K|) = ln(n·(delta+2)^{n-2}·|K|), which lies in O(n log n); this matches the best known ratio up to a factor of O($n^{{1/5-epsilon}}$) using only standard tools.","pith_inferences":["In instances where weights and lengths are anti-correlated, the tighter bound O(n^{1+1/k} + sqrt(n)|E^>|) from Lemma 4 is likely the operative guarantee in practice, rather than the worst-case m.","The cut-based rounding in a layered extension is a transferable template: other constrained network design problems with distance requirements could be encoded as reachability in layered graphs and rounded the same way.","A natural next step is testing whether rational lengths can be scaled to integers with a bounded blow-up, which would extend Theorem 15 to all rational instances at a controlled cost in the ratio.","When the number of terminal pairs is constant and demands are constant-bounded, the modified rounding with gamma = ln(2 mu' |K|) achieves a constant expected ratio, a regime that appears in practical networks with few critical node pairs."],"forward_implications":["The m-ratio gives the first provable worst-case guarantee for decoupled freeform spanner instances, where practitioners previously had to force weights and lengths into a coupled format and rely on unproven heuristics.","The O(n log n) expected ratio nearly matches the best known O~(n^{4/5+epsilon}) guarantee for this problem class while using only a standard LP solver, making the algorithm implementable.","On constant-bounded distance demands with constant (out)degree, the same rounding scheme yields an O(log n) approximation, extending a regime that was previously limited to undirected unit-length multiplicative 2-spanners.","AugmentedGreedy inherits Greedy's size O(n^{1+1/k}) and lightness O(n/k) guarantees for coupled multiplicative alpha-spanners, and size O(n^{3/2}) for additive +beta-spanners with any constant beta >= 2."],"supporting_citations":[{"why":"Supplies the Greedy heuristic whose size and lightness guarantees AugmentedGreedy preserves.","marker":"[5]"},{"why":"Introduces the layered-graph multicommodity flow technique for unit-length multiplicative spanners that RandomizedRounding generalizes.","marker":"[21]"},{"why":"Provides the previously best known O~(n^{4/5+epsilon}) approximation for this problem class, the benchmark that Theorem 15 nearly matches.","marker":"[33]"},{"why":"Gives distance-preserver constructions that make the m-ratio tight and bounds the number of added edges in Lemma 4.","marker":"[17]"},{"why":"Establishes the size O(n^{3/2}) guarantee for additive +2-spanners that Corollary 8 extends to constant beta >= 2.","marker":"[36]"},{"why":"Justifies reducing multiplicative distance demands to adjacent node pairs, a step used throughout the paper.","marker":"[43]"}],"fun_headline_variants":["First unconditional m-approximation for general spanners","Simple greedy and rounding: first m-approx for spanner problems","Augmented Greedy achieves first m-approximation for general spanners","Elementary algorithms give first m-approximation for spanners","General spanners: first m-approx from simple LP rounding and greedy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The O(n log n) result assumes edge lengths are integers and the maximum distance demand delta is polynomially bounded in n; if delta is super-polynomial, the layered graph has delta+1 layers and both the running time and the rounding failure probability degrade, so the stated ratio no longer holds.","fun_headline_variants_meta":{"raw":{"variants":["First unconditional m-approximation for general spanners","Simple greedy and rounding: first m-approx for spanner problems","Augmented Greedy achieves first m-approximation for general spanners","Elementary algorithms give first m-approximation for spanners","General spanners: first m-approx from simple LP rounding and greedy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000904,"raw_usage":{"total_tokens":3944,"prompt_tokens":1055,"completion_tokens":2889,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":2799}},"tokens_in":671,"tokens_out":2889,"duration_ms":22874,"temperature":1.0,"reasoning_tokens":2799,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:38:23.723139+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a family of undirected decoupled freeform instances from the distance-preserver construction of [17] with m edges and run AugmentedGreedy: if the returned weight ever exceeds m times the optimum, Theorem 3 is false; conversely, the paper itself shows the analysis is tight on such instances. For RandomizedRounding, run Algorithm 3 on integer-length instances with delta = 2^n and a single terminal pair, and check whether the delta-extension LP can be formulated and solved in polynomial time; failure to scale to super-polynomial delta would confirm the polynomial-boundedness restriction is genuine.","supporting_citations":[{"cited_title":"Design networks with bounded pairwise distance","cited_arxiv_id":null,"evidence_quote":"Introduces the layered-graph multicommodity flow technique for unit-length multiplicative spanners that RandomizedRounding generalizes."},{"cited_title":"Approximation algorithms for directed weighted spanners","cited_arxiv_id":null,"evidence_quote":"Provides the previously best known O~(n^{4/5+epsilon}) approximation for this problem class, the benchmark that Theorem 15 nearly matches."},{"cited_title":"Additive spanners: A simple construction","cited_arxiv_id":null,"evidence_quote":"Establishes the size O(n^{3/2}) guarantee for additive +2-spanners that Corollary 8 extends to constant beta >= 2."},{"cited_title":"Sch¨ affer","cited_arxiv_id":null,"evidence_quote":"Justifies reducing multiplicative distance demands to adjacent node pairs, a step used throughout the paper."}],"review_version":1}