{"id":"e1adef49-f932-4580-a33a-017ebb81045b","arxiv_id":"2607.17005","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"The rooted terminal-only Manhattan cost-radius spanning-tree decision problem is weakly NP-complete, and the balanced height partition achieves both cost and radius within factor 2 of the independent optima.","lead":"This paper proves that the terminal-only Manhattan cost-radius routing-tree problem is weakly NP-complete, resolving a 1992 open question, and gives a simple height-partition construction with a (2,2) cost-radius guarantee. It also releases HP-RCRST, a deterministic multi-mode solver that Pareto-dominates the published-method union on 23 of 28 development instances, as a case study in using LLM agents to reopen dormant algorithmic problems.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the central theoretical claims and the explicitly scoped empirical claims survive scrutiny.","rationale":"The reader's weakest assumption—the terminal-only boundary—is a genuine and explicit scope limitation, but I do not consider it a load-bearing attack because the paper consistently frames its theorems, algorithm, and comparisons within that model and repeatedly disclaims transfer to Steiner-allowed variants. My independent reading of the NP-completeness reduction found no gap in the reverse direction: the cut-forcing lemmas handle arbitrary complete-graph edges, the bridge inequality is justified by the unique left-to-right path crossing, and the bit accounting is polynomial. The height-partition theorem's disjoint-charge argument is valid, and the factor-two boundary is stated as an arbitrary-metric lower bound, not a planar-L1 impossibility. The empirical Pareto claims are honestly scoped to the development set, with the paper explicitly stating that those instances were used for tuning and that held-out data support only mode ordering, not baseline-dominance generalization. The absence of formal verification of the main theorems and the weak NP-hardness status are limitations already acknowledged in the manuscript and do not change the verdict. I therefore find no reason to alter the reader's ACCEPT verdict.","tokens_in":29380,"tokens_out":34767,"duration_ms":315261,"concrete_test":"Re-derive Lemma A.3's bridge inequality from scratch without assuming path x-monotonicity on bridges, then verify it by exhaustive enumeration of all feasible trees on small reduction instances (n≤4 Partition inputs). If any feasible tree satisfying the budgets violates W+2A≥X, the reverse direction of Theorem 4.1 would need repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the theoretical core in good faith and did not find a load-bearing flaw. Theorem 4.1's reverse direction is supported by cut-forcing lemmas A.1–A.3: the budget argument rules out extra crossings on interblock cuts, nested-cut uniqueness forces consecutive-block bridges, and the bridge inequality W+2A≥X is valid once one notes that the unique path edge crossing each interblock cut must be traversed left-to-right. The height-partition proof of Theorem 4.2 is sound: the residual-height invariant is maintained by induction, the disjoint-charge sets Q_v have total weight at most M, and the length and radius bounds both follow. The arbitrary-metric factor-two lower bound in Appendix B is also internally consistent. The main limitations are explicitly stated: the model is terminal-only, the NP-hardness is weak, the main theorems are not Lean-formalized, and the Pareto-dominance claim is confined to the 28 development instances. These are real scope boundaries, but they do not threaten the claims as formulated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper revisits the rooted, terminal-only Manhattan cost–radius spanning-tree problem: find a spanning tree of a complete terminal graph, with Manhattan edge lengths, satisfying total cost bound B and root-to-terminal radius bound D. It claims three main theoretical results: (1) weak NP-completeness of the decision problem via a polynomial-time reduction from Partition (Theorem 4.1, Appendix A); (2) a continuous cost–radius tradeoff for a bottom-up height partition of a rooted MST, giving rho(A_H) <= (1+Delta/H, 1+H/Delta) and in particular a (2,2) guarantee at H=Delta (Theorem 4.2, Appendix B); (3) an arbitrary-metric lower bound showing that no single tree can have a universal common factor below 2 (Theorem B.4). The paper then presents HP-RCRST, a deterministic solver with one certified mode carrying the (2,2) guarantee and three empirical modes, and evaluates it on 28 development instances, 50 held-out instances, and scaling runs to n=2048. The paper is explicit that the model is terminal-only, that NP-hardness is weak, that the main theorems are not Lean-formalized, and that the empirical frontier claims are scoped to the development set.","tokens_in":29578,"tokens_out":32022,"duration_ms":305836,"significance":"If the results hold, they settle a complexity question left open in 1992 in the weak sense, give an unusually simple certified (2,2) construction, and provide a reproducible solver with careful exact remeasurement. The strengths are real: the NP-completeness reduction is self-contained and includes the cut-forcing lemmas, the bridge inequality, and bit-complexity accounting; the height-partition proof rests on a valid disjoint-charge argument over MST edges; the arbitrary-metric lower bound is internally consistent; and the empirical claims are explicitly limited and backed by exact integer validation. The paper also transparently states which parts are not formalized or not released. I found no load-bearing flaw in the central derivations.","major_comments":[],"minor_comments":[{"comment":"The displayed equation L = X + 2A + 4(S-A) = X + 3S is algebraically false for general A; it becomes X + 4S - 2A, which equals X + 3S only after substituting A = S/2. The main text in Section 4.1 gives the correct form L = X + 4S - 2A = B. Please correct or rephrase the appendix line to avoid confusion in a proof appendix.","section":"Appendix A.3, Eq. (13)"},{"comment":"The telescoping expression H_b = X - 3A+ + 3A- assumes every bridge is traversed left-to-right on P. This follows from Lemma A.1's c_P = 1 on each interblock cut, but the appendix does not state it explicitly. Add a sentence making this justification clear.","section":"Appendix A.4, bridge inequality"},{"comment":"The mode name is written both as 'qality' and 'quality'. Standardize the spelling, since the inconsistency is distracting in pseudocode and policy tables.","section":"Sections 5.4, Alg. 3, C.4"},{"comment":"The direct comparisons against PD-II and the terminal MSPD/MSS portfolio are reported in the text but the corresponding per-baseline tables are not shown; the reader must infer them from the raw-data description. A small table or pointer to the exact rows would improve verifiability.","section":"Section 6.2 / Appendix D"},{"comment":"Several references, especially [22], [27], and [30], are to very recent or non-archival sources. Please confirm they are publicly available and stable before final publication, or mark them as preprints.","section":"References"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is technically sound: the central theorems, especially Theorem 4.1 and Theorem 4.2, survive close reading, and the empirical claims are carefully scoped. The requested changes are all presentational. The LLM-assisted process framing is unusual for a CS-AR paper, but the paper does not overclaim what the LLM did: the mathematical proofs and the final solver are independently auditable, and the artifact boundary is stated precisely. I support acceptance after minor revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading. The central result — weak NP-completeness of the terminal-only Manhattan cost-radius spanning-tree problem — is argued in detail, and the height-partition (2,2) guarantee is simple and correct. The reduction from Partition includes the reverse-direction cut-forcing lemmas and the bridge inequality; those arguments hold up. The height-partition proof uses a valid disjoint-charge argument, and the tradeoff envelope (x−1)(y−1)=1 is genuinely tighter than KRY/LAST's per-terminal envelope for global radius. The factor-two lower bound for pure metric arguments is a nice boundary result.\n\nThe paper is unusually honest about scope. It states the terminal-only, no-Steiner, single-source model up front, and it does not claim the theorem transfers to Steinerized routing. The empirical claims are carefully divided: the Pareto dominance over the published union is confined to the 28 development instances, the paper says so, and the held-out results support a monotone mode ordering but not the same dominance. The code, frozen results, and Lean snapshot for auxiliary lemmas are real evidence; the paper also explicitly says the main theorems are not formally verified. That is the right way to present a reproducibility subset.\n\nSoft spots are proportionate. The NP-hardness is weak, so strong hardness and pseudopolynomial algorithms remain open. The (2,2) guarantee is a global-radius bound, not per-terminal stretch, so it does not replace KRY/LAST. The historical claim that the 1992 question was open could use one more sentence of literature verification, but the cited prior work does appear not to contain this reduction. The LLM-process sections are a bit long, but they are cleanly separated from the mathematical and empirical claims.\n\nWho is this for? VLSI physical-design researchers and anyone working on shallow-light or bicriteria spanning trees. The theory section is self-contained enough for a theory reader, and the empirical section is appropriately qualified.\n\nMy recommendation: send it to peer review. The math is sound, the scope is honest, and the paper settles a specific open question. I would accept after minor revision, mostly asking for a sharper discussion of the Steiner boundary and a slightly more careful check of the 'open since 1992' attribution.","headline":"A careful, honestly-scoped paper that settles a real open complexity question and gives a clean (2,2) tradeoff; the terminal-only boundary is the main caveat, but the paper never overclaims.","tokens_in":30091,"tokens_out":2322,"would_cite":true,"duration_ms":24331,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68R10","05C05","68W25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper settles a 1992 open problem in VLSI routing: the terminal-only Manhattan cost–radius spanning-tree problem is NP-complete, and a simple height partition of a rooted MST yields a tree whose total length and root-to-terminal radius","keywords":["Prim-Dijkstra routing","cost-radius spanning tree","bicriteria approximation","weak NP-completeness","Manhattan metric","height partition","VLSI routing","performance-driven routing"],"falsifier":"Run HeightPartition on any finite metric instance and independently remeasure the output: the theorem predicts R ≤ Δ+H and (L−M)H ≤ MΔ, so a single violation falsifies Theorem 4.2; for the complexity claim, a pseudopolynomial exact algorithm for the terminal-only Manhattan decision problem would contradict the weak NP-hardness result.","tokens_in":29226,"feed_emoji":"🌳","tokens_out":9045,"duration_ms":91930,"temperature":0.7,"pith_summary":"This paper revisits Prim–Dijkstra routing: given terminals in the Manhattan plane, a single root, and a complete graph of possible edges, find a spanning tree with bounded total wirelength L and bounded root-to-sink path length R. The author proves that the natural decision version—does a tree exist with L ≤ B and R ≤ D?—is NP-complete, via a weak reduction from integer Partition, answering a question left open since 1992. On the positive side, the paper gives a bottom-up height partition of a rooted MST that returns, for any threshold H, a tree with R ≤ Δ + H and (L − M)H ≤ MΔ, where M is the MST length and Δ the maximum root distance; choosing H = Δ yields the balanced guarantee L ≤ 2M and R ≤ 2Δ. The paper packages this into HP-RCRST, a deterministic solver whose certified mode always contains such a (2,2) tree and whose empirical modes, on the paper's benchmark set, Pareto-dominate the union of published methods on 23 of 28 instances and tie on the other five. A sympathetic reader should care because the work closes a long-standing complexity question, supplies an unusually simple certified approximation for a practical routing objective, and illustrates a reusable workflow for reopening dormant algorithmic problems.","feed_headline":"Prim-Dijkstra complexity settled: NP-complete, with a (2,2) tree","feed_subtitle":"A new proof and solver certify a tree whose total length and root-to-sink delay each stay within a factor of two.","key_machinery":"The load-bearing object is the rooted complete-terminal Manhattan graph with the two objectives L(T)=sum of edge lengths and R(T)=max root-to-terminal path length, normalized against the MST length M and the maximum root distance Δ. For hardness, the machinery is an explicit Partition gadget whose coordinate and budget choices force a feasible tree to correspond exactly to a subset of sum S/2; the proof uses interblock prefix-cut forcing and a bridge inequality to eliminate all noncanonical complete-graph edges. For approximation, the machinery is Algorithm 1 (HeightPartition): in postorder, keep a parent edge if the residual height stays within H, otherwise replace it with a direct root edg","core_discovery":"The central discovery is that the terminal-only Manhattan version of the bounded-cost bounded-radius spanning-tree problem is computationally hard in the weak sense, yet admits a linear-time, MST-based construction with a balanced bicriteria guarantee. The reduction from Partition is explicit and numerical: terminals are placed at integer coordinates so that any feasible tree encodes a subset summing to S/2, and a cut-forcing argument rules out every other complete-graph edge. The approximation result is the height partition: process a rooted MST bottom-up, cutting a parent edge whenever the accumulated subtree height would exceed H, and reconnecting that subtree root directly to the source.","pith_inferences":["Inference: Because the hardness reduction is weak and numerical, a pseudopolynomial exact algorithm for the terminal-only Manhattan problem is a plausible research target; the explicit coordinate construction shows exactly where bit sizes matter.","Inference: The height-partition charging scheme—charging each shortcut to the residual component that violated the threshold—is a transferable amortization template for other bicriteria spanning-tree problems in metric spaces.","Inference: The paper's empirical split between a good central compromise and weak frontier shoulders suggests a design principle beyond this instance: a certified one-parameter family is a reliable backbone, but articulating a full tradeoff curve requires search that can change MST topology.","Inference: The observation that many MSTs share the same length but different root radii points to a concrete improvement: searching over MST tie structures, rather than thresholds on one canonical MST, may close much of the remaining gap between certified and empirical modes."],"forward_implications":["The decision problem is weakly NP-complete: no polynomial-time exact algorithm exists for the rooted, terminal-only Manhattan cost-radius problem unless P=NP, closing the 1992 question.","For every H>0, HeightPartition returns a tree with normalized guarantee (L/M, R/Δ) ⪯ (1+Δ/H, 1+H/Δ); the balanced choice H=Δ gives a single tree with L≤2M and R≤2Δ.","The construction runs in linear time after the MST is rooted, so a fast deterministic router can carry a certified (2,2) guarantee; HP-RCRST's certified mode always emits such a tree or an exact Pareto dominator.","In arbitrary metric spaces, no single tree can be certified with common factor below two by these arguments (trunk-and-arms lower bound); beating two requires planar L1 structure or a portfolio of trees, both left open.","On the paper's 28 development instances, the stronger empirical modes of HP-RCRST Pareto-dominate the union of published methods on 23 cases and tie on the remaining five; its certified mode does not dominate that union but offers the theorem-backed witness."],"fun_headline_variants":["Prim-Dijkstra NP-complete, yet a 2x balanced tree is achievable","Weak NP-hardness proven for terminal-only Prim-Dijkstra routing","New solver HP-RCRST tops 23 of 28 VLSI cases with (2,2) bound","Balanced (2,2) guarantee: classical VLSI problem reopened and solved"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"All theorems assume terminal-only spanning trees—no Steiner points—with a single root and the same Manhattan metric used for both total cost and path length; if the intended VLSI application allows Steiner vertices, the NP-completeness result and the (2,2) construction do not transfer as stated.","fun_headline_variants_meta":{"raw":{"variants":["Prim-Dijkstra NP-complete, yet a 2x balanced tree is achievable","Weak NP-hardness proven for terminal-only Prim-Dijkstra routing","New solver HP-RCRST tops 23 of 28 VLSI cases with (2,2) bound","Balanced (2,2) guarantee: classical VLSI problem reopened and solved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000149,"raw_usage":{"total_tokens":991,"prompt_tokens":669,"completion_tokens":322,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":413,"completion_tokens_details":{"reasoning_tokens":229}},"tokens_in":413,"tokens_out":322,"duration_ms":4338,"temperature":1.0,"reasoning_tokens":229,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T19:18:17.781264+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run HeightPartition on any finite metric instance and independently remeasure the output: the theorem predicts R ≤ Δ+H and (L−M)H ≤ MΔ, so a single violation falsifies Theorem 4.2; for the complexity claim, a pseudopolynomial exact algorithm for the terminal-only Manhattan decision problem would contradict the weak NP-hardness result.","supporting_citations":[],"review_version":1}