{"id":"664a1e36-b6c9-44bd-9056-a66b349d99fa","arxiv_id":"2411.14745","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A nearly linear work, polylog depth parallel algorithm for approximating the Held-Karp bound and the k-ECSS LP, via a new core-sequence MWU framework.","lead":"This paper presents a parallel algorithm that approximates the Held-Karp lower bound for metric TSP in nearly linear total work and polylogarithmic depth. It introduces a new core-sequence technique for parallel multiplicative weights updates, with potential for other large implicit linear programs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The polylog-depth claim rests on Theorem 2.3, a 'Fast Parallel Tree-Packing' attributed to [Kar00] but not proven there; no parallel derivation is supplied, so the main theorem is conditional on an unverified primitive.","rationale":"The reader's verdict is CONDITIONAL with moderate confidence, and the weakest assumption identified is exactly the load-bearing concern in my stress-test: Theorem 2.3 asserts a parallel tree-packing primitive that is cited to a sequential source and not derived in the paper. I examined the internal logic of the core-sequence framework, including the path-clearing algorithm, the extraction of 2-respecting cuts, the MWU cut oracle, and the k-ECSS acceleration; the arguments appear internally coherent, and I found no clear internal flaw of comparable severity. The provenance gap, however, is genuinely load-bearing: every epoch starts by computing this tree packing, and all subsequent steps reduce cut-clearing to 1-or-2-respecting cuts of these trees. Without a near-linear-work, constant-depth implementation of that primitive, the claimed work and depth bounds do not follow. This is an addressable issue—the authors could supply a proof or a correct citation—so CONDITIONAL is the appropriate verdict, and my stress-test does not change it. The concrete test is to settle whether such a parallel tree-packing algorithm exists in the cited literature or can be derived; if it cannot, the main theorem should be revised to state the dependence on this primitive explicitly.","tokens_in":40482,"tokens_out":21344,"duration_ms":216632,"concrete_test":"Verify the provenance and parallelizability of Theorem 2.3 by checking the original Karger [Kar00] and the cited parallel minimum-cut literature (e.g., [GG18]) for a theorem giving O(log n) spanning trees with the 1-or-2-respect property in Õ(m) work and O(1) depth. If no such theorem exists, attempt to implement the two key ingredients of Karger's tree-packing construction—randomized tree sampling/contraction and the packing verification—in the work-depth model; if either step requires Ω(log n) depth or ω(m) work, Theorem 2.3 fails as stated and Theorem 1.1's depth bound is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem (Theorem 1.1) depends on clearing a cut-covering epoch in nearly linear work and polylogarithmic depth. The epoch algorithm (Theorem 4.2) invokes Theorem 2.3 to obtain O(log n) spanning trees such that every (1+ε)-minimum cut 1-or-2-respects one of them. This theorem is the hinge: without it, clearing all cuts reduces to handling arbitrary (1+ε)-minimum cuts, which the core-sequence framework does not address. Yet Theorem 2.3 is cited from Karger [Kar00], whose algorithm is sequential; the paper gives no proof, no parallel algorithm, and no citation to a parallel source establishing the stated Õ(m) work and O(1) depth. The same concern applies to Lemma 4.25 (canonical cuts from [CQ17]), also used with parallel complexity guarantees not proven here, but Theorem 2.3 is more load-bearing because it is invoked at the top of every epoch and in the k-ECSS extension. If this primitive is unavailable, the polylogarithmic depth claim of Theorem 1.1 collapses, and the k-ECSS result (Theorem 1.2) inherits the failure. The concern is not about internal inconsistency; the rest of the core-sequence framework appears coherent, but the proof relies on an externally cited parallel primitive whose existence is not established in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a parallel approximation algorithm for the Cut Covering LP whose optimal value gives the Held-Karp bound for metric TSP, and an extension to the k-edge-connected spanning subgraph LP relaxation. The main technical innovation is a \"core-sequence\" framework for parallel multiplicative weights update (MWU): instead of updating all active coordinates in an epoch, the algorithm clears a carefully chosen sequence of small subsets. For metric TSP the paper proves the existence of core-sequences of length O(log n) with sets of size O~(n) using Karger tree-packing, forbidden-matrix arguments, path decompositions, and canonical cuts, yielding O~(m/epsilon^4) work and O~(1/epsilon^4) depth for a (1+epsilon)-approximation to the Held-Karp bound (Theorem 1.1). For k-ECSS, the paper uses knapsack-cover constraints and a range-mapping theorem to obtain a similar parallel guarantee (Theorem 1.2). The paper contains detailed proofs of the core-sequence machinery, the path/interval extraction lemmas, and the cut-oracle data structures, and it identifies several external results on which the algorithm depends.","tokens_in":40725,"tokens_out":24609,"duration_ms":261809,"significance":"If the main theorems are correct, this is the first algorithm to approximate the Held-Karp bound in nearly linear work and polylogarithmic depth, answering an open question raised by the sequential algorithm of Chekuri and Quanrud. The core-sequence framework is a genuinely new and broadly applicable tool for parallelizing MWU on implicitly defined packing/covering LPs; the claimed improvement in iteration complexity for such LPs is substantial and of independent interest. The forbidden-matrix arguments used to construct short core-sequences are elegant and, for the most part, carefully proved. The paper also gives explicit credit to the parallel primitives it builds on, though, as detailed below, several of those primitives are not established in the manuscript itself.","major_comments":[{"comment":"Theorem 2.3 is stated as a \"Fast Parallel Tree-Packing\" algorithm with O~(m) work and O~(1) depth and is attributed to [Kar00]. However, [Kar00] presents a sequential near-linear-time minimum-cut algorithm; it does not state or prove a parallel tree-packing procedure. This theorem is used at the top of every epoch in Theorem 4.2 and is inherited by Theorem 1.1 (and by the k-ECSS extension in Section 5), so without a proof or a correct parallel citation the polylogarithmic-depth claim is conditional. The paper already cites [GG18] in the same section for a parallel minimum-cut result; a parallel tree-packing guarantee may be obtainable from that work, but it must be stated and proved or cited precisely.","section":"§2, Theorem 2.3"},{"comment":"There is a mismatch between the LP matrix and the oracle's cut-weight computation. Lemma 4.7 defines A_{e,S}=1/(k c_e), so the column weight is (A^T w)_S=(1/k) sum_{e in delta(S)} w_e/c_e. The described data structure stores and sums unmodified edge weights w(e), and CutValue returns w(cut_T(s)); this is correct only if all costs c_e are equal. The same issue appears in Lemma 5.4 and in Definition 5.2, where the normalized free-cut weight is w(delta(S)\\F)/(k-|F|) with no 1/c_e factor. Since Theorems 1.1 and 1.2 are for arbitrary positive costs, the oracle must maintain w_e/c_e or an equivalent scaling to implement Focus for the stated LP. The proof of Lemma 5.4 contains a related symptom: the first-iteration value g_{s'} = (k-|F_s|)/|B| * epsilon is not epsilon/(|B_0| max_i A_{i,s'}) unless all c_e are equal. Please correct the scaling or the matrix definition.","section":"§4.6, Lemma 4.7; also §5.1, Lemma 5.4"},{"comment":"Lemma 4.25 attributes a canonical-cuts data structure to [CQ17] with O~(|E|) work and poly log|V| depth preprocessing. Reference [CQ17] is a sequential paper, and the cited lemma is not proved in the present manuscript; the parallel preprocessing and query guarantees are therefore unsupported as written. This matters because Lemma 4.7 (the MWU Cut Oracle) and hence Lemma 4.8 and Theorem 4.2 all depend on this data structure. A parallel derivation or a correct citation to a parallel construction is needed.","section":"§4.6, Lemma 4.25"}],"minor_comments":[{"comment":"Line 5 of Algorithm 3 says \"Select a subset tildeB\" at each iteration, but Definition 1.3 and Theorem 3.7 are stated in terms of a precomputed core-sequence. Please clarify that in the epoch applications the caller supplies the next member of a fixed core-sequence in order, or update the definition and proofs to allow online selection of the sequence.","section":"§3.2, Algorithm 3"},{"comment":"The proof that B'_r avoids Z3 asserts \"Then 1 < j < ell-k\" for the center of the forbidden pattern, but the boundary cases where the center lies in the first or last column are not addressed; these cases should be handled explicitly or the argument modified.","section":"§4.3, Claim 4.12"},{"comment":"The symbol k is used both for the k in k-ECSS and for the number of canonical pieces in the decomposition of a cut; consider renaming the latter to avoid ambiguity.","section":"§4.6, proof of Lemma 4.7"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is promising and the main theorems are likely obtainable, but the present version has two load-bearing gaps: the parallel tree-packing primitive is not established by the cited source, and the cut-oracle description does not incorporate edge costs in the way required by the stated LP matrices. Both are fixable within the scope of the paper---by giving a correct parallel citation/proof for tree packing and by scaling the maintained weights by 1/c_e in the oracle---but the corrections are substantive and affect the correctness claims of Theorems 1.1 and 1.2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper introduces core-sequences for parallel MWU, which is a genuinely useful abstraction for implicitly defined LPs, and proves that for the cut covering LP every epoch has a short core-sequence of small sets. That structural result is the real contribution. The advertised near-linear work, polylog depth algorithm for the Held-Karp bound would resolve an open question if it fully holds.\n\nWhat is new and good: the core-sequence definition cleanly unifies sequential Fleischer/Young and parallel Luby-Nisan approaches; Theorem 1.5, based on posimodularity and forbidden matrix theory, is a first-principles proof and I found it convincing. The k-ECSS extension via the Range Mapping Theorem is also a nice application. The paper is honest about what it proves and what it assumes.\n\nThe soft spots are real but not fatal in themselves. Theorem 2.3, 'Fast Parallel Tree-Packing,' is cited from Karger, but Karger's original algorithm is sequential. No parallel derivation or reference to a parallel source is supplied, and this theorem is load-bearing: the epoch algorithm clears all cuts by clearing 1-or-2-respecting cuts of these trees. Without it, the polylog depth claim collapses. The same issue appears in Lemma 4.25 (canonical cuts from Chekuri-Quanrud), though that one is less central because the data structure construction is standard. The k-ECSS iteration complexity proof also leaves some invariants implicit, but that is minor compared to the tree-packing gap. These are conditions, not internal contradictions; the rest of the proof seems coherent.\n\nWho this is for: parallel algorithms researchers and anyone who uses the Held-Karp bound or cut covering LPs as a subroutine. The framework itself is worth teaching and citing, and the main theorem is important enough that the paper should not be desk-rejected. A serious referee should demand that the authors either prove the parallel tree-packing primitive, give a correct citation to a parallel version, or explicitly state the main theorem as conditional on such a primitive. I would send it to review with that as the primary request.","headline":"Core-sequence framework is a real contribution, but the main theorem leans on an unproven parallel tree-packing primitive; the paper deserves review and needs that gap closed.","tokens_in":41287,"tokens_out":1571,"would_cite":true,"duration_ms":18776,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W10","68Q25","90C05","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new parallel algorithm approximates the Held-Karp TSP bound in near-linear work and polylogarithmic depth.","keywords":["Held–Karp bound","Metric TSP","parallel algorithm","multiplicative weights update","core-sequences","minimum cut","k-edge-connected spanning subgraph","work-depth model"],"falsifier":"Exhibit a graph family where no O(log n) spanning trees produced in O(1) depth and near-linear work can have every (1+ε)-minimum cut 1-or-2-respecting one of the trees, or exhibit an instance where the epoch algorithm's core-sequence length grows super-polylogarithmically.","tokens_in":40270,"feed_emoji":"🧮","tokens_out":4721,"duration_ms":40034,"temperature":0.7,"pith_summary":"The paper claims a randomized parallel algorithm that, for any undirected graph with n vertices, m edges and positive edge costs, computes a (1+ε)-approximation to the Held–Karp bound—the value of the subtour-elimination LP behind the best TSP approximation algorithms—in Õ(m/$ε^{4}$) work and Õ(1/$ε^{4}$) depth. If true, this is the first algorithm to achieve both nearly linear total work and polylogarithmic parallel depth for this problem; the previous near-linear algorithm was inherently sequential. The same machinery, combined with a known reduction, also solves the k-edge-connected spanning subgraph LP to (1+ε) accuracy in the same complexity. The central novelty is a notion of core-sequences for the parallel multiplicative weights update method, which lets the algorithm clear each MWU epoch by focusing on a short sequence of small sets of near-minimum cuts rather than touching all quadratic many cuts.","feed_headline":"Held-Karp bound in near-linear work and polylog depth","feed_subtitle":"A core-sequence MWU method gives the first parallel (1+ε)-approximation that runs in polylog depth.","key_machinery":"The core object is a core-sequence: for a fixed MWU epoch, an ordered list of subsets of the active columns (here, cuts of weight below (1+ε)λ) such that clearing each subset in turn with the parallel MWU update clears the whole epoch. The paper proves a general theorem that a core-sequence of sets of size at most n and length ℓ clears an epoch in Õ(Σ f(|B_i|) log(|B_i|)/$ε^{2}$) work and Õ(Σ log(|B_i|)/$ε^{2}$) depth, where f is the cost of updating one set. For the Cut Covering LP the authors find core-sequences of length Õ(1) and sets of size Õ(n) by exploiting submodularity and forbidden-matrix structure of approximate minimum cuts on path minors of Karger's tree packing.","core_discovery":"The authors establish that the Cut Covering LP—equivalent to the Held–Karp bound when k=2—can be solved to (1+ε) accuracy by an epoch-based parallel MWU algorithm whose per-epoch work is near-linear and whose depth is polylogarithmic. They prove that every epoch has a core-sequence of length Õ(1) whose sets each have Õ(n) cuts, and that the canonical cut data structure of Chekuri and Quanrud enables each focus operation in near-linear work. For the k-ECSS LP, the same core-sequence technique combined with the range-mapping theorem of Chalermsook et al. yields a (1+ε)-approximate solution in the same complexity, improving the depth exponentially for large k.","pith_inferences":["The core-sequence idea may apply to other packing/covering LPs whose constraint columns have strong combinatorial structure beyond cut problems; a testable extension is survivable network design LPs other than k-ECSS.","If the tree-packing primitive is the actual bottleneck, a deterministic or simpler parallel replacement for it would immediately strengthen the practicality of the result.","The depth bound Õ(1/ε^4) is independent of graph size, so with enough processors the runtime is governed only by accuracy—a property potentially valuable for very large sparse graphs."],"forward_implications":["A (1+ε)-approximation to the Held–Karp bound can be computed in near-linear work with polylog depth, making the bound practically usable in parallel for large sparse graphs.","Combining with the reduction of Chalermsook et al. gives a parallel (1+ε)-approximate solver for the k-ECSS LP with the same complexity, and exponentially better depth when k is large.","The core-sequence framework generalizes earlier parallel MWU iteration bounds from polylog(nnz(A)) to polylog in the product of core-sequence cardinalities, improving iteration complexity for implicitly defined LPs.","Because the Held–Karp bound is a lower bound for TSP, faster parallel approximation of it directly accelerates parallel approximation algorithms for Metric-TSP that rely on the subtour LP."],"supporting_citations":[{"why":"Supplies the near-linear sequential algorithm and the canonical cut data structure that the parallel implementation reuses for queries and updates.","marker":"[CQ17]"},{"why":"Provides the tree-packing theorem (Theorem 2.3) that every approximate minimum cut 1-or-2-respects one of O(log n) spanning trees; the parallel depth claim inherits its guarantees.","marker":"[Kar00]"},{"why":"Introduced the parallel MWU approach of updating all active coordinates, which the core-sequence framework generalizes.","marker":"[LN93]"},{"why":"Gave the epoch-based parallel MWU whose iteration count core-sequences improve; the paper adapts its on-the-fly initialization.","marker":"[You01]"},{"why":"Introduced epochs in MWU, the structure over which core-sequences are defined.","marker":"[Fle00]"},{"why":"Supplies the reduction and range-mapping theorem that turn the k-ECSS LP into a cut-covering form solvable by the same machinery.","marker":"[CHN+22]"},{"why":"Provides the path-minor and interested-path-pair techniques used to extract 2-respecting cuts efficiently.","marker":"[MN20]"}],"fun_headline_variants":["Parallel Held-Karp bound in near-linear work and polylog depth","Held-Karp bound now parallel: near-linear work, polylog depth","Near-linear work and polylog depth for Held-Karp bound","Core-sequence MWU gives parallel Held-Karp bound in polylog depth","First polylog-depth parallel algorithm for Held-Karp bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The polylogarithmic depth claim rests on the assumption that Karger's tree-packing theorem can be implemented in near-linear work and O(1) depth to output O(log n) spanning trees that capture all (1+ε)-minimum cuts; the paper cites this as a known primitive but gives no parallel algorithm for it.","fun_headline_variants_meta":{"raw":{"variants":["Parallel Held-Karp bound in near-linear work and polylog depth","Held-Karp bound now parallel: near-linear work, polylog depth","Near-linear work and polylog depth for Held-Karp bound","Core-sequence MWU gives parallel Held-Karp bound in polylog depth","First polylog-depth parallel algorithm for Held-Karp bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000787,"raw_usage":{"total_tokens":3522,"prompt_tokens":1048,"completion_tokens":2474,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":664,"completion_tokens_details":{"reasoning_tokens":2378}},"tokens_in":664,"tokens_out":2474,"duration_ms":17813,"temperature":1.0,"reasoning_tokens":2378,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:58:47.552242+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a graph family where no O(log n) spanning trees produced in O(1) depth and near-linear work can have every (1+ε)-minimum cut 1-or-2-respecting one of the trees, or exhibit an instance where the epoch algorithm's core-sequence length grows super-polylogarithmically.","supporting_citations":[],"review_version":1}