{"id":"b1f466ee-e979-4156-8c3f-7f6f024413cb","arxiv_id":"2607.25811","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New bicriteria approximation algorithms give polylog cost and O(log k) length slack for length-constrained Directed Steiner Tree and Forest on planar digraphs.","lead":"This paper gives approximation algorithms for two network design problems on planar directed graphs, where every connection must also be short in addition to being cheap. The algorithms come within a small polylogarithmic factor of optimal cost while only mildly relaxing the length limit.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unproven FPTAS substitution for NP-hard d^(h) oracles is load-bearing; without it, Theorems 1.1–1.3 lack polynomial-time guarantees.","rationale":"The central combinatorial machinery—mixture metric, separator recursion, one-path junction-tree lemma—appears sound after review. The one-path lemma in §4.1.3 handles the failure of the [14] re-routing property by using 2h-reachability, and the recursive cost accounting via disjoint E_L/E_R is credible. The weakest point is indeed the unproven substitution of an FPTAS for the NP-hard exact length-constrained distance computation. This is load-bearing: Algorithm 2's infeasibility checks and base case require d^(h) exactly, and the paper's assertion that a (1+ε)-approximation can be substituted is not accompanied by a proof that the recursion's correctness and cost bounds are preserved. I demonstrated concretely that the naive substitution can cause a false Infeasible return at the top level when γ=c(E); although this is likely repairable by increasing γ to a constant multiple and adjusting the threshold, the repair must be given explicitly. The same gap appears in the claimed polynomial-time solvability of the path LP via a dual separation oracle, since that separation is the restricted shortest path problem. These omissions do not appear to invalidate the ideas, but they are exactly the kind of missing support that justifies a conditional verdict. I therefore endorse the reader's CONDITIONAL verdict and recommend no change.","tokens_in":24519,"tokens_out":38852,"duration_ms":359095,"concrete_test":"Formally re-prove Lemma 3.3 and Lemma 3.4 with a (1+ε)-approximate d^(h) oracle, choosing γ=2c(E) at the root and comparing \\tilde d > γ. If the induction goes through only after enlarging the length slack to O((1+ε)h log k) or the cost bound to O((1+ε)log k), state the new constants explicitly; if a terminal with d^(h)=c(E) forces an Infeasible return despite γ=2c(E), the algorithm's feasibility lemma fails. Also provide the analogous approximate-separation analysis for the LP in §3.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2 (and h-frac-DST) invoke exact length-constrained distances d^(h)(s,t) in the infeasibility test and base case. Computing d^(h) is NP-hard; the paper's only response is a parenthetical claim that a (1+ε)-FPTAS substitution 'does not affect the approximation guarantees,' with no proof. This is not routine: with an approximate oracle \\tilde d∈[d,(1+ε)d], the top-level check \\tilde d>γ can falsely declare Infeasible for a terminal whose d^(h)=c(E) when γ=c(E). While adjusting γ to 2c(E) and constants may repair the proof, Lemmas 3.3 and 3.4 must be re-derived with the approximate distances, and the interaction with the guess/recursion structure is nontrivial. The same issue arises in §3.2: the path LP is solved via 'separation oracle on the dual,' but the dual separation is the restricted shortest path problem, which is itself NP-hard, so an approximate separation oracle is needed and its effect on the LP-competitive ratio is not analyzed. Because Theorems 1.1–1.3 all rely on these polynomial-time subroutines, the central claims are conditional without the missing proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies length-constrained versions of Directed Steiner Tree (LC-DST) and Directed Steiner Forest (LC-DSF) in planar digraphs, where edges have both costs and lengths and terminals must be connected by paths of length at most h. It claims a bicriteria (O(log k), O(log k))-approximation for LC-DST, an LP-competitive (O(log^2 k), O(log k)) approximation, and a bicriteria (O(log^6 k), O(log k))-approximation for LC-DSF. The technical approach adapts the planar separator framework of Friggstad–Mousavi for DST and the junction-tree framework of Chekuri–Jain for DSF, with a new one-path argument to handle length constraints. Theorems 1.1–1.3 are the central claims; if they hold, length-constrained directed Steiner problems inherit polylogarithmic approximability in planar digraphs.","tokens_in":24825,"tokens_out":29177,"duration_ms":269489,"significance":"If the results are correct, this is a meaningful contribution: it extends the recent line of polylogarithmic approximation algorithms for directed network design in planar digraphs to the length-constrained setting, with approximation ratios matching the best known for unconstrained DST and DSF and only an O(log k) length slack. The DSF result rests on a genuinely new argument in the one-path case (Lemma 4.7) that overcomes a non-metric obstacle in previous approaches. The paper carefully benchmarks against published separator and junction-tree theorems. However, a load-bearing algorithmic premise is left unproved: the exact NP-hard oracle d^(h) is assumed in Algorithm 2 and in the LP sections, and the asserted FPTAS substitution is not justified. Until this is repaired, the polynomial-time claims in Theorems 1.1–1.3 remain conditional. There is also a clear proof-writing error in Lemma 3.4 that needs correction.","major_comments":[{"comment":"The algorithms in §3.1 and §3.2 assume exact computation of the NP-hard quantity d^(h)(s,t). The parenthetical claim that replacing it with a (1+ε)-FPTAS 'does not affect the approximation guarantees' is unproved. With an approximate oracle d~∈[d,(1+ε)d], the infeasibility test 'if d^(h)(s,t)>γ' can falsely return Infeasible when d^(h)(s,t)=γ. The base case also requires an FPTAS with an explicit length/cost tradeoff. Lemmas 3.3, 3.4, and 3.6 must be re-derived with approximate distances; the threshold γ must be adjusted (e.g., to (1+ε)γ) and constants re-checked. The same issue appears in the dual-separation claim in §3.2 and in solving LC-Den-LP in §4.2. Since Theorems 1.1–1.3 rely on these polynomial-time subroutines, the polynomial-time guarantees are conditional without this proof.","section":"§3.1, Algorithm 2"},{"comment":"The proof of Lemma 3.4 states the induction hypothesis as c(F) ≤ 12γ(log|S|+1), but in the F_2 branch it uses c(F_i) ≤ 12(log|S∩C_i|+1) OPT_i, which is not implied by the stated hypothesis. With the stated hypothesis the sum would be 12γ ∑ (log k_i+1), which is not ≤ 12γ log|S|. The argument is repaired by inducting on |S| with c(F) ≤ O(OPT log|S|), using ∑ OPT_i ≤ OPT. This is a local but load-bearing proof error that must be corrected.","section":"§3.1, Lemma 3.4"},{"comment":"The sentence 'The LP contains an exponential number of variables but can be solved approximately (up to a (1+ε) factor) via separation oracle on the dual' is not a proof. The dual separation problem is the NP-hard restricted shortest path problem; an approximate separation oracle is needed. The effect of approximate separation on the LP value and on the feasibility of the returned (x,f) solution—used in Lemma 3.5 and Lemma 3.6—is not analyzed. This is needed to make Theorem 1.2 rigorous and to support Theorem 1.3 via Lemma 4.12.","section":"§3.2, LC-DST-LP"}],"minor_comments":[{"comment":"Claim 4.3 does not hold for j=0, as the authors note. The proposed dummy-vertex fix should be integrated into the proof of Lemma 4.2 rather than left as a footnote, since the current formal statement still claims the property for all j.","section":"§4.1.1, Footnote 5"},{"comment":"The extensions to buy-at-bulk and rooted generalizations are deferred to the thesis [41]. Since they are not needed for the main theorems, please label them as informal or provide at least precise theorem statements.","section":"§1.1.1"},{"comment":"The preprocessing assumption 'all edge costs are ≥1 and polynomially bounded in n' is justified in one sentence. Please expand to make the (1+o(1)) loss precise.","section":"§2.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct after repairs; the missing oracle proofs are the main obstacle. The self-citation concentration ([14],[17],[41]) is notable but the cited papers are published/refereed. The proof of Lemma 3.4 has a clear induction error that should not be mistaken for a fatal flaw; it is fixable. The FPTAS substitution and approximate separation oracle are the real load-bearing issues and should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading: the main theorems are likely true, and the one-path junction tree lemma is a real contribution, but the polynomial-time claims rest on an unproven FPTAS substitution for the NP-hard d^(h) oracle. That is the thing to look at before accepting.\n\nWhat's new: the DST results adapt Friggstad-Mousavi and Chekuri et al. to the mixture metric, as the authors acknowledge. The genuinely new content is in Section 4: the reduction to 3-layered digraphs and especially the one-path junction tree lemma (Lemma 4.7). The failure mode in [14] under length constraints is real, and the new pair (a_i,b_i) definitions plus the recursive partitioning on the path appear to handle it. I tried to break the disjointness argument (Claim 4.11) and couldn't. The junction-tree finding via the density LP is standard but coherent. The final bounds match the unconstrained planar state of the art with O(log k) length slack, which is exactly what one would hope for.\n\nSoft spots, in proportion: The FPTAS substitution is the real one. Algorithm 2 calls d^(h) exactly, and the text asserts a (1+epsilon)-approximation \"does not affect the approximation guarantees\" without proof. Since exact computation is NP-hard, this is load-bearing. The stress-test example with gamma = c(E) is correct: an overshooting oracle can falsely declare infeasibility. Likely fixable by adjusting constants and re-deriving Lemmas 3.3 and 3.4 with approximate distances, but the proof is currently missing. Section 3.2 has the same issue in reverse: the dual separation is restricted shortest path, itself NP-hard, and the effect on the LP-competitive ratio is not analyzed. Minor: the buy-at-bulk and polymatroid corollaries are deferred to an unpublished thesis, so they aren't yet part of the contribution. Citation heavy self-citations to [14] and [17] are heavy but appropriate; those papers are published and directly relevant.\n\nVerdict: the central claims are conditional rather than wrong. If the FPTAS gap is closed—and I expect it can be—this is a strong paper for the planar network-design program. It deserves a serious referee and I would bring it to reading group, largely to argue about the oracle issue. For peer review: engage with it, but require the FPTAS proof or an explicit statement that the results are bicriteria in the oracle assumption as well.","headline":"Genuine new results for length-constrained planar DST/DSF, but the polynomial-time claims are currently conditional on an unproven FPTAS substitution for the NP-hard restricted shortest path oracle.","tokens_in":25289,"tokens_out":2046,"would_cite":true,"duration_ms":22561,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68W25","90C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Length-constrained Directed Steiner Tree and Forest in planar digraphs admit (O(log k), O(log k))- and (O(log^6 k), O(log k))-bicriteria approximations, with only O(log k) slack in path length.","keywords":["length-constrained network design","directed Steiner tree","directed Steiner forest","planar digraphs","bicriteria approximation","junction trees","planar separators","buy-at-bulk network design"],"falsifier":"Exhibit a planar LC-DST instance and a (1+epsilon)-approximate routine for d^(h)(s,t) such that substituting the approximation into the prune-and-separate step makes a separator path violate the cost/length bounds of Claim 3.2, pushing the solution's length slack beyond O(log k) or its cost beyond O(log k)·OPT. Alternatively, a family of planar LC-DST instances whose path-flow LP (LC-DST-LP) has integrality gap ω(log^2 k) would directly refute Theorem 1.2.","tokens_in":24418,"feed_emoji":"🕸️","tokens_out":9067,"duration_ms":84939,"temperature":0.7,"pith_summary":"This paper asks whether network design problems that become harder when path lengths are bounded stay tractable in planar directed graphs. Its central claim is that they do: for the length-constrained versions of Directed Steiner Tree and Directed Steiner Forest, the authors give bicriteria approximation algorithms whose cost ratios match the best known for the unconstrained problems in planar digraphs, at the price of allowing paths to be longer than the bound by an O(log k) factor. The tree problem gets an (O(log k), O(log k)) approximation and an LP-competitive (O(log^2 k), O(log k)) version; the forest problem gets an (O(log^6 k), O(log k)) approximation. If these theorems are right, adding a length or delay limit to directed Steiner problems does not destroy the algorithmic advantage of planarity, and several related problems, including buy-at-bulk versions, inherit polylogarithmic approximations.","feed_headline":"Path-length limits add only O(log k) slack to planar Steiner ratios","feed_subtitle":"Delay-bounded connections in planar directed networks keep the same polylog cost ratios as unconstrained ones.","key_machinery":"Three structures carry the argument. First, the mixture metric, defined by c'(e)=c(e)+(γ/h)ℓ(e), blends edge cost and edge length into a true metric; a shortest path in this metric automatically has bounded cost and bounded length. Second, the planar separator lemma for directed paths, which guarantees three root-to-vertex dipaths whose removal splits the terminal set in half; the divide-and-conquer recursion follows exactly those paths. Third, for the forest result, the h-length-constrained junction tree: a subgraph rooted at a single vertex v in which each covered demand pair (s_i,t_i) is connected by an s_i-to-v path and a v-to-t_i path, each of length at most 3h. The paper proves low-den","core_discovery":"The authors establish that the planar separator method, which already yields polylogarithmic approximations for Directed Steiner Tree and Forest in planar digraphs, can be made length-aware. The key move is to replace ordinary distances with a mixture metric c'(e)=c(e)+(γ/h)ℓ(e), which bakes the length bound into the cost used to find separator paths; the planar separator lemma then gives three paths from the root whose total cost is O(γ) and whose total length is O(h). Recursing over the components left by those separator paths yields the tree results: an O(log k)-approximation with O(log k) length slack, and an O(log^2 k) LP-competitive version when the LP optimum is used as the guess for","pith_inferences":["The O(log k) length slack appears tied to the recursion depth of the separator method: each level adds O(h) to path length. Whether the slack can be reduced to O(1) while keeping polylogarithmic cost, as has been done for length-constrained MST in undirected planar graphs, is a natural next question the paper leaves open.","The forest result's cost exponent (log^6 k) mirrors the gap between the tree and forest algorithms; an LP-competitive planar DSF, which the paper notes is unknown even without lengths, would immediately sharpen the forest ratio to roughly O(log^3 k).","The one-path lemma's 3h length bound and the 2h reachability windows along the central path suggest the true length slack of the forest construction may be improvable; layered examples where a demand path spans exactly three layers are the natural testbed for whether 3h is inherent."],"forward_implications":["LC-DST in planar digraphs has an (O(log k), O(log k))-bicriteria approximation, so demanding bounded-length paths costs only a logarithmic length violation over the unconstrained O(log k) ratio.","The natural path-flow LP relaxation for LC-DST is O(log^2 k)-competitive in planar digraphs, allowing the LP optimum to be used directly as a budget guide.","LC-DSF in planar digraphs has an (O(log^6 k), O(log k))-bicriteria approximation, giving the first length-constrained analogue of the planar forest result.","Buy-at-bulk versions of DST and DSF in planar digraphs inherit polylogarithmic approximations from the length-constrained algorithms, as the paper argues in its extensions section.","Length-constrained rooted group, covering, and polymatroid Steiner problems in planar digraphs also receive polylogarithmic approximations via the same recursion-tree embedding idea."],"fun_headline_variants":["Planar Steiner: length bounds cost only O(log k) slack","Length-constrained planar Steiner: polylog cost, log slack","Bicriteria approximations for length-bounded Steiner in planar graphs","Planar digraphs yield near-optimal length-bounded Steiner trees","Length-aware planar Steiner matches unconstrained ratios"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing algorithmic premise is that the cost of the cheapest path no longer than h between two vertices can be treated as exactly computable, even though computing it exactly is NP-hard and the paper only asserts, without proof, that an approximate version would do.","fun_headline_variants_meta":{"raw":{"variants":["Planar Steiner: length bounds cost only O(log k) slack","Length-constrained planar Steiner: polylog cost, log slack","Bicriteria approximations for length-bounded Steiner in planar graphs","Planar digraphs yield near-optimal length-bounded Steiner trees","Length-aware planar Steiner matches unconstrained ratios"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000278,"raw_usage":{"total_tokens":1513,"prompt_tokens":789,"completion_tokens":724,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":638}},"tokens_in":533,"tokens_out":724,"duration_ms":6896,"temperature":1.0,"reasoning_tokens":638,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T01:26:45.803494+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a planar LC-DST instance and a (1+epsilon)-approximate routine for d^(h)(s,t) such that substituting the approximation into the prune-and-separate step makes a separator path violate the cost/length bounds of Claim 3.2, pushing the solution's length slack beyond O(log k) or its cost beyond O(log k)·OPT. Alternatively, a family of planar LC-DST instances whose path-flow LP (LC-DST-LP) has integrality gap ω(log^2 k) would directly refute Theorem 1.2.","supporting_citations":[],"review_version":1}