{"id":"f348ca89-ff76-40fc-ad6d-22d238f68d02","arxiv_id":"2506.22010","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The k-fault-tolerant basis problem for matroids is FPT with parameter k plus rank r, NP-hard for k=1, and NP-hard for every fixed rank at least 3.","lead":"This paper studies the minimum set of matroid elements that still spans the whole matroid after any k elements are deleted, a fault-tolerant generalization of a basis. It gives an FPT algorithm parameterized by redundancy k and matroid rank r, and shows the problem is hard when either parameter alone is fixed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the two flagged proof gaps are patchable and do not threaten Theorem 1.","rationale":"The reader's conditional verdict is justified: the paper states two derivation steps without proof, and both need a sentence of clarification. However, neither is load-bearing in the sense of threatening the correctness of Theorem 1. Proposition 3's upper bound can be proven with a weaker and true invariant about the sizes of the greedy blocks. Lemma 2's recursive coverage identity follows from an unstated but valid invariant that the recursion preserves closure. I independently checked the other potentially delicate points: the greedy h-uniform check is sound because all candidate elements lie in cl(X), hence in cl(Z); the Lemma 1 exchange argument does not require the greedy blocks to have full rank; and the size and runtime bounds are consistent with the claimed (kr)^{O(kr^4)} enumeration. The hardness side of the paper is somewhat terse, especially the reduction from General Position Subset Selection, but the central FPT claim is the main result and it holds under these repairs. Therefore I do not recommend changing the verdict; a request to patch the two proof details is appropriate but the result is not unverified or rejected.","tokens_in":16285,"tokens_out":46689,"duration_ms":554725,"concrete_test":"Re-run the proof of Proposition 3 with the corrected invariant that each greedy block X_i is an inclusion-maximal independent set of the remaining set, of size at most r. Verify that B' = ∪_{i=0}^k X_i is k-fault-tolerant via the existing pigeonhole and cl(X_i) argument, and that |B'| ≤ (k+1)r < |B|. If this proof step goes through, the only substantive gap feeding into Lemma 1 is closed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central FPT algorithm. The two places flagged by the reader are genuine proof gaps but both are easily repaired, and neither invalidates the main theorem. (1) In Proposition 3, the assertion that the greedy construction produces sets X_0,...,X_k each of size r is not justified: after removing previous blocks, the rank of the remaining set may drop, so an inclusion-maximal independent set can have size less than r. The fix is to allow each X_i to have size at most r. The same argument still works: for any F ⊆ B of size at most k, one block X_i avoids F, and since B \\ B' ⊆ cl(X_i), we get E(M) = cl(B \\ F) ⊆ cl(B' \\ F). Also |B'| = Σ|X_i| ≤ (k+1)r < |B|, giving the contradiction. (2) In Lemma 2, the identity cl(X) = ∪ cl(Y_S) needs the unstated invariant that each recursive call Important(M,S) returns a set spanning S, i.e. cl(Y_S) = cl(S). This invariant does hold by induction: for h=1 every nonempty subset of cl(S) spans S because S is a singleton; for h>1, the returned Y_S either equals cl(S), or equals a greedy h-uniform set containing S, or is a union of recursive outputs that individually span all (h-1)-subsets S' of the greedy set, which together span S. I also checked the greedy h-uniform construction: because every candidate x lies in cl(X), rank(Z ∪ {x}) = rank(Z) = h automatically, so checking only the new h-subsets S ∪ {x} is sufficient. The Lemma 1 exchange argument, the counting step, and the final enumeration over W appear sound. The paper's central claim survives.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies k-fault-tolerant bases: minimum-cardinality subsets B of a matroid ground set such that rank(B \\ F) = rank(M) for every F ⊆ B with |F| ≤ k. The main contribution is an FPT algorithm for Fault-Tolerant Basis parameterized by both k and the rank r, with running time (kr)^{O(kr^4)} · n^{O(1)} in the independence-oracle model. The algorithm constructs a bounded \"important\" set W via a recursive decomposition based on h-uniform sets, then enumerates candidate bases within W. The paper also proves the size bounds r + k ≤ |B| ≤ (k + 1)r, gives an O(n^2)-time algorithm for weighted partition matroids and for rank at most two, and presents lower bounds: W[1]-hardness for parameter k on linear matroids, NP-hardness for k = 1 on graphic matroids, and a claimed NP-hardness dichotomy for fixed rank r ≥ 3.","tokens_in":16619,"tokens_out":20766,"duration_ms":241094,"significance":"If the proof gaps are repaired, the FPT algorithm is a solid and nontrivial contribution: it gives a unifying treatment of fault-tolerant spanning structures in matroids and a tight dichotomy by k + r. The core derivations are from first principles; there is no circularity and no fitted-parameter tuning. The hardness parts use established external results as building blocks. The main reservation is that the fixed-rank lower-bound proof, as written, does not establish the stated dichotomy because the constructed matroid need not have the required rank.","major_comments":[{"comment":"The reduction from General Position Subset Selection does not ensure rank(M) = 3. The text says \"Note that rank(M) ≤ 3\" and then applies Proposition 3 to conclude that any k-fault-tolerant basis has size at least p = k + 3; this uses rank(M) = 3, which is not guaranteed. If the input point set P is collinear, the lifted vectors have rank 2, and a rank-2 matroid on that ground set has a k-fault-tolerant basis of size k + 2 = p - 1, which is at most the budget p. Thus a no-instance with collinear points can map to a yes-instance. The same issue propagates to the extension r > 3. The authors need either to prove that General Position Subset Selection remains hard when the point set has rank 3, or to give a rank-forcing construction that preserves the answer; the current argument is not a valid reduction to the rank-r problem.","section":"§6, proof of Theorem 2"},{"comment":"The identity cl(X) = ∪_{S ⊆ Z, |S| = h-1} cl(Y_S) is asserted without proving that each recursive output Y_S spans its input S. The induction hypothesis stated in Claim 1 covers only properties (i) and (ii); it does not include cl(Y_S) = cl(S). The base case h = 1 works because any nonempty subset of cl({e}) spans {e}, but for h > 1 the spanning property must be proved by induction and stated explicitly. If it failed, the union of cl(Y_S) could be a proper subset of cl(X), so the bounded core W could fail to contain a k-fault-tolerant basis. This is load-bearing because Lemma 2 is the engine of Theorem 1.","section":"Lemma 2, proof of Claim 1"},{"comment":"The upper-bound proof says \"as rank(B) = rank(M) and |B| > (k+1)r, such sets X_0, ..., X_k exist,\" where each X_i is an inclusion-maximal independent set in the remaining part of B. This is not justified: after removing previous blocks, the remaining set may have rank strictly smaller than r, so an inclusion-maximal independent set X_i can have size less than r. The proof should allow each X_i to have size at most r; then |B'| = Σ |X_i| ≤ (k+1)r < |B|, and the pigeonhole argument still works because B \\ B' ⊆ cl(X_i) for the chosen i. The paper should state this correction explicitly.","section":"Proposition 3"}],"minor_comments":[{"comment":"In the proof of property (ii), the last displayed line ends with \"= ∪_{i=1}^j Y_j\"; the index should be i, i.e., \"= ∪_{i=1}^j Y_i\".","section":"Lemma 2, Claim 1"},{"comment":"The reduction for r > 3 does not specify the budget b for the constructed instance. The proof should state b = (r - 3)(k + 1) + p and justify that any k-fault-tolerant basis meeting this budget must contain all newly added vectors and exactly p original vectors.","section":"§6, extension to r > 3"},{"comment":"The statement says \"For every integer k ≥ 1, it is NP-hard...\" but the cited hardness results are of different types: [13] handles k = 1 and [16] gives inapproximability for higher connectivity. The authors should clarify whether k is fixed or part of the input in this observation.","section":"Observation 1"}],"recommendation":"major_revision","confidential_remarks":"The reader's stress test focused on Lemma 2 and Proposition 3, and both are indeed patchable. The more serious issue I found is in Theorem 2: the rank of the constructed matroid is not guaranteed to be exactly r, and the yes/no behavior can flip for collinear inputs. The revision should address this first; if a valid rank-preserving reduction is supplied, the paper is acceptable modulo the other fixes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is real: Fault-Tolerant Basis admits an FPT algorithm parameterized by k+r, with a matching dichotomy (NP-hard for k=1, para-NP-hard for r>=3, poly for r<=2). I think Theorem 1 survives. The h-uniform core lemma is a genuinely new device, and the reduction of the problem to a bounded core W is clean.\n\nWhat the paper does well: it identifies a natural matroid formulation, relates it to bulk-robustness and k-edge-connected spanning subgraph, gives tight examples for the size bounds, and uses known hardness results correctly. The exchange argument in Lemma 1 is sound.\n\nSoft spots. There is one real gap, exactly where the reader points: Lemma 2's Claim 1 asserts cl(X) = union over S of cl(Y_S), where Y_S is the recursive output on S. This requires the invariant that Y_S spans S. The paper never states or proves it. It does hold—the base case works, the big-Z case returns a superset of S, and the union case inherits the invariant from recursive calls—but it needs to be explicit. As written, a reader cannot verify the equality.\n\nThe Proposition 3 concern is less serious than the reviewer's note suggests. The proof never claims each X_i has size r; it only needs each X_i to be independent, so |B'| <= (k+1)r. The greedy deletion step is valid for that bound. The proof is terse and could use a sentence saying each |X_i| <= r and the recursion is well-defined, but that is a clarification, not a fix.\n\nThe running-time analysis is believable; the oracle model is explicit. Lower bounds are built on published reductions used as black boxes; no fitting or post hoc selection.\n\nWho benefits: people working on parameterized algorithms for matroid problems, and anyone using fault-tolerant basis notions. It is not a practice-changing paper, but it settles a natural problem and introduces a reusable technique.\n\nRecommendation: this deserves a serious referee. If I were handling it, I would ask for a revision that states and proves the spanning invariant in Lemma 2 and expands the few terse lines in Proposition 3. Conditional accept.","headline":"The k+r FPT algorithm and the rank-based dichotomy are real; Theorem 1 holds, but Lemma 2 needs an explicit spanning invariant.","tokens_in":17167,"tokens_out":6990,"would_cite":true,"duration_ms":67455,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B35","68Q17","68Q25","68R05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a fixed-parameter tractable algorithm for finding a minimum set of matroid elements that stays spanning after any k deletions, parameterized by k plus the matroid's rank, and shows the parameterization is tight.","keywords":["matroids","fault tolerance","fixed-parameter tractable","h-uniform sets","matroid rank","independence oracle","NP-hardness","bulk-robust optimization"],"falsifier":"Run the algorithm Important(M,X) on a small matroid (for example, a rank-3 matroid with a 3-element circuit and a spanning element) and check after each recursive call whether cl(Y_S) contains S for every chosen (h−1)-subset S; if any call returns Y_S with S not contained in cl(Y_S), the identity cl(X)=∪ cl(Y_S) fails and the proof of Claim 1 collapses, which would mean the FPT algorithm can output a set W that excludes all k-fault-tolerant bases.","tokens_in":16091,"feed_emoji":"🛡️","tokens_out":5166,"duration_ms":61853,"temperature":0.7,"pith_summary":"The paper introduces Fault-Tolerant Basis: find a minimum-size set B of matroid elements such that after deleting any k of them, the rest still spans the entire ground set. The main result is a fixed-parameter tractable algorithm parameterized by both k and the matroid's rank r, running in (kr)^{O($kr^{4}$)} · $n^{{O(1)}}$ time on matroids given by independence oracles. This two-variable parameterization is shown to be tight: the problem is NP-hard already for k=1, para-NP-hard for rank at least 3, and polynomial-time solvable for rank at most 2. A sympathetic reader would care because the problem unifies fault-tolerance for vector spaces, graphs, and matching-like structures, so the algorithm and the hardness dichotomy give a single answer across these settings.","feed_headline":"Matroid bases that survive k deletions: FPT algorithm found","feed_subtitle":"A recursive core-shrinking method solves the problem fast when the failure count and rank are small.","key_machinery":"The key machinery is the h-uniform set and the recursive core construction built on it. A set X is h-uniform if rank(X)=|X|=h and every h-element subset of X has rank h; Observation 2 says a set of size k+r is k-fault-tolerant exactly when it is r-uniform. The algorithm Important(M,X) greedily builds a maximal h-uniform set Z inside cl(X); if Z is large enough, Lemma 1 guarantees that a k-fault-tolerant basis can be moved so that its part inside cl(X) lies in Z itself; otherwise the algorithm recurses on all (h−1)-element subsets S of Z and outputs the union of the returned sets, relying on the identity cl(X)=∪_{S⊆Z, |S|=h−1} cl(S) to cover the whole closure. The bounded size of Z, about (h−1)[(k+1)r]^{r−1}+(k+1)r, is what keeps the search space and the recursion depth under control.","core_discovery":"The central claim is that k-fault-tolerant matroid bases can be found efficiently when both the failure count k and the matroid rank r are small, and that this joint parameterization is the right one. The algorithm constructs a small core set W of elements such that, if any k-fault-tolerant basis exists, one exists entirely inside W; it then brute-forces over candidate subsets of W. The construction is driven by h-uniform sets, sets where every h-element subset has rank h, and uses the fact that a set of size k+r is a k-fault-tolerant basis exactly when it is r-uniform. The paper also proves that fixing k alone or r alone leaves the problem intractable, giving a clean dichotomy that separates the easy rank-2 case from the hard rank-3 and above case.","pith_inferences":["Beyond the paper: the h-uniform core-shrinking technique may transfer to the broader bulk-robust matroid basis model, where failure scenarios are arbitrary interdiction sets rather than all k-subsets; the recursion only needs the identity cl(X)=∪ cl(S) over (h−1)-subsets, which holds in any matroid, so a structured family of interdiction sets could be handled similarly if the core construction can","A testable extension: for linear matroids over a fixed field, one could try to derandomize the core construction or improve the running time to (kr)^{O(kr)} using more careful counting, which would be significant because the current exponent kr^4 is large even for moderate k and r.","The author leaves open whether the theorem extends to the weighted variant; if the exchange argument of Lemma 1 fails in the weighted setting, a plausible reason is that replacing an element outside X by an element inside X changes the weight, suggesting that weighted fault-tolerant bases may be genuinely harder than the unweighted case.","The NP-hardness for rank 3, based on planar point sets in general position, suggests that the rank-3 case is already as hard as a geometric packing problem, so the polynomial rank-2 result is likely the boundary of tractability for fixed ranks."],"forward_implications":["If the central claim is correct, then Fault-Tolerant Basis is fixed-parameter tractable with parameters k and r, meaning instances where both the number of failures and the matroid rank are small can be solved in time that grows polynomially with the ground set size n.","The tightness results imply that no FPT algorithm exists for the parameter k alone (since the problem is W[1]-hard for k) and no FPT or even polynomial algorithm exists for the parameter r alone for r ≥ 3, unless P = NP.","The rank-2 weighted case being polynomial-time solvable means that in the plane (rank 2 linear matroids), fault-tolerant bases can be computed in O(n^2) time even with weights.","The core-set reduction also shows the problem is in XP when parameterized by k, since after shrinking to W one can brute-force over subsets of size at most (k+1)r.","The equivalence between k-fault-tolerant bases and r-uniform sets of size k+r gives a direct certificate of fault-tolerance that could be checked without enumerating all failure sets."],"supporting_citations":[{"why":"Oxley's matroid theory text supplies the rank, closure, and basis definitions and the closure axioms used throughout the algorithm and proofs.","marker":"[20]"},{"why":"Fomin et al. provide the W[1]-hardness of Rank h-Reduction, which the paper reduces from to show that Fault-Tolerant Basis is W[1]-hard for parameter k.","marker":"[14]"},{"why":"Fernandes gives the NP-hardness of 2-edge-connected spanning subgraph via Hamiltonian cycle, used to show the problem is NP-hard for k=1 on graphic matroids.","marker":"[13]"},{"why":"Gabow et al. provide inapproximability lower bounds for higher edge-connectivity, which the paper uses to extend the k=1 hardness to all k ≥ 1 in Observation 1.","marker":"[16]"},{"why":"Froese et al. prove NP-hardness of General Position Subset Selection for rational planar points, the base problem the reduction uses to establish NP-hardness for rank r ≥ 3.","marker":"[15]"},{"why":"Lokshtanov et al. give the deterministic truncation of linear matroids, which the proof of Proposition 1 uses to construct the truncated matroid in the W[1]-hardness reduction.","marker":"[19]"}],"fun_headline_variants":["Survive any k deletions? Matroid bases get FPT solution","Core-shrinking FPT: k-fault-tolerant matroid bases","FPT for matroid bases that resist k failures","Fast fault-tolerant bases in matroids when k and rank are small"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recursive core construction assumes that each call Important(M,S) returns a set Y_S whose span still contains S, so that the closures of the (h−1)-element subsets S of Z genuinely cover the closure of X; if that spanning invariant fails for some S, the core set W may miss every k-fault-tolerant basis.","fun_headline_variants_meta":{"raw":{"variants":["Survive any k deletions? Matroid bases get FPT solution","Core-shrinking FPT: k-fault-tolerant matroid bases","FPT for matroid bases that resist k failures","Fast fault-tolerant bases in matroids when k and rank are small"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001449,"raw_usage":{"total_tokens":5794,"prompt_tokens":864,"completion_tokens":4930,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":4865}},"tokens_in":480,"tokens_out":4930,"duration_ms":40118,"temperature":1.0,"reasoning_tokens":4865,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:16:30.145351+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm Important(M,X) on a small matroid (for example, a rank-3 matroid with a 3-element circuit and a spanning element) and check after each recursive call whether cl(Y_S) contains S for every chosen (h−1)-subset S; if any call returns Y_S with S not contained in cl(Y_S), the identity cl(X)=∪ cl(Y_S) fails and the proof of Claim 1 collapses, which would mean the FPT algorithm can output a set W that excludes all k-fault-tolerant bases.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Oxley's matroid theory text supplies the rank, closure, and basis definitions and the closure axioms used throughout the algorithm and proofs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Fomin et al. provide the W[1]-hardness of Rank h-Reduction, which the paper reduces from to show that Fault-Tolerant Basis is W[1]-hard for parameter k."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Fernandes gives the NP-hardness of 2-edge-connected spanning subgraph via Hamiltonian cycle, used to show the problem is NP-hard for k=1 on graphic matroids."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gabow et al. provide inapproximability lower bounds for higher edge-connectivity, which the paper uses to extend the k=1 hardness to all k ≥ 1 in Observation 1."},{"cited_title":"Froese, I","cited_arxiv_id":null,"evidence_quote":"Froese et al. prove NP-hardness of General Position Subset Selection for rational planar points, the base problem the reduction uses to establish NP-hardness for rank r ≥ 3."},{"cited_title":"Lokshtanov, P","cited_arxiv_id":null,"evidence_quote":"Lokshtanov et al. give the deterministic truncation of linear matroids, which the proof of Proposition 1 uses to construct the truncated matroid in the W[1]-hardness reduction."}],"review_version":1}