{"id":"1bcd9ea6-704a-41fe-a025-d49209e746ea","arxiv_id":"2608.03801","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Partial Set Cover is inapproximable below factor 2 even at VC-dimension 7, while bounded semi-ladder index restores a k+1-sets covering target and yields new EPAS results.","lead":"This paper shows a sharp split between the two classic covering objectives: bounded VC-dimension makes fixed-budget coverage approximable, but the target-covering version is hard below factor 2 already at VC-dimension 7 (unless FPT = W[1]). A stronger parameter, the semi-ladder index, restores a k+1-sets guarantee and yields new approximation schemes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound half rests on two black-box hardness theorems whose exact gap/runtime hypotheses are not independently verified; a mismatch would collapse Theorems 3.6/3.10/3.13/3.14.","rationale":"The reader's weakest assumption already identifies the external hardness imports as the main threat to the lower-bound theorems; I agree that this is the most load-bearing part of the central claim. The internal reductions I checked are consistent and the probabilistic algorithmic half (Theorems 1.2 and 1.3) appears to be supported by the lemmas as written, modulo the known index-ordering typo in Lemma 5.7. The disagreement is only partial because the reader also lists the deterministic running-time dependence on Guillemot's algorithm and the Lemma 5.7 proof gap; I view the BSM/Lin black-box gap/runtime as more decisive, since the headline separation disappears if those exact hypotheses fail, whereas the other two items are localized and fixable. Since the reader's verdict was already CONDITIONAL and the concern does not change that assessment, I recommend keeping CONDITIONAL: the paper should be accepted only after the two external theorems are checked against the quoted statements and the precise parameters are confirmed.","tokens_in":64768,"tokens_out":19402,"duration_ms":226586,"concrete_test":"Obtain the exact statements of [Lin21, Theorem 1.2] and [BSM25, Theorem 1.1]. Verify: (a) Lin rules out distinguishing ω(H)≥k from ω(H)<δk in F(k)|V(H)|^a time for every fixed δ∈(0,1) and every constant a; (b) BSM gives, for every ζ>0, a D_ζ-regular bipartite 2-CSP with alphabet Σ that is ETH-hard to distinguish from value ≤ζ, with no algorithm faster than F(k)|Σ|^{k/log^{C_ζ} k}. Then recompute Theorems 3.10 and 3.13 using the exact exponent and gap; if the BSM runtime exponent is weaker (e.g., |Σ|^{o(k)} rather than |Σ|^{k/log^C k}), check whether the no-PAS argument at VC-dimension 7 and the fixed-factor lower bound still survive. If both quoted theorems match Proposition 3.3 and Proposition 3.7 verbatim, the lower-bound half is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's negative separation—bounded VC-dimension does not help target covering—is entirely conditional on Proposition 3.3, importing Lin's constant-factor k-Clique inapproximability as [Lin21, Theorem 1.2], and Proposition 3.7, importing BSM's ETH-hard regular 2-CSP with soundness ζ and running time F(k)|Σ|^{k/log^{C_ζ} k}. I checked the internal reductions: the row/blocking-list syntax, Lemma 3.2's trace bound, and the soundness arguments in Lemmas 3.4, 3.8, and 3.11 are coherent, and they genuinely convert the quoted gaps into the claimed VC-dimension-constrained Partial Set Cover gaps. But the manuscript does not restate the source theorems' full hypotheses. In particular, the label-selection and list constructions need (i) Lin's theorem to exclude F(k)n^a algorithms for every constant a and every fixed δ, not just for one fixed gap; and (ii) BSM's theorem to allow soundness ζ arbitrarily close to 1 with the very strong runtime F(k)|Σ|^{k/log^{C_ζ} k} and constant regularity D_ζ. If either theorem has a different gap parameter, a different running-time exponent, or requires the instance to satisfy additional restrictions, then Theorem 3.6's (2−δ) factor, Theorem 3.10's no-PAS conclusion, and the 2^{o(d)} trade-off in Theorems 3.13/3.14 would weaken or fail. The central boundary claim is therefore not self-contained at its most load-bearing point.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parameterized approximability of Maximum Coverage (fixed budget) versus Partial Set Cover (covering target) on set systems of bounded VC-dimension. Its central negative claim is that bounded VC-dimension does not support target-covering algorithms: assuming FPT != W[1], Partial Set Cover has no FPT (2-delta)-approximation even at VC-dimension 7; assuming ETH, it has no PAS at VC-dimension 7 and no 2^{o(d)}-approximation at VC-dimension d. These results are proved by reductions from Lin's k-Clique inapproximability and a regular low-soundness 2-CSP hardness of Bafna--Karthik--Minzer, using a unified rows-and-blocking-lists construction that yields the VC-dimension bounds. On the positive side, the paper introduces the semi-ladder index / downward intersection complexity Gamma as the right structural parameter: for Weighted Max RBDS it gives a randomized EPAS in (1/epsilon)^{O(Gamma k log k)} ||G|| time, and for Dec-Wt-Partial RBDS it gives an additive approximation that finds k+1 sets covering weight W whenever k sets can, in 2^{O(Gamma k log k)} ||G|| time. It further extends the framework to matroid/partition constraints, gives a deterministic FPT reduction from Weighted CC-MaxSAT to Weighted Maximum Coverage, and proposes a faster deterministic implementation of the BKL bounded-VC scheme.","tokens_in":64969,"tokens_out":18643,"duration_ms":190507,"significance":"If the two imported hardness theorems are exactly as quoted, the negative separation is a significant conceptual contribution: it shows that the EPAS for fixed-budget Maximum Coverage at bounded VC-dimension does not carry over to the target-covering objective. The positive framework is also substantial: it strictly generalizes the earlier K_{d,d}-free results, handles weights directly, and uses a clean skeleton/MustInclude invariant in which the downward intersection complexity bounds the recursion depth. The internal reductions and the main randomized algorithm are coherent, and the approximation factors and running times are derived rather than fitted, so the paper is not circular. The deterministic results and the improved BKL implementation extend the reach of the framework, although they rely on an external FPT Dominating Set subroutine whose running time is not stated.","major_comments":[{"comment":"The four lower-bound theorems are conditional on the exact statements of [Lin21, Thm 1.2] and [BSM25, Thm 1.1], paraphrased in Propositions 3.3 and 3.7. The internal reductions are coherent, but the hypotheses are load-bearing: Theorem 3.6 needs Lin's theorem to exclude F(k)n^a for every constant a and every fixed delta, while Theorems 3.10/3.13/3.14 need the BSM theorem with soundness zeta arbitrarily close to 1, running time F(k)|Sigma|^{k/log^{C_zeta} k}, and constant regularity D_zeta. If the source theorems have additional restrictions or different gap/runtime constants, the claimed (2-delta), no-PAS, and 2^{o(d)} conclusions weaken or fail. Please state the source theorems in full (ideally verbatim) and confirm that all parameters used here are covered by those statements.","section":"Sec. 3, Prop. 3.3 and 3.7 (Theorems 3.6, 3.10, 3.13, 3.14)"},{"comment":"The deterministic results (Theorem 1.5 and the Section 8 framework) invoke an FPT algorithm for Dominating Set on semi-ladder-free graphs [Gui25] without stating its running time. The claims such as '(k log k / epsilon)^{O(k)} * 2^{O~(kd/epsilon)} ||I||^{O(1)}' cannot be reproduced from this paper alone. Please give the exact running time of the dominating-set subroutine, state how it is combined with the weighted delta-net construction (Lemma 2.5), and derive the final deterministic bounds. Without this, the deterministic EPAS for CC-MaxSAT and the improved deterministic BKL implementation cannot be checked.","section":"Sec. 8, Lemma 2.5 and deterministic algorithms"},{"comment":"In the base case where mu(J)=0, the proof argues that if u in N(s_alpha) and u not in FreeCov_alpha, then DI(G, MustInclude_alpha cup {u}) >= Gamma+1 by Lemma 7.5. However, Lemma 7.5 has the hypothesis u in B \\ FreeCov(J), not merely u not in FreeCov_alpha. The gap is fixable: apply Lemma 7.5 only when u not in FreeCov(J); if u belongs to another FreeCov_beta, it is already covered by every consistent tuple and no contradiction is needed. Please correct this step, since the current proof does not establish the base case as written.","section":"Sec. 7, Lemma 7.6, base case"}],"minor_comments":[{"comment":"The proof gives success probability per run (epsilon/(2k))^{O(Gamma k)} and hence a running-time bound (2k/epsilon)^{O(Gamma k)} poly(||G||), which is (1/epsilon)^{O(Gamma k)} 2^{O(Gamma k log k)}. Stating Theorem 1.2 as (1/epsilon)^{O(Gamma k log k)} ||G|| is an overestimate; please align the displayed running time with the proof.","section":"Sec. 2.2.1 / Theorem 1.2"},{"comment":"The definition of DI(G, X) for X subseteq B uses chains of realizable sets but does not say what happens when X = emptyset or when IntExt(G, X) = emptyset; this leads to minor ambiguity in the proof of Lemma 5.7. A short convention would help.","section":"Sec. 5, Definition 5.5"},{"comment":"There are several typos and minor wording issues: 'conludes' in Lemma 2.2, 'suffice' in the introduction, and occasional 'we have'/'it holds' repetitions in Sections 6 and 7. A proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is well within the scope of cs.DS and makes a compelling conceptual claim. My main reservation is that the lower-bound half rests on two very strong external hardness theorems whose full hypotheses are not quoted; if either source theorem differs from the paraphrase, the central negative results weaken. The authors should also make the deterministic running-time claims reproducible by stating the Guillemot Dominating Set subroutine exactly. The base-case slip in Lemma 7.6 is local but should be fixed. I would not recommend rejection, as the positive algorithms appear sound and the reductions are internally coherent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main take: this is real work, not a desk reject. The separation between fixed-budget Maximum Coverage (EPAS via BKL) and target-covering Partial Set Cover (no (2-delta)-approximation at VC-dimension 7 under FPT != W[1], no PAS under ETH, no 2^{o(d)} at dimension d) is genuinely new, and the positive side--bounded semi-ladder index restoring the additive k+1 guarantee for weighted partial cover--is a solid contribution. The paper also correctly credits BKL for the existence of the fixed-budget EPAS; no overclaiming there.\n\nI checked the load-bearing internal lemmas: the exchange bound, the semi-ladder certification of skeletons, the trace bound for the row/blocking-list constructions, and the soundness of the three reductions. They hold up. The downward intersection complexity DI(G) is connected to the pre-existing semi-ladder index within an additive constant, so it's not an ad-hoc invented parameter.\n\nThe soft spots are real but proportionate. First, the negative results are conditional on Lin's constant-factor k-Clique inapproximability and BSM's regular low-soundness 2-CSP hardness. The paper restates both with the exact gap and runtime hypotheses it uses (Propositions 3.3 and 3.7), so the stress-test note that the hypotheses are 'not restated' is too strong; what is true is that those theorems are very strong, and the reductions inherit any error in the cited versions. A referee must verify the statements against the sources. That's a verification task, not a flaw in the paper's internal logic.\n\nSecond, the deterministic counterparts in Section 8 depend on Guillemot's FPT Dominating Set algorithm, whose running time is never stated. As written, the deterministic runtime claims cannot be reproduced from this paper alone. That's a genuine reproducibility gap, though likely fixable by pinning down the cited bound. Third, Lemma 5.7's proof has a direction-inconsistent index argument; it looks like a typo, and reversing the enumeration on one side fixes it. Minor.\n\nWho is this for: parameterized algorithms researchers, especially those working on covering problems and structural graph parameters. The technical overview in Section 2 is well-written and conveys the main ideas; the rest is long but structured. I would send it to a serious referee. With the black-box theorems verified and the deterministic running times pinned down, it should be accepted. My own verdict is conditional accept with minor revisions.","headline":"A serious, dense theory paper that likely resolves the target-covering boundary for bounded VC-dimension; the lower-bound half leans on two very strong black-box theorems that need referee verification, but the internal reductions are sound.","tokens_in":65726,"tokens_out":2857,"would_cite":true,"duration_ms":33453,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q27","68W25","68Q17","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"Bounded VC-dimension makes fixed-budget Maximum Coverage tractable, but the target-covering version Partial Set Cover stays hard: under FPT≠W[1] it has no FPT (2−δ)-approximation even at VC-dimension 7, and under ETH no parameterized approx","keywords":["Partial Set Cover","Maximum Coverage","VC-dimension","parameterized approximation","EPAS","semi-ladder index","downward intersection complexity","CC-MaxSAT"],"falsifier":"Run the Section 3.1 row-and-blocking-list construction on a sequence of graphs H with no k-clique and check whether any FPT algorithm can distinguish Partial Set Cover instances with optimum at most k from those with optimum greater than (2−δ)k, all having VC-dimension at most 7. Producing such an algorithm, or a correct (2−δ)-approximation for VC-dimension-7 Partial Set Cover, would directly falsify the main separation.","tokens_in":64451,"feed_emoji":"🎯","tokens_out":7612,"duration_ms":81259,"temperature":0.7,"pith_summary":"The paper draws a sharp structural boundary between the two parameterized covering objectives at bounded VC-dimension. For the fixed-budget objective, Maximum Coverage, bounded VC-dimension supports efficient parameterized approximation schemes. For the target-covering objective, Partial Set Cover, the same structure fails: assuming FPT≠W[1], no FPT algorithm approximates within factor below 2, even on VC-dimension-7 instances, and under ETH there is no parameterized approximation scheme there and no 2^{o(d)}-approximation at VC-dimension d. The paper then shows that the stronger hypothesis of bounded semi-ladder index restores the target guarantee: if k sets cover weight W, a randomized FPT algorithm finds k+1 sets covering weight W in time 2^{O(Γk log k)} times the input size. This locates the boundary fairly precisely: bounded VC-dimension alone is enough for budgeted coverage, but target covering needs the extra semi-ladder structure.","feed_headline":"No factor-2 FPT approximation for Partial Set Cover at VC-dimension 7","feed_subtitle":"The same structure that makes budgeted coverage easy leaves target covering hard; bounded semi-ladder index restores it.","key_machinery":"The central objects are the semi-ladder and the closely related downward intersection complexity Γ of the incidence bipartite graph. A semi-ladder is a two-sided sequence of red vertices r_1,…,r_d and blue vertices b_1,…,b_d with edges (r_i,b_j) exactly when i>j and missing diagonal edges (r_i,b_i); Γ measures the length of chains of realizable subsets and differs from the semi-ladder index by at most one. The lower bounds use a synthetic row-and-blocking-list syntax: each element is sensitive to at most two positions and each sensitivity is blocked by at most q labels, and a trace bound on such q-local set systems caps the VC-dimension automatically. The algorithms maintain k MustInclude sk","core_discovery":"The central claim is that for parameterized approximation, bounded VC-dimension is the right regime for fixed-budget Maximum Coverage but provably not for target-covering Partial Set Cover. The lower-bound half shows that all three target-covering barriers occur at tiny VC-dimension: a row-and-blocking-list reduction from the constant-factor inapproximability of k-Clique rules out (2−δ)-approximation at VC-dimension 7; a regular low-soundness 2-CSP reduction rules out a PAS under ETH at VC-dimension 7; and a list version raises VC-dimension only logarithmically in the ratio, ruling out 2^{o(d)}-approximation at VC-dimension d. The algorithmic half identifies bounded semi-ladder index, a para","pith_inferences":["The row-and-blocking-list method gives a reusable template for proving target-side hardness while keeping VC-dimension constant, so other fixed-budget versus target-covering pairs (influence, clustering, or domination variants) may display the same split.","The (2−δ) barrier is left open at intermediate dimensions: the paper rules out approximation below 2 at dimension 7, but does not construct instances showing that factor 2 itself is achievable there.","Because the semi-ladder index is a single numeric parameter, one could investigate intermediate regimes where Γ is large but not unbounded, asking whether running time degrades smoothly with Γ.","The improved trace-enumeration insight is independent of the target-covering question and may speed up other reductions that call the bounded-VC Maximum Coverage scheme as a subroutine."],"forward_implications":["Target-covering is intrinsically harder than budgeted coverage under bounded VC-dimension: no EPAS, no PAS, and no factor-2 FPT approximation can be built on VC-dimension alone.","On bounded semi-ladder index instances, Weighted Partial Set Cover gets a randomized additive guarantee: k+1 sets instead of k, with the same weight W, in FPT time 2^{O(Γk log k)}N, and this yields a PAS for the partial-cover version.","Weighted CC-MaxSAT inherits an EPAS at bounded semi-ladder index and, via the improved deterministic trace-enumerated implementation of the bounded-VC Maximum Coverage scheme, an EPAS at bounded VC-dimension with running time 2^{O~(kd/ε)}N^{O(1)}.","The same branching framework extends to per-class coverage targets and matroid independence constraints, covering partial dominating set, geometric partial covering, and bounded-size covering problems.","Deterministic counterparts exist through weighted δ-nets of size O((Γ/δ) log(1/δ)), giving deterministic EPAS/PAS with the same structural parameters."],"supporting_citations":[{"why":"Supplies the fixed-budget EPAS for Maximum Coverage on bounded-VC set systems; the paper improves its deterministic implementation and uses it as the contrast for target-covering hardness.","marker":"[BKL12]"},{"why":"Provides the constant-factor FPT inapproximability of k-Clique used as the source for the no-(2−δ) FPT approximation at VC-dimension 7.","marker":"[Lin21]"},{"why":"Provides the ETH-hard regular, low-soundness 2-CSP gap used to rule out a PAS at VC-dimension 7 and to derive the 2^{o(d)} approximation lower bound.","marker":"[BSM25]"},{"why":"Establishes the K_{d,d}-free target-covering guarantee (k+1 sets when k sets meet the target) that the paper generalizes to bounded semi-ladder index and contrasts with the VC-dimension boundary.","marker":"[JKP+23]"},{"why":"Introduces semi-ladders and the FPT machinery for Dominating Set and Set Cover on bounded semi-ladder instances, grounding the structural parameter and the deterministic net construction.","marker":"[FPST19]"},{"why":"Gives the FPT algorithm for Dominating Set on semi-ladder-free graphs used in the deterministic weighted δ-net and derandomization results.","marker":"[Gui25]"},{"why":"Supplies the matroid representative-family lemma used in the constrained extension and a prior CC-MaxSAT-to-Maximum-Coverage reduction whose structure the deterministic reduction refines.","marker":"[IJL+24]"},{"why":"The Sauer–Shelah shatter-function bound is used to count only realized traces, reducing the deterministic bounded-VC Maximum Coverage running time.","marker":"[Sau72]"},{"why":"Provides a lossy kernel for CC-MaxSAT on K_{d,d}-free formulas, serving as the starting point and comparison baseline for the reduction from Weighted CC-MaxSAT.","marker":"[Man25]"}],"fun_headline_variants":["VC-dim 7 kills factor-2 FPT for Partial Set Cover","Semi-ladder index restores k+1 sets for weighted targets","Partial Set Cover: no FPT 2-approx at VC-dim 7","Weighted CC-MaxSAT gets EPAS under bounded semi-ladder","Bounded VC-dim fails for target covering; semi-ladder wins"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The lower-bound half imports two black-box hardness theorems — constant-factor FPT inapproximability of k-Clique and an ETH-hard regular low-soundness 2-CSP gap with running time F(k)|Σ|^{k/log^{Cζ} k} — and if either stated gap or running-time exponent is weaker than cited, the main separation theorems weaken or fall; the deterministic half additionally assumes an FPT Dominating Set algorithm whose exact running time is never stated.","fun_headline_variants_meta":{"raw":{"variants":["VC-dim 7 kills factor-2 FPT for Partial Set Cover","Semi-ladder index restores k+1 sets for weighted targets","Partial Set Cover: no FPT 2-approx at VC-dim 7","Weighted CC-MaxSAT gets EPAS under bounded semi-ladder","Bounded VC-dim fails for target covering; semi-ladder wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001349,"raw_usage":{"total_tokens":5420,"prompt_tokens":950,"completion_tokens":4470,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":4383}},"tokens_in":694,"tokens_out":4470,"duration_ms":36469,"temperature":1.0,"reasoning_tokens":4383,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:15:42.160444+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Section 3.1 row-and-blocking-list construction on a sequence of graphs H with no k-clique and check whether any FPT algorithm can distinguish Partial Set Cover instances with optimum at most k from those with optimum greater than (2−δ)k, all having VC-dimension at most 7. Producing such an algorithm, or a correct (2−δ)-approximation for VC-dimension-7 Partial Set Cover, would directly falsify the main separation.","supporting_citations":[],"review_version":1}