{"id":"07de4705-32a6-46e2-8437-126cc8c4cfd1","arxiv_id":"2411.16578","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A deterministic LP-rounding algorithm achieves a 2-approximation for the forest cover problem, and a 6-approximation for the bounded forest cover problem.","lead":"This paper gives a deterministic 2-approximation algorithm for the forest cover problem, a weighted generalization of vertex cover where the cover must form a forest and the cost counts both vertices and edge weights. It also improves the best known approximation for the bounded forest cover problem from 8 to 6.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 8's proof jumps from prefix/suffix inequalities to (39) without deriving the suffix analogue of (26), leaving the component bound behind Theorem 5 unproven.","rationale":"The central claim is Theorem 5, a deterministic 2-approximation for forest cover. The proof structure is clear: Lemma 5 component-wise, then summation over components. The fragile step is in Lemma 8, where the manuscript combines a prefix inequality (26), a suffix edge-weight inequality (32), and a suffix vertex inequality (35) to obtain the component inequality (39). The text does not derive a suffix analogue of (26), and the displayed algebra duplicates γ_i terms unless the prefix and suffix vertex sets are disjoint. This is a proof gap, not a demonstrated counterexample; the claimed ratio may well be repairable. I do not share the reader's choice of Lemma 12's degree-2 claim as the weakest assumption, since low-low support edges are excluded by the LP vertex-cover constraints and high leaves are not deleted, so the needed degree assertion admits a simple proof. The verdict should remain CONDITIONAL: the BFC result and the overall approach are valuable, but Theorem 5 is not established as written until Lemma 8 is repaired or replaced.","tokens_in":28623,"tokens_out":29429,"duration_ms":297079,"concrete_test":"Re-derive inequality (39) in the proof of Lemma 8 from (26), (32), and (35), writing every prefix and suffix set with explicit disjoint overbar notation. If (39) does not follow without separately proving the suffix version of (26), then Lemma 5 is not proved; a repaired proof must supply that suffix inequality explicitly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The deterministic 2-approximation is Theorem 5, and it is exactly Lemma 5 summed over components. Lemma 5 is proved through Lemma 8 in Section 4.2. In the proof of Lemma 8, inequality (26) is established for the prefix H_t (Lemma 9). Inequality (32) is then stated for the suffix, and the text claims that adding (26), (32), and (35) gives (38), and that 'adding terms of sub-graph H_t and H_t' gives (39). The load-bearing gap is that no inequality analogous to (26) is ever derived for the suffix H_t; Lemma 9 is explicitly about the first t edges. Furthermore, when (26) and (35) are combined, the γ_i terms appear twice unless the two sums are over disjoint vertex sets, and the manuscript's overbar notation is too garbled to establish that disjointness. Without (39), Lemma 8 fails, and with it Lemma 5 and Theorem 5 are unsupported. The reader's identified weak point, Lemma 12's degree-2 claim, is actually less fragile: a low vertex cannot have a low-low support edge by x_u+x_v ≥ 1, and high leaves are not deleted, so the degree claim has a short justification. The real missing step is the prefix/suffix algebra in Lemma 8.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies the forest cover problem, in which one chooses a vertex-covering forest minimizing the weighted index wi(F)=Σ|T_i|-Σ_{e∈E(F)}(1-w_e), and the bounded forest cover problem. The claimed contributions are: (1) a randomized (2+ε)-approximation via a dual-fitting argument over binary-weight instances, (2) a deterministic LP-rounding 2-approximation (Theorem 5), and (3) a 6-approximation for bounded forest cover (Theorem 6), improving a known 8-approximation. The deterministic result is presented as the main contribution and is proved through a component-wise inequality (Lemma 5) established by Kruskal-prefix and Hall-type arguments in Section 4.2; the bounded forest cover result depends directly on the deterministic 2-approximation.","tokens_in":28780,"tokens_out":16775,"duration_ms":167353,"significance":"If the deterministic 2-approximation were correct, it would be essentially tight under the standard reduction from vertex cover, and it would imply the stated improvement for bounded forest cover. The paper also attempts a genuinely different probabilistic dual-fitting technique, which could be of independent interest. The lower-bound construction for binary weights (Lemma 2) is clean, and the overall LP-rounding strategy is natural. However, the current manuscript contains load-bearing gaps in both the deterministic and the probabilistic proofs, so the significance is conditional on substantial repair.","major_comments":[{"comment":"The step from inequalities (26), (32), and (35) to inequality (39) is not valid as written. Inequality (26) is proved only for the prefix H_t. Inequality (32) bounds the suffix edge terms, but no analogue of (26) is derived for the suffix H_t^bar. In the derivation of (36)–(38), the prefix deleted-vertex term Σ_{i∈VD_t} x*_i − Σ_{(i,j)∈ED_t} y*_ij(1−w_ij) is added twice, while the corresponding suffix term Σ_{i∈VD_t^bar} x*_i − Σ_{(i,j)∈ED_t^bar} y*_ij(1−w_ij) never appears. The sentence \"To (38), we add terms of sub-graph H_t and H_t^bar\" cannot produce the missing suffix term from a duplicated prefix term. Since Lemma 8 is the load-bearing step for Lemma 5 and Theorem 5, the deterministic 2-approximation is not proved as written.","section":"Section 4.2, Lemma 8"},{"comment":"The statement and proof of Lemma 12 are too garbled to verify. The sets S, S′, S′′ and the edge partitions ET^A_t and ET^B_t are defined with conflicting membership conditions, and formula (35) mixes barred and unbarred vertex sets from H_t and H_t^bar. The Hall argument also asserts without a precise proof that every vertex in VT_t^<.5 has degree at least two in the relevant tree, which is plausible from the pruning rule but should be stated for the suffix sets used in (35). Lemma 12 supplies the −Q/2 bound needed to complete inequality (38), so this is not merely a presentation issue.","section":"Section 4.2, Lemma 12"},{"comment":"The expectation step E[y_i^e W_i^e] = y_i^e E[W_i^e] is invalid. Here y_i^e is the output of Algorithm 1 on the random binary instance W_i, so y_i^e and W_i^e are correlated; y_i^e is not a fixed quantity. This breaks the averaged primal-dual inequality P ≤ 2D and the subsequent derivation of the claimed (2+ε)-approximation.","section":"Section 3.2, Theorem 4"},{"comment":"The choice δ = ε² and the assertion that δΣ_e y*_e ≤ ε·OPT for sufficiently small ε are not uniform in the instance size. For example, take a complete graph on N vertices with all edge weights 0. The forest cover optimum is 1, and an optimal LP solution can have x*_i = 1 for every vertex and y*_e = 1 on the edges of a spanning tree, giving Σ_e y*_e = N−1. Then δΣ_e y*_e = ε²(N−1), which exceeds ε for N > 1/ε + 1. Thus OPT′ ≤ (1+ε)OPT is not guaranteed. The parameter δ needs to be chosen as a function of the instance, or a bound on Σ_e y*_e must be proved.","section":"Section 3.2, Theorem 4"}],"minor_comments":[{"comment":"When stating the Chernoff–Hoeffding bound, the sentence after the choice m = n/(2δ²) should read Pr[1/m Σ W_i^e ≤ (1−w_e)−δ] ≤ 1/e^n; the displayed inequality direction in the following sentence is reversed or missing a complement.","section":"Section 3.2, Theorem 3"},{"comment":"Step 9 of Algorithm 2 should specify whether the deletion of pendant vertices in V_C^{<0.5} is simultaneous or iterative; the current wording leaves the structure of the resulting tree T ambiguous.","section":"Section 4, Algorithm 2"},{"comment":"Throughout Section 4.2, the overbar notation for suffix objects (H_t^bar, V_t^bar, E_t^bar) is used inconsistently, with many formulas omitting bars in places where the proof clearly refers to the suffix. This makes the already intricate algebra extremely difficult to follow.","section":"Section 4.2"},{"comment":"The notation OP T, OP T′, and OP T in Observation 1 is confusing: the first is a number of trees while the second is a weighted index. Please distinguish the two quantities notationally.","section":"Section 5, Observation 1"},{"comment":"The manuscript contains numerous typographical errors, including \"attibute\", \"Collolary\", and inconsistent use of \"vice\" versus \"vertex\". A careful proofreading pass is needed.","section":"Various"}],"recommendation":"major_revision","confidential_remarks":"The paper has two promising algorithmic ideas, but neither is currently established. The deterministic proof has a concrete unfilled gap in Lemma 8, and the probabilistic proof contains a correlation error plus a parameter choice that is not uniform in the input size. I would ask the authors for a complete rewrite of Section 4.2 and a corrected treatment of Section 3.2 before sending the paper back to review. The central ideas are worth further work, but the manuscript is not ready for acceptance in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Best to read this as a first draft of a good paper. The forest cover problem is a natural relative of vertex cover: cover all edges with vertices and pay the weighted index of a forest. Unit weights make it exactly vertex cover, so 2 is tight under UGC; the deterministic 2-approximation would close the problem if the proof held. The binary-weight dual fitting argument in Section 3.1 is clean and really does give a 2-approximation for the 0/1 case, and the BFC 6-approximation via scaling plus Lemma 13 is a genuine improvement over the authors' earlier 8, conditional only on the deterministic 2-approximation. The citation pattern is ordinary, and the self-citation to the earlier CALDAM paper is appropriate.\n\nThe soft spots are serious. The probabilistic Theorem 4 is wrong as written. The quantity P_i includes a stray 2|M_i| that is not part of the weighted index, so P_i is not the primal objective for experiment i. The proof then averages over m experiments while treating the y variables as fixed, but those variables depend on the random W_i_e. The expectation step is invalid, and I do not see a typo-level repair; one would need a per-experiment bound on the true primal cost. Theorem 4 should be fixed or dropped from the claims.\n\nThe deterministic proof is structurally plausible but not verifiable. The reader's worry about Lemma 12's degree claim is less fragile than it looks: a low-low support edge is impossible by x_u+x_v >= 1, and the Hall argument has a short repair. The real broken step is in Lemma 8. Inequality (26) is proved for the prefix H_t via Lemma 9. Lemma 11 gives a suffix edge inequality (32), but nothing gives a suffix analogue of (26) with a component bound, and the move from (38) to (39) simply declares the union of H_t and H_t^bar terms. Without (39), Lemma 8 fails, and with it Lemma 5 and Theorem 5. That is load-bearing. Section 4.2 needs a full rewrite with the definitions fixed; the text around S, S', S'', and ET^A/ET^B is garbled.\n\nWho gets value from this? Researchers working on vertex cover variants, tree cover, and bounded covering problems. The BFC improvement is worth keeping, and the problem definition is worth having in the literature. I would not accept the manuscript in its current form, but I would send a serious referee a revised version: fix or remove Theorem 4, and rewrite Section 4.2 with the prefix/suffix algebra done explicitly. If the deterministic 2-approximation survives that rewrite, this becomes a solid, tight result.","headline":"A natural vertex-cover generalization with a likely-tight 2-approximation, but the deterministic proof is unverifiable as written and the probabilistic theorem is wrong as written.","tokens_in":29403,"tokens_out":3649,"would_cite":true,"duration_ms":37122,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The forest cover problem admits a deterministic 2-approximation via LP rounding, matching the inapproximability inherited from vertex cover.","keywords":["forest cover","bounded forest cover","approximation algorithm","LP rounding","dual fitting","probabilistic method","vertex cover","minimum spanning tree"],"falsifier":"Run Algorithm 2 on a small weighted graph and check whether the returned forest ever satisfies wi(APX_FC) > 2·LP_OPT, or more directly, search for an LP-optimal support whose MST has, after deleting pendant low-valued vertices, a remaining vertex with x* < 0.5 and degree 1 in the contracted tree; if such an instance exists and the inequality of Lemma 12 fails, the 2-approximation proof collapses.","tokens_in":28356,"feed_emoji":"🌲","tokens_out":5439,"duration_ms":54219,"temperature":0.7,"pith_summary":"The paper studies two NP-complete covering problems: forest cover, where a forest's vertices must cover all edges and the cost is the number of vertices plus a weight-discounted edge count, and bounded forest cover, where each tree in the covering forest may weigh at most λ. It claims that forest cover admits a randomized (2+ε)-approximation via dual fitting on randomly rounded binary-weight instances, a deterministic 2-approximation by rounding an LP solution through component-wise minimum spanning trees and pruning low-value pendant vertices, and, as a consequence, a 6-approximation for bounded forest cover. If the deterministic 2-approximation is correct, the approximation ratio of forest cover is exactly 2, matching the hardness inherited from vertex cover. The probabilistic averaging technique is presented as a contribution that may be of independent use.","feed_headline":"Forest cover now has a 2-approximation algorithm","feed_subtitle":"LP rounding plus tree pruning hits the vertex-cover hardness barrier; bounded forest cover improves from 8 to 6.","key_machinery":"The load-bearing objects are the LP relaxation with three constraint families — vertex cover constraints x_u + x_v ≥ 1, incidence constraints x_i ≥ y_ij, and cycle-elimination constraints for every nonempty vertex set S — and the component-wise MST-plus-prune rounding. For the probabilistic result, the mechanism is dual fitting on randomly rounded binary-weight instances: each edge weight is replaced by an independent Bernoulli(1 − w_e) indicator, the binary-weight primal-dual Algorithm 1 gives a feasible dual of value k + |M|, and averaging m = n/(2δ²) such dual solutions produces a feasible dual for a δ-perturbed LP, yielding a (2+ε)-approximation. For bounded forest cover, the mechanism is an edge-decomposition lemma stating that a tree of weight w with edges of weight at most β splits into at most max{w/β, 1} trees of weight at most 2β.","core_discovery":"The central discovery is that the weighted index objective — the number of vertices in the forest minus the weight-discounted edge sum, equivalently the component count plus the weighted edge sum — can be rounded from the LP optimum without losing more than a factor of two. The proof works component by component on the support of the optimal fractional solution: an MST is built by Kruskal's algorithm, pendant vertices with fractional value below 1/2 are deleted along with their incident edges, and a loop-invariant argument over the Kruskal edge order shows each remaining tree's cost is at most twice the component's fractional cost. Isolated vertices with fractional value at least 1/2 are kept in the forest, while isolated vertices below 1/2 are discarded. Summing over all components yields the theorem wi(OPT_FC) ≥ (1/2) wi(APX_FC), establishing that Algorithm 2 is a deterministic 2-approximation.","pith_inferences":["Editorial inference: the averaging trick over randomized binary-weight duals is not tied to forest cover's specific objective; it should apply to any covering problem that has a 2-approximate primal-dual pair on binary instances and linear dual constraints, provided independent Bernoulli rounding of the right-hand sides is feasible.","Editorial inference: the deterministic proof's component-wise loop invariant suggests a general recipe — round the LP support with a minimum spanning tree, prune low-value leaves, and charge the rounded cost to fractional vertex and edge variables — that may transfer to related tree and path covering problems with vertex costs.","Editorial inference: the 6-factor for bounded forest cover is likely not the end of the line; a tighter edge-decomposition or a better forest-cover approximation would directly lower it, and the 8-to-6 jump suggests trying to close the gap to the forest-cover ratio."],"forward_implications":["Every instance of the forest cover problem can be solved in polynomial time to within a factor of 2 of the LP optimum, by solving the LP and applying the component-wise MST rounding.","Because any α-approximation for forest cover would give an α-approximation for vertex cover on unit-weight edges, the ratio 2 cannot be improved without also improving vertex cover's approximation ratio, so the problem is closed under the same hardness assumptions.","The bounded forest cover problem has a 6-approximation algorithm, improving the previous 8-approximation, via edge-decomposing the trees returned by the 2-approximation for forest cover.","The probabilistic dual-fitting scheme implies that with O(n/ε⁴) random experiments, at least one of the produced primal forests is a (2+ε)-approximation with high probability, giving the first approximation factor arbitrarily close to 2 for arbitrary real weights in [0,1]."],"supporting_citations":[{"why":"Establishes vertex cover as one of Karp's NP-complete problems, the basis for the approximation-preserving reduction proving forest cover NP-complete.","marker":"[20]"},{"why":"Supplies the conditional vertex-cover hardness lower bound that makes the 2-approximation best possible under standard assumptions.","marker":"[4]"},{"why":"Provides the unconditional 1.36 hardness lower bound for vertex cover, used to frame the expected approximation limits.","marker":"[7]"},{"why":"Hall's theorem is the matching argument in Lemma 12, the step that bounds the contribution of low-fractional vertices in the pruning analysis.","marker":"[14]"},{"why":"Kruskal's algorithm is the method used to construct the minimum spanning tree in each LP-support component, and its edge order defines the loop invariant in the proof.","marker":"[23]"},{"why":"Supplies the edge-decomposition lemma for trees with bounded edge weights, which is the tool that converts the forest-cover 2-approximation into the 6-approximation for bounded forest cover.","marker":"[21]"},{"why":"Introduced the bounded forest cover problem with an 8-approximation algorithm, the baseline that Theorem 6 improves to 6.","marker":"[11]"},{"why":"Provides the Chernoff-Hoeffding bound used to show the averaged dual solution is feasible for the perturbed LP with high probability.","marker":"[8]"},{"why":"Supplies the polynomial-time algorithm for linear programs with two variables per inequality, used in the separation oracle for the exponentially many cycle-elimination constraints.","marker":"[19]"}],"fun_headline_variants":["Deterministic 2-approximation for forest cover via LP rounding","Forest cover gets deterministic 2-approx via LP rounding","LP rounding yields 2-approx for forest cover, improving bounded to 6","Forest cover: deterministic 2-approx; bounded improved to 6","Bounded forest cover 6-approx from LP rounding of forest cover"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the key component bound assumes that in the MST built from the LP support, every surviving vertex whose fractional LP value is below 0.5 has degree at least 2 after the tree is contracted; this follows only because the LP's vertex-cover constraint forbids edges joining two low-value vertices, and if that structural fact failed, the Hall's theorem matching step in Lemma 12 would break.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic 2-approximation for forest cover via LP rounding","Forest cover gets deterministic 2-approx via LP rounding","LP rounding yields 2-approx for forest cover, improving bounded to 6","Forest cover: deterministic 2-approx; bounded improved to 6","Bounded forest cover 6-approx from LP rounding of forest cover"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000965,"raw_usage":{"total_tokens":4042,"prompt_tokens":814,"completion_tokens":3228,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":430,"completion_tokens_details":{"reasoning_tokens":3133}},"tokens_in":430,"tokens_out":3228,"duration_ms":20464,"temperature":1.0,"reasoning_tokens":3133,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:02:39.862164+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a small weighted graph and check whether the returned forest ever satisfies wi(APX_FC) > 2·LP_OPT, or more directly, search for an LP-optimal support whose MST has, after deleting pendant low-valued vertices, a remaining vertex with x* < 0.5 and degree 1 in the contracted tree; if such an instance exists and the inequality of Lemma 12 fails, the 2-approximation proof collapses.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes vertex cover as one of Karp's NP-complete problems, the basis for the approximation-preserving reduction proving forest cover NP-complete."},{"cited_title":"In: 2009 24th Annual IEEE Conference on Computational Complexity","cited_arxiv_id":null,"evidence_quote":"Supplies the conditional vertex-cover hardness lower bound that makes the 2-approximation best possible under standard assumptions."},{"cited_title":"Classic Papers in Combinatorics pp","cited_arxiv_id":null,"evidence_quote":"Hall's theorem is the matching argument in Lemma 12, the step that bounds the contribution of low-fractional vertices in the pruning analysis."},{"cited_title":"Algorithmica69(2), 443–460 (2014)","cited_arxiv_id":null,"evidence_quote":"Supplies the edge-decomposition lemma for trees with bounded edge weights, which is the tool that converts the forest-cover 2-approximation into the 6-approximation for bounded forest cover."},{"cited_title":"In: Algorithms and Discrete Applied Mathematics: 9th International Conference, CALDAM 2023, Gandhinagar, India, February 9–11, 2023, Proceedings","cited_arxiv_id":null,"evidence_quote":"Introduced the bounded forest cover problem with an 8-approximation algorithm, the baseline that Theorem 6 improves to 6."},{"cited_title":"Theory of evolutionary computation: Recent developments in discrete optimization pp","cited_arxiv_id":null,"evidence_quote":"Provides the Chernoff-Hoeffding bound used to show the averaged dual solution is feasible for the perturbed LP with high probability."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time algorithm for linear programs with two variables per inequality, used in the separation oracle for the exponentially many cycle-elimination constraints."}],"review_version":1}