{"id":"eef5fba9-b53c-4733-be40-d0b011fc55c6","arxiv_id":"2611.17201","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"First polylogarithmic, LP-competitive approximations with constant (down to 1+epsilon) length slack for directed and multicommodity length-constrained Steiner problems on planar graphs, plus hardness separating planar from general graphs.","lead":"Researchers found faster approximation algorithms for building cheap networks whose connection paths must be short, working on planar graphs. Their results give the first near-exact path-length guarantees for directed and multi-customer variants, and they prove these problems are easier on planar layouts than on general graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"LC-SF cost bound relies on a flow-threshold covering argument whose constants are not fully verified; the weighted averaging step (Lemma 4.6) requires that the set of candidates is finite and that the sum of weights over candidates covering a pair is at least 1, but the construction of candidates…","rationale":"The reader identified the LC-SF small-intersection property and the bucketing as the weakest assumption, which aligns with my concern. However, the reader did not flag the specific interaction between the 4/3 scaling and the mixture-cost bound in Lemma 4.3, which is the precise technical gap I see. The reader's verdict is CONDITIONAL, which I agree with; I do not see a reason to change it to REJECT because the gap may be fixable by adjusting constants or by redefining γ_j after scaling. The paper's own disclosure of AI assistance and the acknowledged complexity of the LC-SF proof further support a CONDITIONAL verdict. I therefore recommend UNCHANGED (i.e., the reader's CONDITIONAL stands). The agreement_with_reader is 'partial' because the reader's weakest_assumption is about the small-intersection property, which is related but not identical to the scaling-mixture interaction I highlight.","tokens_in":34194,"tokens_out":1126,"duration_ms":14240,"concrete_test":"Recompute Lemma 4.3 and Lemma 4.7 after the 4/3 scaling: define X' = (4/3)X, γ'_j = (X'/k) τ^j, and verify that for every path p in the scaled bucket Bj, w'_j(p) ≤ 2γ'_j still holds. If the inequality fails, recompute the chunk-per-vertex bound in Lemma 4.7 and the total weighted cost in Lemma 4.11; if the exponent of log k increases, the O(log^5 k/ϵ^2) claim may be invalid.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The LC-SF cost analysis (Section 4.2) depends on a chain of inequalities whose constants are not fully instantiated. The critical step is Lemma 4.7, which bounds the number of chunks containing a given vertex by O(log^2 k/(ϵ log τ)). This bound multiplies three sources: (i) O(1/ϵ) chunks per separator path (derived from the mixture-cost bound of 4γ_j on the subpath between the first and last intersection points), (ii) O(log k) levels of recursion, and (iii) O(log k / log τ) buckets. The derivation of (i) uses Lemma 4.3, which states that every path in bucket Bj has mixture cost at most 2γ_j. However, Lemma 4.3 relies on the preprocessing step (Lemma 4.2) that discards paths of cost ≥4X and scales the remaining flow by 4/3. After scaling, the LP value X is replaced by (4/3)X, but the bucket definitions (γ_j = (X/k) τ^j) are not updated accordingly in the text. If the scaling changes the effective γ_j, the bound w_j(p) ≤ 2γ_j may no longer hold for all p in Bj, potentially increasing the number of chunks per vertex beyond O(1/ϵ). The subsequent weighted averaging (Lemma 4.6) and the bound on total weighted cost (Lemma 4.11) depend on the chunk-membership bound of Lemma 4.7; if that bound is off by a factor, the final O(log^5 k/ϵ^2) approximation ratio could be understated. The authors acknowledge the preprocessing step (line after Lemma 4.2: 'the scaled fractional solution supports a flow of 1 between demand pairs') but do not explicitly recompute the mixture-cost bound after scaling. This is a concrete gap that could affect the correctness of the LC-SF cost guarantee.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper presents the first polylogarithmic approximations with O(1) length slack for three length-constrained network design problems on planar graphs: LC-DST (directed Steiner tree), LC-SF (Steiner forest), and LC-DSF (directed Steiner forest). The algorithms are LP-competitive for LC-DST and LC-SF, achieving 1+ε length slack, and for LC-DSF they achieve 6+ε slack. The approach uses a novel charging argument that charges cost to length and length to cost, based on a hierarchical mixture metric and shortcut selection on planar separators. The paper also provides hardness results showing that on general graphs, polylogarithmic approximations with length slack below 3 are impossible for LC-SF and any slack for LC-DSF.","tokens_in":34595,"tokens_out":2430,"duration_ms":17188,"significance":"If correct, these results resolve open questions about the existence of O(1)-slack polylogarithmic approximations for directed and multicommodity length-constrained problems on planar graphs. The LP-competitive bounds for LC-DST and LC-SF also give the first upper bounds on the integrality gaps of natural LP relaxations for these problems on planar graphs. The techniques, particularly the cost-to-length and length-to-cost charging framework, are novel and may be of independent interest. The hardness results separate planar from general graphs, which is a clean contribution.","major_comments":[{"comment":"The bound on the number of chunks containing a given vertex is O(log^2 k/(ε log τ)). However, the derivation of the O(1/ε) factor per separator path relies on Lemma 4.3, which states that every path in bucket B_j has mixture cost at most 2γ_j. Lemma 4.3 itself depends on the preprocessing step (Lemma 4.2) that discards paths of cost ≥4X and scales the remaining flow by 4/3. After scaling, the LP value X is replaced by (4/3)X, but the bucket definitions γ_j = (X/k) τ^j are not updated accordingly in the text. If the scaling changes the effective γ_j, the bound w_j(p) ≤ 2γ_j may no longer hold for all p in B_j, potentially increasing the number of chunks per vertex beyond O(1/ε). The authors acknowledge the scaling (line after Lemma 4.2: 'the scaled fractional solution supports a flow of 1 between demand pairs') but do not explicitly recompute the mixture-cost bound after scaling. This could affect the O(log^5 k/ε^2) approximation ratio for LC-SF. The authors should clarify whether the bucket definitions are adjusted after scaling, or provide a justification that the bound remains valid.","section":"§4.2, Lemma 4.7 and surrounding text","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Lemma 4.8 states that 'the recursive process continues until all terminal pairs are separated, therefore every path in P_hi must intersect the separator at some level of recursion.' However, the recursion is on the graph after removing separator paths, and the separator paths are defined with respect to an arbitrary root r. It is not guaranteed that every s_i-t_i path in the LP support intersects the separator at some level, because the separator is defined from a fixed root r, not from the terminal pairs. The recursion only separates terminals that lie in different components after removing the separator paths, but a path could potentially avoid all separator paths if it stays entirely within a component that is never separated. The authors should justify that the separator hierarchy eventually separates all terminal pairs, or adjust the argument to account for paths that may not intersect any separator.","section":"§4.2, Lemma 4.8","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The proof of Lemma 3.9 charges the cost of each shortcut to the improvement in length to reach the final vertex z of the separator. However, the definition of L_i uses d_T(r, a_i) + l(P_i) + l(Q[v_i, z]), where d_T(r, a_i) is the distance in the current solution T before buying P_i. The inequality c(P_i)/(X_H log k) ≤ (L_{i-1} - L_i)/(ε h) relies on the assumption that the existing path to v_i before buying P_i is exactly the path through the previous shortcut and the separator subpath. But the solution T may contain multiple paths to v_i; the distance d_T(r, v_i) is the minimum over all paths, not necessarily the one through the previous shortcut. If there is a shorter path to v_i that does not go through the previous shortcut, then the inequality may not hold because the improvement Δ_i could be smaller than claimed. The authors should argue that the path through the previous shortcut is indeed the shortest path to v_i in T before buying P_i, or provide a more careful charging argument that does not rely on this assumption.","section":"§3.2, Lemma 3.9","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The construction of candidate solutions uses the median distance a_i from s_i to chunk C along paths in P_hi ∩ P_C, weighted by f_p. The median is defined such that at least half the flow from s_i to C has length ≤ a_i, and at least half the flow from C to t_i has length ≤ h - a_i. However, the flow paths in P_hi ∩ P_C are s_i-t_i paths, not s_i-C or C-t_i paths. The subpaths from s_i to C and from C to t_i are not necessarily independent; the flow on a path p is counted in both the s_i-C and C-t_i parts. The median condition ensures that there is a set of paths with total flow at least β/2 from s_i to C of length ≤ a_i, and similarly from C to t_i of length ≤ h - a_i, but these sets may be different. The LC-ST algorithm then connects s_i' and t_i' to the root r_C, but the paths from s_i' to r_C and from r_C to t_i' may use different flow paths, and the concatenation may not correspond to a single s_i-t_i path of length ≤ h. The authors should clarify how the median trick guarantees a feasible s_i-t_i path of length ≤ (1+ε)h, given that the two halves may come from different flow paths.","section":"§4.1, Step 2: Constructing Candidate Rooted Solutions","authors_acknowledge":null,"authors_acknowledge_p":null}],"minor_comments":[{"comment":"The abstract states 'We give the first poly-time polylogarithmic approximations with O(1) length slack for these problems on planar graphs.' This is accurate for the directed and multicommodity problems, but for LC-ST on planar graphs, Hershkowitz and Huang [33] already gave an O(log^{1+ε} k) approximation with 1+ε length slack. The authors should clarify that 'these problems' refers to the directed and multicommodity variants, or adjust the wording to avoid overclaiming.","section":"Abstract","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The table lists the LC-DST result from [12] as having cost O(log^2 k) and length slack O(log k), but the text in §1.1 says 'O(log^2 k) LP-competitive approximation with length slack O(log k) for LC-DST'. The table should include a note that the [12] result is LP-competitive, or the text should be consistent. Currently the table says 'No' for LP-competitive for the first [12] row, but the second [12] row says 'Yes'. This is confusing; the authors should clarify which result is which.","section":"§1.1, Table 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The hierarchical mixture metric w_H(e) = l(e)/(ε h) + c(e)/(X_H log k) uses X_H, which is defined as the sum of c(e) x_e over edges in region H. However, after buying separator edges, their costs are set to 0 for the remainder of the algorithm, but X_H remains its original value. This is stated in the text, but it would be helpful to explicitly note that X_H is not updated after separator edges are bought, to avoid confusion.","section":"§3.1, Definition 3.2","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"In Algorithm 5, the recursion on connected components of G \\(Q_1 ∪ Q_2 ∪ Q_3) is described, but it is not specified how the root r is chosen for each recursive call. The separator lemma (Lemma 2.3) requires a root, but the algorithm says 'from an arbitrary root r ∈ V'. If the root is chosen arbitrarily, the separator paths may not be balanced with respect to the terminal pairs in that component. The authors should specify how the root is chosen in each recursive call, or argue that any root works.","section":"§4.1, Algorithm 5","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The hardness result for LC-SF states that there is no polynomial time 2^{log^{1-ε} k} approximation with length slack β < 3. However, the reduction uses a constant δ that depends on β, and the length constraint h = 1 + 4δ. The hardness is for general graphs, not planar graphs. The authors should explicitly state that the hardness is for general graphs, as the rest of the paper focuses on planar graphs.","section":"§5, Theorem 1.4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The AI disclosure is unusual but appreciated. However, the authors state that GPT-6 Astra improved the LC-DST bound from O(log^4 k/ε^3) to O(log^2 k/ε) and provided the path preprocessing and flow threshold arguments for LC-SF. This raises questions about the novelty and attribution of the key ideas. The authors should ensure that the contributions of the AI are clearly delineated and that the authors take full responsibility for correctness, as they do.","section":"§6, Acknowledgements","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The paper uses the term 'LP-competitive' to mean that the cost of the solution is bounded by a polylogarithmic factor times the LP optimum. This is standard, but the authors should define it explicitly in the preliminaries, as it is used throughout.","section":"General","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"major_revision"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"This is a serious theory paper and on my reading the main results are real. The headline is LC-DST at O(log^2 k/epsilon) with 1+epsilon slack, LP-competitive: it improves Hershkowitz-Huang's O(log^3 k/epsilon) undirected LC-ST result and moves to the directed setting, and it tightens Chekuri-Jain's O(log k) slack down to 1+epsilon. The cost-to-length / length-to-cost charging is the genuinely new idea, and I traced it end to end. Lemma 3.8's separator bounds follow from the pruning radius; Lemma 3.9's shortcut cost telescopes against cumulative length improvement toward the separator endpoint with L_1 - L_m <= O(h); the canonical-path argument closes the length budget at h + epsilon h. I found no error in that pipeline.\n\nLC-SF is where the work is, and it is dense. The stress-test note flags a scaling inconsistency: after Lemma 4.2 discards paths of cost >= 4X and rescales the flow by 4/3, are the bucket boundaries gamma_j = (X/k) tau^j stale? I went back to the text and I think that concern does not land. Bucketing is by actual path cost, which is invariant to flow scaling; Lemma 4.3's bound w_j(p) <= 2 gamma_j uses c(p) <= gamma_j and l(p) <= h, both unchanged. The 4/3 enters only the final constant, and the paper says exactly that at the end of Section 4.2. I would not hold that against the authors.\n\nWhat I would want a referee to sit with: the per-vertex chunk-membership bound in Lemma 4.7, the covering argument in Lemma 4.8, and the weighted averaging hinge (Lemma 4.6 into Lemma 4.11). Those constants are load-bearing and not all fully instantiated. I could not re-derive every inequality in Section 4.2 in one sitting; nothing contradicted itself, but it deserves a careful reader. The LC-DSF result rests on Lemma A.1 quoted from Chekuri-Jain [12], which is published, so that is supported rather than a soft spot. The AI disclosure is honest and argues for a watchful referee, not distrust.\n\nVerdict: send to review. I would want Section 4 checked before signing off, but the LC-DST result alone is a solid contribution worth the reading group.","headline":"Serious theory paper that likely resolves the stated O(1)-slack open questions; the LC-DST pipeline is clean and checkable, while LC-SF is the dense part a referee must actually sit with.","tokens_in":35988,"tokens_out":621,"duration_ms":33195},"pith_extraction":null,"created_at":"2026-11-13T09:32:46.225588+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":null,"supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}