Introduction
Fault tolerance has been extensively studied in network design, matching, and distributed storage. In these settings, the aim is to preserve a required function despite the failure of some components—for example, maintaining connectivity after link failures, retaining a perfect matching after edge deletions, or recovering data when storage nodes become unavailable; see, e.g., [5 , 8 , 11 ] . A central algorithmic question is how to provide the necessary redundancy at minimum cost.
For spanning problems, the need for redundancy is immediate. A basis spans a vector space, but losing even one basis vector reduces its span. To withstand failures, we must select a larger collection whose surviving vectors continue to span the original space. Similarly, a spanning tree connects a graph, but additional edges are needed to preserve connectivity after links fail. Matroids provide a common framework for these two requirements through the notion of a spanning set.
Given a matroid M M M and a nonnegative integer k k k , the Fault-Tolerant Basis problem asks for a smallest set B ⊆ E ( M ) B \subseteq E(M) B ⊆ E ( M ) such that B ∖ F B \setminus F B ∖ F spans M M M for every F ⊆ B F \subseteq B F ⊆ B with ∣ F ∣ ≤ k |F| \leq k ∣ F ∣ ≤ k , or a report that no such set exists. For k = 0 k = 0 k = 0 , this is the ordinary basis problem; for k ≥ 1 k \geq1 k ≥ 1 , the selected set must contain enough redundancy to withstand the allowed failures.
Bentert, Fomin, Golovach, and Morelle (ESA 2025) [3 ] studied the parameterized complexity of this problem. Their main result is an algorithm running in ( k r ) O ( k r 4 ) n O ( 1 ) (kr)^{O(kr^4)}n^{O(1)} ( k r ) O ( k r 4 ) n O ( 1 ) time for rank-r r r matroids on n n n elements given by an independence oracle, where k k k is the number of failures to be tolerated. Thus, the problem is fixed-parameter tractable when parameterized by r + k r + k r + k .
They left open the following questions:
Weighted costs. Does fixed-parameter tractability in r + k r + k r + k extend to the problem of finding a minimum-cost fault-tolerant spanning set when elements have arbitrary nonnegative costs?
Nonuniform failures. Does this tractability extend to the model in which the ground set is partitioned into safe and vulnerable elements, and only vulnerable elements may fail?
Explicit failure scenarios. Can their results be extended to the setting in which the possible failure scenarios are explicitly supplied as part of the input?
These questions are the starting point of our work. We first address weighted costs and nonuniform failures together, and then study explicitly listed failure scenarios.
Our Results and Tools
For ease of presentation, we first state the problem explicitly. In Weighted Nonuniform Fault-Tolerant Basis, the input consists of a rank-r r r matroid M = ( E , I ) M = (E, \mathcal{I}) M = ( E , I ) , nonnegative integer costs w : E → Z ≥ 0 w : E \to\mathbb{Z}_{\geq0} w : E → Z ≥ 0 , a partition E = S ∪ ˙ V E = S \mathbin{\dot\cup} V E = S ∪ ˙ V into safe and vulnerable elements, and a failure budget k ≥ 0 k \geq0 k ≥ 0 . The task is to find a minimum-cost set B ⊆ E B \subseteq E B ⊆ E satisfying
rank M ( B ∖ F ) = r for every F ⊆ B ∩ V with ∣ F ∣ ≤ k , \operatorname{rank}_{M}(B \setminus F) = r \qquad\text{for every } F \subseteq B \cap V \text{ with } |F| \leq k, rank M ( B ∖ F ) = r for every F ⊆ B ∩ V with ∣ F ∣ ≤ k ,
or report that no such set exists. The ordinary weighted model is the special case S = ∅ S = \varnothing S = ∅ . The surviving selected elements must span the original matroid; the target rank does not change when a failure occurs.
Throughout, n = ∣ E ∣ n = |E| n = ∣ E ∣ and costs are encoded in binary. The cases r = 0 r = 0 r = 0 and k = 0 k = 0 k = 0 are polynomial-time solvable; the exponential bounds below concern r , k ≥ 1 r, k \geq1 r , k ≥ 1 . Section 2 specifies the computational conventions.
Our first result shows that weighted costs and nonuniform failures can be handled simultaneously: the problem remains fixed-parameter tractable when parameterized by the rank and the failure budget. This answers the first two questions of Bentert et al. Moreover, the algorithm requires only an independence oracle.
Theorem 1. Weighted Nonuniform Fault-Tolerant Basis on rank-r r r matroids given by independence oracles is solvable in
2 O ( b log b + b r log ( r + k − 1 k ) ) n O ( 1 ) , 2^{O\left(b\log b+br\log\binom{r+k-1}{k}\right)}n^{O(1)}, 2 O ( b l o g b + b r l o g ( k r + k − 1 ) ) n O ( 1 ) , where b = ( k + 1 ) r b=(k+1)r b = ( k + 1 ) r .
In particular, the problem is solvable in 2 O ( ( r + k ) 4 ) n O ( 1 ) 2^{O((r+k)^4)}n^{O(1)} 2 O (( r + k ) 4 ) n O ( 1 ) time.
The algorithm constructs an optimum-preserving core : a subset of the ground set whose size depends only on r r r and k k k and which contains a minimum-cost feasible solution, whenever one exists. Section 3 gives the construction and its analysis.
When the matroid is given by an explicit linear representation, we can use its algebraic structure to obtain a second algorithm with a different dependence on r r r and k k k . This algorithm is deterministic and works over arbitrary fields. Its main ingredient is a compression method for families of partial solutions.
Theorem 2. On an explicitly represented linear matroid, Weighted Nonuniform Fault-Tolerant Basis is solvable deterministically in
2 O ( k r ( r + k ) log ( r + 1 ) ) n O ( 1 ) 2^{O(kr(r+k)\log(r+1))}n^{O(1)} 2 O ( k r ( r + k ) l o g ( r + 1 )) n O ( 1 ) field operations. Over standard exact representations of finite fields and over the rationals, the algorithm also has fixed-parameter bit complexity.
The algorithm processes elements one at a time, retaining a bounded family of partial selections. Whenever a partial selection admits a feasible completion, a retained selection of no greater cost must work with that same completion under all allowed failures. Polynomial certificates enforce this guarantee; we explain the idea in the overview below.
Section 4 gives the certificate, the dynamic program, and its full complexity analysis.
Over a fixed finite field, a simpler reduction is possible. A rank-r r r representation has a number of nonloop parallel classes bounded in terms of r r r alone, and we retain only a bounded number of inexpensive elements from each class. This gives the following running-time bound.
Corollary 1. For every fixed finite field F Q \mathbb{F}_Q F Q , Weighted Nonuniform Fault-Tolerant Basis is solvable in
2 O ( k r 2 + k r log ( k + 2 ) ) n O ( 1 ) . 2^{O(kr^2+kr\log(k+2))}n^{O(1)}. 2 O ( k r 2 + k r l o g ( k + 2 )) n O ( 1 ) . In particular, for every fixed failure budget k k k , the running time is 2 O ( r 2 ) n O ( 1 ) 2^{O(r^2)}n^{O(1)} 2 O ( r 2 ) n O ( 1 ) .
The oracle and algebraic algorithms offer different advantages. When k = r k = r k = r , their running-time exponents are O ( r 4 ) O(r^4) O ( r 4 ) and O ( r 3 log ( r + 1 ) ) O(r^3 \log(r + 1)) O ( r 3 log ( r + 1 )) , respectively. For fixed r ≥ 2 r \ge2 r ≥ 2 and growing k k k , the oracle bound has exponent O ( k log ( k + 1 ) ) O(k \log(k+1)) O ( k log ( k + 1 )) , whereas the algebraic bound has exponent O ( k 2 ) O(k^2) O ( k 2 ) . Thus, on a represented linear matroid, we may use whichever algorithm gives the better bound.
Overview of the compression methods. Both algorithms start from the observation that, whenever a feasible solution exists, some minimum-cost solution contains at most b = ( k + 1 ) r b = (k+1)r b = ( k + 1 ) r elements. This follows by extending the independent-layer argument of Bentert et al. [3 ] to weighted costs and nonuniform failures. However, enumerating all sets of at most b b b elements takes n O ( b ) n^{O(b)} n O ( b ) time, which does not give fixed-parameter tractability. We therefore need to reduce the search space while preserving an optimum. Our two algorithms do this in different ways: the oracle algorithm retains a bounded subset of the ground set, whereas the linear algorithm retains bounded families of partial selections. Figure 1 summarizes these two approaches.
Figure 1. Two alternative algorithms for weighted safe/vulnerable fault-tolerant spanning. The oracle core contains an optimum. Linear compression preserves every successful future completion at no greater cost. The right-hand loop runs until all input elements have been processed.
An optimum-preserving oracle core: We construct a retained set W W W with the following replacement property. For every feasible selection B B B of size at most b b b and every x ∈ B ∖ W x \in B \setminus W x ∈ B ∖ W , there is an element y ∈ W ∖ B y \in W \setminus B y ∈ W ∖ B of the same safety type as x x x , with w ( y ) ≤ w ( x ) w(y) \le w(x) w ( y ) ≤ w ( x ) , such that ( B ∖ { x } ) ∪ { y } (B \setminus\{x\}) \cup\{y\} ( B ∖ { x }) ∪ { y } remains feasible. Here, having the same safety type means that both elements are safe or both are vulnerable. Starting with an optimum of size at most b b b , repeated replacements therefore produce an optimum contained in W W W . The challenge is to construct a bounded set W W W that guarantees these replacements without knowing the optimum, while preserving spanning under every allowed failure.
To understand which replacements are valid, fix a feasible selection B B B and an element x ∈ B x \in B x ∈ B , and write Y = B ∖ { x } Y = B \setminus\{x\} Y = B ∖ { x } . Consider a failure set F ⊆ Y ∩ V F \subseteq Y \cap V F ⊆ Y ∩ V with ∣ F ∣ ≤ k \lvert F\rvert\le k ∣ F ∣ ≤ k . If Y ∖ F Y \setminus F Y ∖ F already spans, no replacement is needed for this failure. Otherwise, feasibility of B B B implies that adding x x x restores full rank, so Y ∖ F Y \setminus F Y ∖ F has rank r − 1 r-1 r − 1 . Its closure is therefore a hyperplane, and a replacement y y y restores spanning exactly when it lies outside that hyperplane. Thus, one element outside all these hyperplanes works for every failure in which y y y survives. If y y y itself fails, feasibility follows from the corresponding failure of x x x in B B B .
Although there may be many failure sets, they define only a bounded number of distinct obstructing hyperplanes. Indeed, the complement of each such hyperplane in the restriction M ∣ B M\vert B M ∣ B is a cocircuit containing x x x and contained in F ∪ { x } F \cup\{x\} F ∪ { x } , so it has size at most k + 1 k+1 k + 1 . A deletion–contraction argument bounds the number of these cocircuits by ( r + k − 1 k ) \binom{r+k-1}{k} ( k r + k − 1 ) . Each obstructing hyperplane is the closure of a subset of B B B , so its intersection with B B B determines it; distinct hyperplanes therefore give distinct cocircuits in M ∣ B M\vert B M ∣ B .
This reduces the replacement task to avoiding a bounded family of hyperplanes. Our weighted flat-avoidance construction processes elements in nondecreasing cost order and limits the number retained in each flat according to its rank. It ensures that every discarded element has a retained substitute of no greater cost outside all the obstructing hyperplanes and outside the other selected elements. Applying this construction separately to safe and vulnerable elements gives the replacement property above, and hence the core used in Theorem 1.
Polynomial certificates for common completions: The linear algorithm compresses families of partial selections with the same safe and vulnerable counts and the same rank. For each partial selection P P P , we construct a polynomial G P G_P G P . A future completion Z Z Z determines a symbolic substitution ev Z \operatorname{ev}_Z ev Z , common to all partial selections in the state, such that
ev Z ( G P ) ≠ 0 ⟺ P ∪ Z survives every allowed failure. \operatorname{ev}_Z(G_P) \ne0 \quad\Longleftrightarrow\quad P \cup Z\text{ survives every allowed failure.} ev Z ( G P ) = 0 ⟺ P ∪ Z survives every allowed failure.
For each failure pattern, a determinant tests whether the surviving past and future elements span. We multiply these tests in one polynomial ring. After the substitution for Z Z Z , the product is nonzero exactly when every factor is nonzero, so one certificate enforces all failure requirements for the same completion. Nonvanishing here means that the resulting formal polynomial is not identically zero.
We then regard each G P G_P G P as a coefficient vector in a common monomial basis. Processing partial selections in nondecreasing cost order, we retain a vector only if it is linearly independent of the vectors already retained. Every discarded polynomial is therefore a linear combination of retained polynomials of no greater cost. Since the completion substitution is linear,
G P = ∑ i α i G P i , ev Z ( G P ) ≠ 0 ⟹ ev Z ( G P i ) ≠ 0 for some i . G_P = \sum_i \alpha_i G_{P_i}, \qquad\operatorname{ev}_Z(G_P) \ne0 \quad\Longrightarrow\quad\operatorname{ev}_Z(G_{P_i}) \ne0 \text{ for some } i. G P = i ∑ α i G P i , ev Z ( G P ) = 0 ⟹ ev Z ( G P i ) = 0 for some i .
Thus, whenever a completion works for a discarded partial selection, it also works for one retained selection of no greater cost. That one retained selection withstands all allowed failures, because its certificate already combines all the failure tests. This cost-ordered basis selection follows the representative-family paradigm [9 ] . The construction also relates to representative families under several matroid constraints [4 ] ; here the failure requirements are combined in a shared polynomial ring.
The main challenge is to construct the certificates in a coefficient space of bounded dimension. We represent future columns through shared formal moment vectors and use polynomial filters to remove failed future slots. This allows every determinant test to use the same variables: taking their product increases the degree without introducing new variables for each failure pattern. Bounding the number of variables and the degree then bounds the number of retained partial selections. The construction uses formal polynomials throughout and requires neither random evaluation nor a large field.
Explicit Failure Scenarios
We next address the question of Bentert et al. [3 ] concerning explicitly specified failures. Instead of allowing every set of at most k k k vulnerable elements to fail, the input supplies a family F = { F 1 , … , F m } \mathcal{F} = \{F_1, \ldots, F_m\} F = { F 1 , … , F m } of failure scenarios. The task is to find a minimum-cost spanning set B B B such that B ∖ F i B \setminus F_i B ∖ F i spans the matroid for every i ∈ [ m ] i \in[m] i ∈ [ m ] . This is the bulk-robust matroid basis model of Adjiashvili, Stiller, and Zenklusen [2 ] .
Our results distinguish the number of scenarios from their maximum size. Parameterized by the rank r r r and the number m m m of scenarios, the problem is fixed-parameter tractable on independence-oracle matroids. For explicitly represented linear matroids, we obtain an algorithm using 2 O ( r m ) n O ( 1 ) 2^{O(rm)}n^{O(1)} 2 O ( r m ) n O ( 1 ) field operations when m ≥ 1 m \ge1 m ≥ 1 . In contrast, the size-budget decision version is W[1 ] -hard parameterized by rank and maximum scenario size, even on uniform matroids when every scenario contains only two elements. Thus, bounding the size of each failure scenario does not provide the same tractability as bounding the number of scenarios. Section 5 gives the algorithms and the hardness proof.
Related Work
The complexity on transversal matroids and gammoids was another question raised by Bentert et al. [3 ] . A construction of Adjiashvili, Bindewald, and Michaels [1 ] for robust assignment already implies NP-hardness on these classes, even when only one element may fail. We present this construction in matroid language and observe that its optimum identity also yields W[2 ] -hardness parameterized by the solution budget minus the rank. Section 6 gives the construction and the parameterized consequence in detail.
Adjiashvili, Stiller, and Zenklusen [2 ] introduced the bulk-robust framework and studied approximation algorithms for explicitly supplied failure scenarios, including the matroid basis problem. Our scenario results concern exact algorithms and their parameterized complexity. Robust-recoverable bases, as studied by Ito et al. [12 ] , impose overlap or limited-change requirements on a chosen basis. In our model, the selected set purchases redundancy before any failure, and the surviving elements must contain a basis after every allowed failure.
Dey and Kavitha [7 ] study a related weighted preserver: after every bounded failure, its surviving elements contain a minimum-cost basis of the surviving input matroid. Their construction uses successive minimum-cost bases. The two objectives charge for different sets. A basis preserver retains an optimal basis to be chosen after a failure; our objective minimizes the total cost of the set purchased before failures, subject to preserving the original rank. Consequently, preserving a minimum-cost basis after each failure does not by itself ensure that the retained ground set contains an optimum for our objective.
Organization. Section 2 gives the preliminaries. Sections 3 and 4 develop the oracle and linear-matroid algorithms, respectively. Section 5 treats explicit failure scenarios, and Section 6 presents the robust-assignment reduction and its hardness consequences.
Preliminaries
We use standard matroid terminology and parameterized-complexity notions. All ground sets and failure families are finite. For an integer a ≥ 0 a \ge0 a ≥ 0 , write [ a ] = { 1 , … , a } [a] = \{1,\ldots,a\} [ a ] = { 1 , … , a } , with [ 0 ] = ∅ [0] = \emptyset [ 0 ] = ∅ . Throughout, n = ∣ E ∣ n = |E| n = ∣ E ∣ and costs are nonnegative integers given in binary. For X ⊆ E X \subseteq E X ⊆ E , write w ( X ) = ∑ e ∈ X w ( e ) w(X) = \sum_{e \in X} w(e) w ( X ) = ∑ e ∈ X w ( e ) . A selected set need not be independent as fault tolerance may require selecting more elements than the matroid rank. We write L i n L_{\mathrm{in}} L in for the total input encoding length; this is distinct from the ground-set size n n n .
Matroid terminology. A matroid M = ( E , I ) M = (E,\mathcal{I}) M = ( E , I ) consists of a ground set E E E and a nonempty family I \mathcal{I} I of independent sets satisfying:
∅ ∈ I \emptyset\in\mathcal{I} ∅ ∈ I ,
if A ⊆ B ⊆ E A \subseteq B \subseteq E A ⊆ B ⊆ E and B ∈ I B \in\mathcal{I} B ∈ I then A ∈ I A \in\mathcal{I} A ∈ I and
if A , B ∈ I A, B \in\mathcal{I} A , B ∈ I with ∣ A ∣ < ∣ B ∣ |A| < |B| ∣ A ∣ < ∣ B ∣ , some e ∈ B ∖ A e \in B \setminus A e ∈ B ∖ A satisfies A ∪ { e } ∈ I A \cup\{e\} \in\mathcal{I} A ∪ { e } ∈ I .
For X ⊆ E X \subseteq E X ⊆ E , its rank is rank M ( X ) = max { ∣ I ∣ : I ⊆ X , I ∈ I } \operatorname{rank}_{M}(X) = \max\{|I| : I \subseteq X, I \in\mathcal{I}\} rank M ( X ) = max { ∣ I ∣ : I ⊆ X , I ∈ I } . Write r = rank M ( E ) r = \operatorname{rank}_{M}(E) r = rank M ( E ) . A basis of X X X is a maximal independent subset of X X X ; it has size rank M ( X ) \operatorname{rank}_{M}(X) rank M ( X ) . A set X X X spans M M M if rank M ( X ) = r \operatorname{rank}_{M}(X) = r rank M ( X ) = r . Adding or deleting one element changes rank by at most one. The closure of X X X is
cl M ( X ) = { e ∈ E : rank M ( X ∪ { e } ) = rank M ( X ) } . \operatorname{cl}_{M}(X) = \{e \in E : \operatorname{rank}_{M}(X \cup\{e\}) = \operatorname{rank}_{M}(X)\}. cl M ( X ) = { e ∈ E : rank M ( X ∪ { e }) = rank M ( X )} .
We use the following standard closure properties:
X ⊆ cl M ( X ) , cl M ( cl M ( X ) ) = cl M ( X ) , rank M ( cl M ( X ) ) = rank M ( X ) . X \subseteq\operatorname{cl}_{M}(X), \qquad\operatorname{cl}_{M}(\operatorname{cl}_{M}(X)) = \operatorname{cl}_{M}(X), \qquad\operatorname{rank}_{M}(\operatorname{cl}_{M}(X)) = \operatorname{rank}_{M}(X). X ⊆ cl M ( X ) , cl M ( cl M ( X )) = cl M ( X ) , rank M ( cl M ( X )) = rank M ( X ) .
Closure is monotone: if X ⊆ Y X \subseteq Y X ⊆ Y , then cl M ( X ) ⊆ cl M ( Y ) \operatorname{cl}_{M}(X) \subseteq\operatorname{cl}_{M}(Y) cl M ( X ) ⊆ cl M ( Y ) . A flat is a set equal to its closure. For r ≥ 1 r \ge1 r ≥ 1 , a hyperplane is a flat of rank r − 1 r-1 r − 1 , and a cocircuit is the complement of a hyperplane. A rank-zero matroid has no hyperplanes or cocircuits.
A circuit is an inclusion-minimal dependent set. An element e e e is a loop if { e } \{e\} { e } is dependent and a coloop if it belongs to every basis. Two distinct nonloop elements are parallel if they form a circuit. A matroid is simple if it has no loops or parallel pairs. We omit the subscript M M M when the matroid is clear.
The restriction M ∣ X M|X M ∣ X has ground set X X X and independent sets { I ∈ I : I ⊆ X } \{I \in\mathcal{I}: I \subseteq X\} { I ∈ I : I ⊆ X } . Deletion is restriction to the remaining elements: M ∖ e = M ∣ ( E ∖ { e } ) M \setminus e = M|(E \setminus\{e\}) M ∖ e = M ∣ ( E ∖ { e }) . Contraction by e e e , denoted M / e M/e M / e , has rank function
rank M / e ( X ) = rank M ( X ∪ { e } ) − rank M ( { e } ) ( X ⊆ E ∖ { e } ) . \operatorname{rank}_{M/e}(X) = \operatorname{rank}_{M}(X \cup\{e\}) - \operatorname{rank}_{M}(\{e\}) \qquad(X \subseteq E \setminus\{e\}). rank M / e ( X ) = rank M ( X ∪ { e }) − rank M ({ e }) ( X ⊆ E ∖ { e }) .
For X ⊆ B ⊆ E X \subseteq B \subseteq E X ⊆ B ⊆ E , closure in the restriction satisfies
cl M ∣ B ( X ) = B ∩ cl M ( X ) . \operatorname{cl}_{M|B}(X) = B \cap\operatorname{cl}_{M}(X). cl M ∣ B ( X ) = B ∩ cl M ( X ) .
Indeed, restriction preserves the ranks of all subsets of B B B , so the defining rank test for closure is the same for each element of B B B . The dual matroid M ∗ M^* M ∗ has ground set E E E and has as its bases the complements of the bases of M M M . The uniform matroid U r , E U_{r,E} U r , E , where 0 ≤ r ≤ ∣ E ∣ 0 \le r \le|E| 0 ≤ r ≤ ∣ E ∣ , has precisely the subsets of size at most r r r as its independent sets. When only the ground-set size matters, we write U r , n U_{r,n} U r , n .
Failure models and optimization problems. In the safe/vulnerable model, the input partitions E = S ∪ ˙ V E = S \mathbin{\dot\cup} V E = S ∪ ˙ V into safe and vulnerable elements and specifies a failure budget k ≥ 0 k \ge0 k ≥ 0 . A selection B ⊆ E B \subseteq E B ⊆ E is k k k -fault tolerant if
rank M ( B ∖ F ) = r for every F ⊆ B ∩ V with ∣ F ∣ ≤ k . (1) \operatorname{rank}_{M}(B \setminus F) = r \qquad\text{for every } F \subseteq B \cap V \text{ with } |F| \le k. \tag*{(1)} rank M ( B ∖ F ) = r for every F ⊆ B ∩ V with ∣ F ∣ ≤ k . (1)
The choice F = ∅ F = \varnothing F = ∅ includes the requirement that B B B itself spans. Weighted Nonuniform Fault-Tolerant Basis asks for a minimum-cost such set, or a report of infeasibility. Ordinary Weighted Fault-Tolerant Basis is the special case S = ∅ S = \varnothing S = ∅ , in which every selected element may fail. The explicit-scenario model, defined in § 5 , instead specifies a list of admissible failures. The corresponding unweighted size-budget decision problems ask whether a feasible set of size at most a given integer β \beta β exists. Here β \beta β is an input budget. We use b b b for a structural upper bound on the size of some optimum, defined locally for each algorithm: b = ( k + 1 ) r b = (k+1)r b = ( k + 1 ) r in the failure-budget model and b = m r b = mr b = m r in the algorithm for m ≥ 1 m \ge1 m ≥ 1 listed scenarios.
Boundary cases. If r = 0 r = 0 r = 0 , the empty set is feasible and optimal in every model. For the failure-budget models, k = 0 k = 0 k = 0 reduces to finding a minimum-cost basis by weighted matroid greedy. The same algorithm handles the explicit-scenario model when m = 0 m=0 m = 0 . We may replace k k k by min { k , ∣ V ∣ } \min\{k, |V|\} min { k , ∣ V ∣ } without changing feasibility. In the ordinary model, positive rank and k ≥ n k \ge n k ≥ n imply infeasibility, since all selected elements may be deleted. Unless stated otherwise, exponential parameter estimates for failure-budget algorithms concern r , k ≥ 1 r,k \ge1 r , k ≥ 1 ; polynomial boundary cases are treated separately. Loops may be deleted: removing selected loops preserves every survivor rank and cannot increase cost.
Cocircuits as failure obstructions. A set spans M M M exactly when it intersects every cocircuit. Indeed, a nonspanning set is contained in a hyperplane and therefore misses its complementary cocircuit; conversely, a set missing a cocircuit is contained in the complementary hyperplane. For rank zero, the condition is vacuous and every set spans. This gives the following characterization.
Proposition 1. Let M M M be a rank-r r r matroid on E = S ∪ ˙ V E = S \mathbin{\dot\cup} V E = S ∪ ˙ V , let k ≥ 0 k \ge0 k ≥ 0 and let B ⊆ E B \subseteq E B ⊆ E . Then B B B is k k k -fault tolerant in the safe/vulnerable model if and only if every cocircuit C ∗ C^* C ∗ of M M M satisfies
B ∩ S ∩ C ∗ ≠ ∅ or ∣ B ∩ V ∩ C ∗ ∣ ≥ k + 1. B \cap S \cap C^* \ne\varnothing\quad\text{or}\quad|B \cap V \cap C^*| \ge k+1. B ∩ S ∩ C ∗ = ∅ or ∣ B ∩ V ∩ C ∗ ∣ ≥ k + 1. In particular, in the ordinary model this condition is ∣ B ∩ C ∗ ∣ ≥ k + 1 |B \cap C^*| \ge k+1 ∣ B ∩ C ∗ ∣ ≥ k + 1 for every cocircuit C ∗ C^* C ∗ .
Proof. If a cocircuit contains no selected safe element and at most k k k selected vulnerable elements, deleting those vulnerable elements leaves a set disjoint from that cocircuit, which does not span. Conversely, under the displayed condition, every allowed failure leaves at least one selected element in each cocircuit, so its survivors span. This also includes the no-failure constraint. □ \square □
Linear representations and duality. A linear representation over a field F \mathbb{F} F assigns a column a e a_e a e to each e ∈ E e \in E e ∈ E , with a set independent precisely when its columns are linearly independent. Retaining r r r independent original rows gives an r × n r \times n r × n representation of the same matroid. We use this form before applying exterior products or determinant certificates. In a linear representation, parallel nonloop elements have columns that are nonzero scalar multiples of one another. The following characterization relates fault tolerance to independence in the dual. It provides an alternative interpretation; the algorithms below do not require it.
Proposition 2. Let M M M be a rank-r r r linear matroid over F \mathbb{F} F , let B ⊆ E B \subseteq E B ⊆ E span M M M and let A B A_B A B be an r × ∣ B ∣ r \times|B| r × ∣ B ∣ representation of M ∣ B M|B M ∣ B of row rank r r r . Let H B H_B H B have as its rows a basis of the orthogonal complement of the row space of A B A_B A B in F B \mathbb{F}^{B} F B . Thus H B H_B H B has ∣ B ∣ − r |B|-r ∣ B ∣ − r rows and ∣ B ∣ |B| ∣ B ∣ columns. For F ⊆ B F \subseteq B F ⊆ B , let ( H B ) F (H_B)_F ( H B ) F denote its columns indexed by F F F . Then
rank M ( B ∖ F ) < r ⟺ ( H B ) F has linearly dependent columns . \operatorname{rank}_M(B \setminus F) < r \quad\Longleftrightarrow\quad(H_B)_F\text{ has linearly dependent columns}. rank M ( B ∖ F ) < r ⟺ ( H B ) F has linearly dependent columns . Consequently, in the ordinary model B B B is k k k -fault tolerant exactly when every set of at most k k k columns of H B H_B H B is independent. For k = 2 k=2 k = 2 , this is equivalent to simplicity of ( M ∣ B ) ∗ (M|B)^* ( M ∣ B ) ∗ . In the safe/vulnerable model, only sets F ⊆ B ∩ V F \subseteq B \cap V F ⊆ B ∩ V of size at most k k k need to be tested.
Proof. Deleting F F F lowers rank exactly when a nonzero linear combination of the rows of A B A_B A B vanishes outside F F F . Since H B H_B H B is the row space of A B A_B A B , this is equivalent to a nonzero vector supported in F F F lying in ker H B \ker H_B ker H B , or a linear dependence among the columns of ( H B ) F (H_B)_F ( H B ) F . The matrix H B H_B H B represents ( M ∣ B ) ∗ (M\mid B)^* ( M ∣ B ) ∗ , so independence of all column sets of size at most two is exactly simplicity of that dual. □ \square □
Determinants and formal polynomial identities. For matrices U ∈ F a × m U \in\mathbb{F}^{a \times m} U ∈ F a × m and W ∈ F m × a W \in\mathbb{F}^{m \times a} W ∈ F m × a , where 0 ≤ a ≤ m 0 \leq a \leq m 0 ≤ a ≤ m , the Cauchy–Binet identity is
det ( U W ) = ∑ L ⊆ [ m ] ∣ L ∣ = a det ( U [ : , L ] ) det ( W [ L , : ] ) . (2) \det(UW) = \sum_{\substack{L \subseteq[m] \\ |L|=a}} \det(U_{[:,L]})\det(W_{[L,:]}). \tag*{(2)} det ( U W ) = L ⊆ [ m ] ∣ L ∣ = a ∑ det ( U [ : , L ] ) det ( W [ L , : ] ) . (2)
Here U [ : , L ] U_{[:,L]} U [ : , L ] consists of the columns indexed by L L L and W [ L , : ] W_{[L,:]} W [ L , : ] consists of the corresponding rows, both in increasing index order. If a > m a > m a > m , the product has rank below a a a and its determinant is zero, matching the empty sum. For indeterminates t 1 , … , t a t_1,\ldots,t_a t 1 , … , t a , the Vandermonde matrix V = ( t i j − 1 ) i , j = 1 a V = (t_i^{j-1})_{i,j=1}^{a} V = ( t i j − 1 ) i , j = 1 a satisfies
det V = ∏ 1 ≤ i < j ≤ a ( t j − t i ) . \det V = \prod_{1 \leq i < j \leq a}(t_j-t_i). det V = 1 ≤ i < j ≤ a ∏ ( t j − t i ) .
Empty products and determinants of 0 × 0 0 \times0 0 × 0 matrices equal 1. These identities hold over polynomial rings as well as over fields. A polynomial ring over a field is an integral domain, so a product of polynomials is nonzero exactly when every factor is nonzero. Formal nonvanishing is distinguished from nonvanishing after numerical evaluation, particularly over finite fields.
Computational conventions. An independence oracle answers whether a queried set is independent. Scanning a set X X X and retaining an element whenever it preserves independence constructs a basis of X X X , so a rank query uses at most ∣ X ∣ |X| ∣ X ∣ independence queries. Weighted matroid greedy scans elements in nondecreasing cost order and retains those preserving independence; it returns a minimum-cost basis. Ties are broken consistently. Oracle bounds count independence queries and elementary arithmetic and comparison operations. With explicit representations, we state field-operation bounds separately and use exact field arithmetic. Bounds written with a factor n O ( 1 ) n^{O(1)} n O ( 1 ) use this operation-count convention; reading the encoded input and reducing an input matrix to r r r independent rows contribute additional polynomial preprocessing. Bit bounds also account for the encoding lengths of costs and field elements, and are stated in terms of L i n L_{\mathrm{in}} L in , not only the number n n n of ground elements. Weight additions and comparisons have polynomial bit cost in the encoded weights and the number of selected elements. For standard finite-field encodings, field operations have polynomial bit complexity in the field encoding length. Over Q \mathbb{Q} Q , coefficient growth is analyzed in the proof of the relevant algorithm. We make no bit-complexity claim for an unspecified black-box field.
A parameterized problem is fixed-parameter tractable (FPT) with parameter t t t if it admits a running time f ( t ) L i n O ( 1 ) f(t)L_{\mathrm{in}}^{O(1)} f ( t ) L in O ( 1 ) , where f f f is computable and L i n L_{\mathrm{in}} L in is the input encoding length. We use the standard notions of W[1 ] -hardness and W[2 ] -hardness under parameterized reductions. Throughout, an optimum means a minimum-cost feasible selection; algorithms report infeasibility when no feasible selection exists.
A weighted FPT algorithm for oracle matroids
We prove Theorem 1 by constructing a bounded set of original elements that contains a minimum-cost feasible solution. Throughout this section, M M M is a rank-r r r matroid given by an independence oracle, E = S ∪ ˙ V E = S \mathbin{\dot\cup} V E = S ∪ ˙ V is its partition into safe and vulnerable elements, and w w w assigns nonnegative costs. A feasible selection must span after every deletion of at most k k k of its vulnerable elements. The safety type of an element records whether it is safe or vulnerable.
The argument proceeds in five steps. First, some optimum has at most b = ( k + 1 ) r b = (k + 1)r b = ( k + 1 ) r elements. Second, we identify what is needed to replace one selected element: its replacement must have the same safety type and avoid every hyperplane spanned by a deficient survivor set. Third, we bound the number of these hyperplanes using small cocircuits through the removed element. Fourth, a weight-ordered construction retains enough inexpensive elements to avoid any such family of hyperplanes. Finally, we apply this construction to each safety type and search the resulting core. The exchanges establish that the core contains an optimum; the algorithm constructs the core without knowing that optimum.
For r = 0 r = 0 r = 0 , the empty set is optimal, and for k = 0 k = 0 k = 0 , weighted matroid greedy finds an optimum. We therefore assume r , k ≥ 1 r, k \ge1 r , k ≥ 1 in the algorithmic construction. Loops may be deleted because they contribute nothing to any survivor rank and have nonnegative costs. The auxiliary lemmas below state their own assumptions, including the boundary cases in which they apply.
Small optimal solutions
We begin by bounding the number of elements needed in an optimal solution. The following sparsification lemma preserves the entire closure after every failure of size at most k k k . We use a disjoint-layer construction, as in the dimension-reduction procedure for Matrix Rigidity [10 ] and the small-solution bound for Fault-Tolerant Basis [3 full version, Proposition 3] .
Lemma 1. Let M = ( E , I ) M = (E, \mathcal{I}) M = ( E , I ) be a matroid of rank r r r , let B ⊆ E B \subseteq E B ⊆ E , and let k ≥ 0 k \ge0 k ≥ 0 be an integer. There exists a set C ⊆ B C \subseteq B C ⊆ B with ∣ C ∣ ≤ ( k + 1 ) r |C| \le(k + 1)r ∣ C ∣ ≤ ( k + 1 ) r such that
cl M ( C ∖ F ) = cl M ( B ∖ F ) for every F ⊆ B with ∣ F ∣ ≤ k . \operatorname{cl}_M(C \setminus F) = \operatorname{cl}_M(B \setminus F) \qquad\text{for every } F \subseteq B \text{ with } |F| \le k. cl M ( C ∖ F ) = cl M ( B ∖ F ) for every F ⊆ B with ∣ F ∣ ≤ k . Consequently, every feasible instance of Weighted Nonuniform Fault-Tolerant Basis has a minimum-cost feasible solution of size at most b = ( k + 1 ) r b = (k+1)r b = ( k + 1 ) r . The same conclusion holds when the allowed failures form a prescribed family of subsets of E E E , each of size at most k k k .
Proof. For each j ∈ { 0 , … , k } j \in\{0,\ldots,k\} j ∈ { 0 , … , k } , choose a maximal independent subset I j I_j I j of B ∖ ⋃ h < j I h B \setminus\bigcup_{h<j} I_h B ∖ ⋃ h < j I h , and put C = ⋃ j = 0 k I j C = \bigcup_{j=0}^{k} I_j C = ⋃ j = 0 k I j . The sets I 0 , … , I k I_0,\ldots,I_k I 0 , … , I k are pairwise disjoint and each has at most r r r elements, so ∣ C ∣ ≤ ( k + 1 ) r |C| \le(k+1)r ∣ C ∣ ≤ ( k + 1 ) r .
Every element e ∈ B ∖ C e \in B \setminus C e ∈ B ∖ C was available when each I j I_j I j was chosen. By maximality of I j I_j I j , the set I j ∪ { e } I_j \cup\{e\} I j ∪ { e } is dependent, and hence e ∈ cl M ( I j ) e \in\operatorname{cl}_M(I_j) e ∈ cl M ( I j ) . Thus every element of B ∖ C B \setminus C B ∖ C is spanned by each layer.
Fix F ⊆ B F \subseteq B F ⊆ B with ∣ F ∣ ≤ k |F| \le k ∣ F ∣ ≤ k . Since the k + 1 k+1 k + 1 layers are pairwise disjoint, at least one layer I j I_j I j is disjoint from F F F . Therefore I j ⊆ C ∖ F I_j \subseteq C \setminus F I j ⊆ C ∖ F , and
( B ∖ C ) ∖ F ⊆ cl M ( I j ) ⊆ cl M ( C ∖ F ) . (B \setminus C) \setminus F \subseteq\operatorname{cl}_M(I_j) \subseteq\operatorname{cl}_M(C \setminus F). ( B ∖ C ) ∖ F ⊆ cl M ( I j ) ⊆ cl M ( C ∖ F ) .
Every element of B ∖ F B \setminus F B ∖ F either belongs to C ∖ F C \setminus F C ∖ F or to ( B ∖ C ) ∖ F (B \setminus C) \setminus F ( B ∖ C ) ∖ F . It follows that B ∖ F ⊆ cl M ( C ∖ F ) B \setminus F \subseteq\operatorname{cl}_M(C \setminus F) B ∖ F ⊆ cl M ( C ∖ F ) . Taking closures and using idempotence gives cl M ( B ∖ F ) ⊆ cl M ( C ∖ F ) \operatorname{cl}_M(B \setminus F) \subseteq\operatorname{cl}_M(C \setminus F) cl M ( B ∖ F ) ⊆ cl M ( C ∖ F ) . The reverse inclusion follows from C ∖ F ⊆ B ∖ F C \setminus F \subseteq B \setminus F C ∖ F ⊆ B ∖ F , proving the equality.
Now let B B B be a minimum-cost feasible solution and apply the construction above. Every failure F ⊆ C ∩ V F \subseteq C \cap V F ⊆ C ∩ V with ∣ F ∣ ≤ k |F| \le k ∣ F ∣ ≤ k is also an allowed failure for B B B . Feasibility of B B B and the closure equality imply cl M ( C ∖ F ) = cl M ( B ∖ F ) = E \operatorname{cl}_M(C \setminus F) = \operatorname{cl}_M(B \setminus F) = E cl M ( C ∖ F ) = cl M ( B ∖ F ) = E . Thus C C C is feasible. Since C ⊆ B C \subseteq B C ⊆ B and costs are nonnegative, w ( C ) ≤ w ( B ) w(C) \le w(B) w ( C ) ≤ w ( B ) , so C C C is also optimal.
Finally, suppose the allowed failures form a prescribed family of subsets of E E E , each of size at most k k k . For any such failure F F F , apply the closure equality to F ∩ B F \cap B F ∩ B . Since C ⊆ B C \subseteq B C ⊆ B , we have C ∖ ( F ∩ B ) = C ∖ F C \setminus(F \cap B) = C \setminus F C ∖ ( F ∩ B ) = C ∖ F and B ∖ ( F ∩ B ) = B ∖ F B \setminus(F \cap B) = B \setminus F B ∖ ( F ∩ B ) = B ∖ F . Hence feasibility is preserved under every prescribed failure. The same cost argument proves the final assertion. □ \square □
Remark 1. The size bound is tight even for ordinary unweighted fault tolerance. For example, take the direct sum of r r r rank-one uniform matroids, each with exactly k + 1 k+1 k + 1 elements, and make every element vulnerable. A feasible set must select all k + 1 k+1 k + 1 elements of every summand. Otherwise, an allowed failure can delete all selected elements in that summand. Thus its unique feasible set has size ( k + 1 ) r (k+1)r ( k + 1 ) r .
Replacing a selected element
The size bound does not yet give an FPT algorithm: searching all subsets of E E E of size at most b b b takes n O ( b ) n^{O(b)} n O ( b ) time. We seek a bounded set W ⊆ E W \subseteq E W ⊆ E into which an optimum can be moved by exchanges. To determine what W W W must preserve, we first study a single exchange while fixing the other selected elements.
Definition 1. Fix Y ⊆ E Y \subseteq E Y ⊆ E . Two elements x , y ∈ E ∖ Y x,y \in E \setminus Y x , y ∈ E ∖ Y are equivalent relative to Y Y Y if they have the same safety type—either both belong to S S S or both belong to V V V —and
rank M ( ( Y ∖ F ) ∪ { x } ) = rank M ( ( Y ∖ F ) ∪ { y } ) \operatorname{rank}_M((Y \setminus F) \cup\{x\}) = \operatorname{rank}_M((Y \setminus F) \cup\{y\}) rank M (( Y ∖ F ) ∪ { x }) = rank M (( Y ∖ F ) ∪ { y }) for every F ⊆ Y ∩ V F \subseteq Y \cap V F ⊆ Y ∩ V with ∣ F ∣ ≤ k |F| \le k ∣ F ∣ ≤ k .
For fixed Y Y Y , this is an equivalence relation: it compares the safety type and the ranks obtained after each allowed failure within Y Y Y . Costs are not part of the relation. In an exchange, we will additionally require w ( y ) ≤ w ( x ) w(y) \leq w(x) w ( y ) ≤ w ( x ) .
Now fix a feasible set B B B , choose x ∈ B x \in B x ∈ B , and put Y = B ∖ { x } Y = B \setminus\{x\} Y = B ∖ { x } . Define
H ( B , x ) = { cl M ( Y ∖ F ) : F ⊆ Y ∩ V , ∣ F ∣ ≤ k , rank M ( Y ∖ F ) < r } . \mathcal{H}(B,x)=\left\{\operatorname{cl}_{M}(Y\setminus F): F\subseteq Y\cap V,\ |F|\leq k,\ \operatorname{rank}_{M}(Y\setminus F)<r\right\}. H ( B , x ) = { cl M ( Y ∖ F ) : F ⊆ Y ∩ V , ∣ F ∣ ≤ k , rank M ( Y ∖ F ) < r } .
We regard this as a set of distinct flats, so different failures may contribute the same member. Feasibility of B B B implies that adding x x x to each survivor set restores rank r r r . Thus every member of H ( B , x ) \mathcal{H}(B,x) H ( B , x ) is a hyperplane avoiding x x x .
Lemma 2. Let B B B be feasible, let x ∈ B x \in B x ∈ B , and put Y = B ∖ { x } Y = B \setminus\{x\} Y = B ∖ { x } . An element y ∈ E ∖ B y \in E \setminus B y ∈ E ∖ B of the same safety type as x x x is equivalent to x x x relative to Y Y Y if and only if it avoids every member of H ( B , x ) \mathcal{H}(B,x) H ( B , x ) . In this case, B ′ = Y ∪ { y } B' = Y \cup\{y\} B ′ = Y ∪ { y } is feasible. If also w ( y ) ≤ w ( x ) w(y) \leq w(x) w ( y ) ≤ w ( x ) , then w ( B ′ ) ≤ w ( B ) w(B') \leq w(B) w ( B ′ ) ≤ w ( B ) .
Proof. Fix F ⊆ Y ∩ V F \subseteq Y \cap V F ⊆ Y ∩ V with ∣ F ∣ ≤ k |F| \leq k ∣ F ∣ ≤ k . Since B B B is feasible, rank M ( ( Y ∖ F ) ∪ { x } ) = r \operatorname{rank}_{M}((Y \setminus F)\cup\{x\})=r rank M (( Y ∖ F ) ∪ { x }) = r . Deleting one element lowers rank by at most one, so Y ∖ F Y \setminus F Y ∖ F has rank either r r r or r − 1 r-1 r − 1 . If it has rank r r r , adding either x x x or y y y leaves the rank unchanged. Otherwise, H F = cl M ( Y ∖ F ) H_F=\operatorname{cl}_{M}(Y\setminus F) H F = cl M ( Y ∖ F ) is a hyperplane avoiding x x x , and adding y y y restores rank r r r exactly when y ∉ H F y\notin H_F y ∈ / H F . Applying this observation to every allowed F F F proves the equivalence.
To verify feasibility of B ′ B' B ′ , let F ′ ⊆ B ′ ∩ V F' \subseteq B' \cap V F ′ ⊆ B ′ ∩ V have size at most k k k . If y ∉ F ′ y \notin F' y ∈ / F ′ , then F ′ ⊆ Y ∩ V F' \subseteq Y \cap V F ′ ⊆ Y ∩ V . Equivalence gives
rank M ( B ′ ∖ F ′ ) = rank M ( ( Y ∖ F ′ ) ∪ { y } ) = rank M ( ( Y ∖ F ′ ) ∪ { x } ) = r . \operatorname{rank}_{M}(B'\setminus F')=\operatorname{rank}_{M}((Y\setminus F')\cup\{y\})=\operatorname{rank}_{M}((Y\setminus F')\cup\{x\})=r. rank M ( B ′ ∖ F ′ ) = rank M (( Y ∖ F ′ ) ∪ { y }) = rank M (( Y ∖ F ′ ) ∪ { x }) = r .
If y ∈ F ′ y \in F' y ∈ F ′ , then y y y is vulnerable, and hence so is x x x . The set
F = ( F ′ ∖ { y } ) ∪ { x } F=(F'\setminus\{y\})\cup\{x\} F = ( F ′ ∖ { y }) ∪ { x }
is an allowed failure for B B B , with ∣ F ∣ = ∣ F ′ ∣ |F|=|F'| ∣ F ∣ = ∣ F ′ ∣ and B ′ ∖ F ′ = B ∖ F B'\setminus F'=B\setminus F B ′ ∖ F ′ = B ∖ F . Feasibility of B B B again gives rank r r r . Finally, w ( B ′ ) = w ( B ) − w ( x ) + w ( y ) ≤ w ( B ) w(B')=w(B)-w(x)+w(y)\leq w(B) w ( B ′ ) = w ( B ) − w ( x ) + w ( y ) ≤ w ( B ) whenever w ( y ) ≤ w ( x ) w(y)\leq w(x) w ( y ) ≤ w ( x ) .
The same replacement must avoid all members of H ( B , x ) \mathcal{H}(B,x) H ( B , x ) . A separate replacement for each failure would not yield one feasible selected set. We next bound the size of this family, and then construct representatives that work for every family of that size.
Bounding the replacement obstructions
Each deficient survivor hyperplane gives a small cocircuit through x x x in the restriction M ∣ B M|B M ∣ B . We first bound such cocircuits in an arbitrary matroid, and then verify that this also bounds the distinct ambient hyperplanes in H ( B , x ) \mathcal{H}(B,x) H ( B , x ) .
Lemma 3. Let M M M be a matroid of rank r ≥ 1 r \ge1 r ≥ 1 , let x ∈ E ( M ) x \in E(M) x ∈ E ( M ) , and let k ≥ 0 k \ge0 k ≥ 0 be an integer. Then the number of cocircuits C ∗ C^* C ∗ satisfying
x ∈ C ∗ , ∣ C ∗ ∣ ≤ k + 1 x \in C^*, \qquad|C^*| \le k+1 x ∈ C ∗ , ∣ C ∗ ∣ ≤ k + 1 is at most
( r + k − 1 k ) . \binom{r+k-1}{k}. ( k r + k − 1 ) .
Proof. It is equivalent to count the hyperplanes H H H avoiding x x x whose complements have size at most k + 1 k+1 k + 1 . We prove the bound by induction on r + k r+k r + k . If x x x is a loop, the count is zero. So now we assume that x x x is not a loop. For r = 1 r=1 r = 1 there is a unique hyperplane, namely the set of loops. For k = 0 k=0 k = 0 , the only possible cocircuit is { x } \{x\} { x } . These two cases also satisfy the bound.
Assume now that r ≥ 2 r \ge2 r ≥ 2 and k ≥ 1 k \ge1 k ≥ 1 . If x x x is a coloop, the only cocircuit containing it is { x } \{x\} { x } , so the bound holds. Otherwise, x x x is neither a loop nor a coloop and belongs to a circuit C C C of size at least two. Choose y ∈ C ∖ { x } y \in C \setminus\{x\} y ∈ C ∖ { x } . Since y y y belongs to this circuit, it is neither a loop nor a coloop. We separate the counted hyperplanes according to whether they contain y y y .
If y ∈ H y \in H y ∈ H , then H ∖ { y } H \setminus\{y\} H ∖ { y } is a flat of M / y M/y M / y . Since y y y is a nonloop, the flat has rank r − 2 r-2 r − 2 and M / y M/y M / y has rank r − 1 r-1 r − 1 . Thus it is a hyperplane with complement E ( M ) ∖ H E(M) \setminus H E ( M ) ∖ H , which contains x x x and has size at most k + 1 k+1 k + 1 . Adjoining y y y recovers H H H , so the correspondence is injective. Induction bounds this case by
( r + k − 2 k ) . \binom{r+k-2}{k}. ( k r + k − 2 ) .
If y ∉ H y \notin H y ∈ / H , then H H H remains a flat of rank r − 1 r-1 r − 1 in M ∖ y M \setminus y M ∖ y . Since y y y is not a coloop, this deletion has rank r r r , and H H H is still a hyperplane. Its complement is ( E ( M ) ∖ H ) ∖ { y } (E(M) \setminus H) \setminus\{y\} ( E ( M ) ∖ H ) ∖ { y } , which contains x x x and has size at most k k k . Induction bounds the number of these hyperplanes by
( r − 1 + k − 1 k − 1 ) = ( r + k − 2 k − 1 ) . \binom{r-1+k-1}{k-1} = \binom{r+k-2}{k-1}. ( k − 1 r − 1 + k − 1 ) = ( k − 1 r + k − 2 ) .
Summing the two bounds and applying Pascal’s identity completes the induction.
The bound is attained by U r , r + k U_{r,r+k} U r , r + k . Every cocircuit of this uniform matroid has size k + 1 k+1 k + 1 , and exactly ( r + k − 1 k ) \binom{r+k-1}{k} ( k r + k − 1 ) of them contain a prescribed element. □ \square □
Lemma 4. For every feasible set B B B and every x ∈ B x \in B x ∈ B ,
∣ H ( B , x ) ∣ ≤ ( r + k − 1 k ) . |\mathcal{H}(B,x)| \le\binom{r+k-1}{k}. ∣ H ( B , x ) ∣ ≤ ( k r + k − 1 ) .
Proof. Put Y = B ∖ { x } Y = B \setminus\{x\} Y = B ∖ { x } , and consider a failure F ⊆ Y ∩ V F \subseteq Y \cap V F ⊆ Y ∩ V with ∣ F ∣ ≤ k |F| \le k ∣ F ∣ ≤ k that contributes H F = cl M ( Y ∖ F ) H_F = \operatorname{cl}_{M}(Y \setminus F) H F = cl M ( Y ∖ F ) to H ( B , x ) \mathcal{H}(B,x) H ( B , x ) . As observed above, rank M ( Y ∖ F ) = r − 1 \operatorname{rank}_{M}(Y \setminus F) = r-1 rank M ( Y ∖ F ) = r − 1 and x ∉ H F x \notin H_F x ∈ / H F .
The restriction M ∣ B M|B M ∣ B has rank r r r , since B B B is feasible. The set B ∩ H F B \cap H_F B ∩ H F is a flat of this restriction. It contains Y ∖ F Y \setminus F Y ∖ F and is contained in H F H_F H F , so its rank is r − 1 r-1 r − 1 . Consequently,
C F = B ∖ H F C_F = B \setminus H_F C F = B ∖ H F
is a cocircuit of M ∣ B M|B M ∣ B containing x x x . Every element of Y ∖ F Y \setminus F Y ∖ F belongs to H F H_F H F , so C F ⊆ F ∪ { x } C_F \subseteq F \cup\{x\} C F ⊆ F ∪ { x } and ∣ C F ∣ ≤ k + 1 |C_F| \le k+1 ∣ C F ∣ ≤ k + 1 .
Distinct ambient hyperplanes yield distinct cocircuits. Indeed,
cl M ( B ∩ H F ) = H F , \operatorname{cl}_{M}(B \cap H_F) = H_F, cl M ( B ∩ H F ) = H F ,
because B ∩ H F B \cap H_F B ∩ H F contains Y ∖ F Y \setminus F Y ∖ F , whose closure is H F H_F H F , and is itself contained in the flat H F H_F H F . Equal cocircuits give equal complements within B B B , hence equal closures in M M M , and therefore equal hyperplanes. Lemma 3 applied to M ∣ B M|B M ∣ B now proves the bound. □ \square □
We therefore need representatives that avoid any family of at most t = ( r + k − 1 k ) t = \binom{r+k-1}{k} t = ( k r + k − 1 ) hyperplanes avoiding a discarded element. We also need a reserve of b b b inexpensive candidates: at most b − 1 b-1 b − 1 of them may already belong to the selection Y Y Y . The next lemma provides exactly this guarantee without knowing B B B , x x x , or its family of deficient hyperplanes in advance.
Weighted flat-avoidance representatives
We now construct representatives for the requirement identified above. The lemma is stated for arbitrary positive integers b , t b,t b , t , so it can also be used for the explicit-scenario model later. It processes a set A A A in nondecreasing cost order and limits the number of retained elements in each flat according to its rank.
The lemma selects a small set W ⊆ A W \subseteq A W ⊆ A of representatives. For every discarded element x ∈ A ∖ W x \in A \setminus W x ∈ A ∖ W and every collection of at most t t t hyperplanes not containing x x x , at least b b b elements of W W W have cost at most w ( x ) w(x) w ( x ) and lie outside all these hyperplanes. For example, consider a rank-two matroid represented by nonzero vectors in R 2 \mathbb{R}^2 R 2 , and let t = 2 t = 2 t = 2 and b = 3 b = 3 b = 3 . Choose any two lines through the origin, neither containing the discarded vector x x x . The lemma guarantees that W W W contains at least three vectors outside both lines, each of cost at most w ( x ) w(x) w ( x ) . Even if two of these vectors are already selected, a third remains available. Like x x x , this vector can extend a rank-one set lying on either line to a set of rank two.
Lemma 5. Let M M M be a loopless matroid of rank r ≥ 1 r \ge1 r ≥ 1 , let A ⊆ E ( M ) A \subseteq E(M) A ⊆ E ( M ) , let w : A → R ≥ 0 w : A \to\mathbb{R}_{\ge0} w : A → R ≥ 0 , and let b , t ≥ 1 b,t \ge1 b , t ≥ 1 be integers. Define L 0 = 0 L_0 = 0 L 0 = 0 and
L h = t L h − 1 + b = b ∑ j = 0 h − 1 t j for 1 ≤ h ≤ r . L_h = tL_{h-1} + b = b \sum_{j=0}^{h-1} t^j \qquad\text{for } 1 \le h \le r. L h = t L h − 1 + b = b j = 0 ∑ h − 1 t j for 1 ≤ h ≤ r . There is an algorithm that computes a set W ⊆ A W \subseteq A W ⊆ A of size at most L r L_r L r with the following property. For every x ∈ A ∖ W x \in A \setminus W x ∈ A ∖ W , every collection of at most t t t hyperplanes H 1 , … , H ℓ H_1,\ldots,H_\ell H 1 , … , H ℓ with x ∉ H i x \notin H_i x ∈ / H i for each i i i , and every set D ⊆ E ( M ) D \subseteq E(M) D ⊆ E ( M ) of size at most b − 1 b-1 b − 1 , there exists
y ∈ W ∖ ( D ∪ ⋃ i = 1 ℓ H i ) such that w ( y ) ≤ w ( x ) . y \in W \setminus\left(D \cup\bigcup_{i=1}^{\ell} H_i\right) \qquad\text{such that} \qquad w(y) \le w(x). y ∈ W ∖ ( D ∪ i = 1 ⋃ ℓ H i ) such that w ( y ) ≤ w ( x ) . The algorithm uses O ( n r ( L r + 1 ) r + 1 ) O(nr(L_r+1)^{r+1}) O ( n r ( L r + 1 ) r + 1 ) independence queries, in addition to sorting the elements of A A A by weight, where n = ∣ E ( M ) ∣ n = |E(M)| n = ∣ E ( M ) ∣ .
Proof. First we process the elements of A A A in nondecreasing order of cost, breaking ties arbitrarily. Initially we set W = ∅ W = \varnothing W = ∅ . Throughout the process we maintain
∣ W ∩ Q ∣ ≤ L rank ( Q ) for every flat Q of M . (3) |W \cap Q| \le L_{\operatorname{rank}(Q)} \qquad\text{for every flat } Q \text{ of } M. \tag*{(3)} ∣ W ∩ Q ∣ ≤ L rank ( Q ) for every flat Q of M . (3)
We call a flat Q Q Q saturated if ∣ W ∩ Q ∣ = L rank ( Q ) |W \cap Q| = L_{\operatorname{rank}(Q)} ∣ W ∩ Q ∣ = L rank ( Q ) .
Now when an element x ∈ A x \in A x ∈ A is considered, we discard x x x if there exists a saturated flat Q Q Q containing x x x . Otherwise, we add x x x to W W W . We verify that (3) is preserved. An insertion of x x x can change the quantity ∣ W ∩ Q ∣ |W \cap Q| ∣ W ∩ Q ∣ only for flats Q Q Q containing x x x . Before the insertion, every such flat satisfies ∣ W ∩ Q ∣ < L rank ( Q ) |W \cap Q| < L_{\operatorname{rank}(Q)} ∣ W ∩ Q ∣ < L rank ( Q ) , for otherwise, it would be saturated and x x x would have been discarded. Since the quantities involved are integral, after inserting x x x we still have ∣ W ∩ Q ∣ ≤ L rank ( Q ) |W \cap Q| \le L_{\operatorname{rank}(Q)} ∣ W ∩ Q ∣ ≤ L rank ( Q ) . Thus the invariant is maintained.
Observe that applying (3) to the flat E ( M ) E(M) E ( M ) , which has rank r r r , gives ∣ W ∣ ≤ L r |W| \le L_r ∣ W ∣ ≤ L r , throughout the algorithm.
We next show that the above rule can be implemented without enumerating all flats of M M M .
First observe that the thresholds are strictly increasing: L h = t L h − 1 + b > L h − 1 L_h = tL_{h-1} + b > L_{h-1} L h = t L h − 1 + b > L h − 1 , and hence L h > L d L_h > L_d L h > L d whenever h > d h > d h > d . Suppose that Q Q Q is a saturated flat of rank h h h . We claim that rank ( W ∩ Q ) = h \operatorname{rank}(W \cap Q) = h rank ( W ∩ Q ) = h . Assume instead that d : = rank ( W ∩ Q ) < h d := \operatorname{rank}(W \cap Q) < h d := rank ( W ∩ Q ) < h , and define P : = cl ( W ∩ Q ) P := \operatorname{cl}(W \cap Q) P := cl ( W ∩ Q ) . Then P P P is a flat of rank d d d . Moreover, since Q Q Q is a flat containing W ∩ Q W \cap Q W ∩ Q , closure minimality gives P = cl ( W ∩ Q ) ⊆ Q P = \operatorname{cl}(W \cap Q) \subseteq Q P = cl ( W ∩ Q ) ⊆ Q . On the other hand, W ∩ Q ⊆ cl ( W ∩ Q ) = P W \cap Q \subseteq\operatorname{cl}(W \cap Q) = P W ∩ Q ⊆ cl ( W ∩ Q ) = P . Combining this with P ⊆ Q P \subseteq Q P ⊆ Q yields W ∩ P = W ∩ Q W \cap P = W \cap Q W ∩ P = W ∩ Q . Indeed, the inclusion P ⊆ Q P \subseteq Q P ⊆ Q gives W ∩ P ⊆ W ∩ Q W \cap P \subseteq W \cap Q W ∩ P ⊆ W ∩ Q , whereas W ∩ Q ⊆ P W \cap Q \subseteq P W ∩ Q ⊆ P gives the reverse inclusion.
Since Q Q Q is saturated, ∣ W ∩ P ∣ = ∣ W ∩ Q ∣ = L h |W \cap P| = |W \cap Q| = L_h ∣ W ∩ P ∣ = ∣ W ∩ Q ∣ = L h . But rank ( P ) = d < h \operatorname{rank}(P) = d < h rank ( P ) = d < h , and therefore L h > L d L_h > L_d L h > L d . Consequently
∣ W ∩ P ∣ = L h > L d = L rank ( P ) , |W \cap P| = L_h > L_d = L_{\operatorname{rank}(P)}, ∣ W ∩ P ∣ = L h > L d = L rank ( P ) ,
contradicting the invariant (3) . Hence rank ( W ∩ Q ) = h \operatorname{rank}(W \cap Q) = h rank ( W ∩ Q ) = h . It follows that W ∩ Q W \cap Q W ∩ Q contains an independent set I I I of size h h h spanning Q Q Q . Thus cl ( I ) = Q \operatorname{cl}(I) = Q cl ( I ) = Q . Therefore every saturated flat has the form cl ( I ) \operatorname{cl}(I) cl ( I ) for some independent set I ⊆ W I \subseteq W I ⊆ W , ∣ I ∣ ≤ r |I| \le r ∣ I ∣ ≤ r .
Accordingly, when processing x x x , enumerate all independent subsets I ⊆ W I \subseteq W I ⊆ W , ∣ I ∣ ≤ r |I| \le r ∣ I ∣ ≤ r . For each such I I I , test whether x ∈ cl ( I ) x \in\operatorname{cl}(I) x ∈ cl ( I ) and determine the quantity ∣ W ∩ cl ( I ) ∣ |W \cap\operatorname{cl}(I)| ∣ W ∩ cl ( I ) ∣ . Discard x x x precisely when some enumerated I I I satisfies
x ∈ cl ( I ) , ∣ W ∩ cl ( I ) ∣ = L ∣ I ∣ . x \in\operatorname{cl}(I), |W \cap\operatorname{cl}(I)| = L_{|I|}. x ∈ cl ( I ) , ∣ W ∩ cl ( I ) ∣ = L ∣ I ∣ .
Every such witness indeed defines a saturated flat, because I I I is independent and hence rank ( cl ( I ) ) = ∣ I ∣ \operatorname{rank}(\operatorname{cl}(I)) = |I| rank ( cl ( I )) = ∣ I ∣ . Conversely, if x x x lies in a saturated flat Q Q Q , the preceding argument produces an independent set I ⊆ W ∩ Q I \subseteq W \cap Q I ⊆ W ∩ Q of size rank ( Q ) \operatorname{rank}(Q) rank ( Q ) with cl ( I ) = Q \operatorname{cl}(I) = Q cl ( I ) = Q , and this I I I is among the enumerated subsets. Hence the finite procedure is exactly equivalent to the abstract saturation rule.
Now for an independent set I I I , membership of an element e e e in cl ( I ) \operatorname{cl}(I) cl ( I ) can be tested by checking whether I ∪ { e } I \cup\{e\} I ∪ { e } is independent: for e ∉ I e \notin I e ∈ / I ,
e ∈ cl ( I ) ⟺ I ∪ { e } is dependent , e \in\operatorname{cl}(I) \quad\Longleftrightarrow\quad I \cup\{e\}\text{ is dependent}, e ∈ cl ( I ) ⟺ I ∪ { e } is dependent ,
while membership is automatic when e ∈ I e \in I e ∈ I .
Since ∣ W ∣ ≤ L r |W| \le L_r ∣ W ∣ ≤ L r , the number of subsets of W W W of size at most r r r is at most
∑ j = 0 r ( ∣ W ∣ j ) ≤ ∑ j = 0 r ( L r j ) . \sum_{j=0}^{r} \binom{|W|}{j} \le\sum_{j=0}^{r} \binom{L_r}{j}. j = 0 ∑ r ( j ∣ W ∣ ) ≤ j = 0 ∑ r ( j L r ) .
Using ( L r j ) ≤ L r j \binom{L_r}{j} \le L_r^j ( j L r ) ≤ L r j , we obtain
∑ j = 0 r ( L r j ) ≤ ∑ j = 0 r L r j ≤ ( L r + 1 ) r . \sum_{j=0}^{r} \binom{L_r}{j} \le\sum_{j=0}^{r} L_r^j \le(L_r+1)^r. j = 0 ∑ r ( j L r ) ≤ j = 0 ∑ r L r j ≤ ( L r + 1 ) r .
Testing whether an enumerated set I I I is independent uses one query. For each independent I I I , testing x ∈ cl ( I ) x \in\operatorname{cl}(I) x ∈ cl ( I ) and determining W ∩ cl ( I ) W \cap\operatorname{cl}(I) W ∩ cl ( I ) uses at most O ( L r + 1 ) O(L_r+1) O ( L r + 1 ) further independence queries. Thus one may in fact implement the rule using O ( n ( L r + 1 ) r + 1 ) O(n(L_r+1)^{r+1}) O ( n ( L r + 1 ) r + 1 ) independence queries. In particular, this is within the stated bound O ( n r ( L r + 1 ) r + 1 ) O(nr(L_r+1)^{r+1}) O ( n r ( L r + 1 ) r + 1 ) .
To prove the replacement guarantee, fix a discarded element x x x , and let Q Q Q be a saturated witness at the moment when x x x is discarded. Write h : = rank ( Q ) h := \operatorname{rank}(Q) h := rank ( Q ) . Let Z : = W ∩ Q Z := W \cap Q Z := W ∩ Q at that moment. Since Q Q Q is saturated, ∣ Z ∣ = L h |Z| = L_h ∣ Z ∣ = L h . All elements of Z Z Z were processed before x x x , and therefore w ( z ) ≤ w ( x ) w(z) \le w(x) w ( z ) ≤ w ( x ) for every z ∈ Z z \in Z z ∈ Z . Since elements are never removed from W W W , all elements of Z Z Z remain in the final set W W W .
Because M M M is loopless and x ∈ Q x \in Q x ∈ Q , we have h ≥ 1 h \ge1 h ≥ 1 . Now let H H H be any hyperplane avoiding x x x . Since x ∈ Q x \in Q x ∈ Q but x ∉ H x \notin H x ∈ / H , we have Q ⊈ H Q \nsubseteq H Q ⊈ H . Therefore Q ∩ H Q \cap H Q ∩ H is a proper flat of Q Q Q , and hence rank ( Q ∩ H ) ≤ h − 1 \operatorname{rank}(Q \cap H) \le h-1 rank ( Q ∩ H ) ≤ h − 1 . Applying the invariant (3) to the flat Q ∩ H Q \cap H Q ∩ H gives
∣ W ∩ ( Q ∩ H ) ∣ ≤ L rank ( Q ∩ H ) ≤ L h − 1 . |W \cap(Q \cap H)| \le L_{\operatorname{rank}(Q \cap H)} \le L_{h-1}. ∣ W ∩ ( Q ∩ H ) ∣ ≤ L rank ( Q ∩ H ) ≤ L h − 1 .
Since Z ⊆ W ∩ Q Z \subseteq W \cap Q Z ⊆ W ∩ Q , it follows that ∣ Z ∩ H ∣ ≤ L h − 1 |Z \cap H| \le L_{h-1} ∣ Z ∩ H ∣ ≤ L h − 1 .
Now let H 1 , … , H ℓ H_1,\ldots,H_\ell H 1 , … , H ℓ be at most t t t hyperplanes avoiding x x x . By the union bound,
∣ Z ∩ ⋃ i = 1 ℓ H i ∣ ≤ ∑ i = 1 ℓ ∣ Z ∩ H i ∣ ≤ t L h − 1 . \left|Z \cap\bigcup_{i=1}^{\ell} H_i\right| \le\sum_{i=1}^{\ell} |Z \cap H_i| \le tL_{h-1}. Z ∩ i = 1 ⋃ ℓ H i ≤ i = 1 ∑ ℓ ∣ Z ∩ H i ∣ ≤ t L h − 1 .
Hence
∣ Z ∖ ⋃ i = 1 ℓ H i ∣ ≥ L h − t L h − 1 = b . \left|Z \setminus\bigcup_{i=1}^{\ell} H_i\right| \ge L_h-tL_{h-1}=b. Z ∖ i = 1 ⋃ ℓ H i ≥ L h − t L h − 1 = b .
Finally, since ∣ D ∣ ≤ b − 1 |D| \le b-1 ∣ D ∣ ≤ b − 1 , at least one element of Z ∖ ⋃ i = 1 ℓ H i Z \setminus\bigcup_{i=1}^{\ell} H_i Z ∖ ⋃ i = 1 ℓ H i lies outside D D D . Thus there exists
y ∈ Z ∖ ( D ∪ ⋃ i = 1 ℓ H i ) . y \in Z \setminus\left(D \cup\bigcup_{i=1}^{\ell} H_i\right). y ∈ Z ∖ ( D ∪ i = 1 ⋃ ℓ H i ) .
Because Z ⊆ W Z \subseteq W Z ⊆ W and every element of Z Z Z has cost at most w ( x ) w(x) w ( x ) , this y y y satisfies
y ∈ W ∖ ( D ∪ ⋃ i = 1 ℓ H i ) , w ( y ) ≤ w ( x ) , y \in W \setminus\left(D \cup\bigcup_{i=1}^{\ell} H_i\right), \quad w(y) \le w(x), y ∈ W ∖ ( D ∪ i = 1 ⋃ ℓ H i ) , w ( y ) ≤ w ( x ) ,
as required. ∞ӘА
Constructing and searching the core
We apply the representative construction separately to safe and vulnerable elements. The resulting union contains an optimum by the replacement criterion, and its bounded size permits exhaustive search.
Theorem 3. On rank-r r r matroids given by independence oracles, Weighted Nonuniform Fault-Tolerant Basis is fixed-parameter tractable in r + k r+k r + k . The cases r = 0 r=0 r = 0 and k = 0 k=0 k = 0 are polynomial-time solvable. For r , k ≥ 1 r,k \ge1 r , k ≥ 1 , the running time is
2 O ( b log b + b r log ( r + k − 1 k ) ) n O ( 1 ) , b = ( k + 1 ) r . 2^{O\left(b\log b+br\log\binom{r+k-1}{k}\right)}n^{O(1)}, \qquad b=(k+1)r. 2 O ( b l o g b + b r l o g ( k r + k − 1 ) ) n O ( 1 ) , b = ( k + 1 ) r . In particular, the running time is 2 O ( ( r + k ) 4 ) n O ( 1 ) 2^{O((r+k)^4)}n^{O(1)} 2 O (( r + k ) 4 ) n O ( 1 ) .
Proof. For r = 0 r=0 r = 0 , return the empty set. For k = 0 k=0 k = 0 , return a minimum-cost basis using the matroid greedy algorithm. Henceforth assume r , k ≥ 1 r,k \ge1 r , k ≥ 1 .
To construct the core, delete all loops, which cannot improve a nonnegative-cost solution. Set
t = ( r + k − 1 k ) , b = ( k + 1 ) r . t=\binom{r+k-1}{k}, \qquad b=(k+1)r. t = ( k r + k − 1 ) , b = ( k + 1 ) r .
Apply Lemma 5 separately to the safe set S S S and the vulnerable set V V V , with these values of b b b and t t t . The flat tests in both applications use the ambient matroid M M M . Let W W W be the union of the two resulting cores. Then
∣ W ∣ ≤ 2 b ∑ j = 0 r − 1 t j . (4) |W| \le2b\sum_{j=0}^{r-1}t^j. \tag*{(4)} ∣ W ∣ ≤ 2 b j = 0 ∑ r − 1 t j . (4)
The factor two is unnecessary when all elements are vulnerable.
To prove that W W W contains an optimum, use Lemma 1 to choose a minimum-cost feasible set B B B with ∣ B ∣ ≤ b |B| \le b ∣ B ∣ ≤ b . Suppose x ∈ B ∖ W x \in B \setminus W x ∈ B ∖ W , and put Y = B ∖ { x } Y=B\setminus\{x\} Y = B ∖ { x } . Lemma 4 gives at most t t t members in H ( B , x ) \mathcal{H}(B,x) H ( B , x ) , each avoiding x x x . Apply Lemma 5 in the subset S S S or V V V containing x x x , with forbidden set D = Y D=Y D = Y . Since ∣ Y ∣ ≤ b − 1 |Y| \le b-1 ∣ Y ∣ ≤ b − 1 , it gives an element y ∈ W ∖ Y y \in W\setminus Y y ∈ W ∖ Y of the same safety type, with w ( y ) ≤ w ( x ) w(y) \le w(x) w ( y ) ≤ w ( x ) , outside every member of H ( B , x ) \mathcal{H}(B,x) H ( B , x ) . Also y ≠ x y\ne x y = x , because x ∉ W x\notin W x ∈ / W , so y ∉ B y\notin B y ∈ / B . Lemma 2 shows that B ′ = Y ∪ { y } B'=Y\cup\{y\} B ′ = Y ∪ { y } is feasible and has no greater cost.
We have ∣ B ′ ∣ = ∣ B ∣ |B'|=|B| ∣ B ′ ∣ = ∣ B ∣ , w ( B ′ ) ≤ w ( B ) w(B')\le w(B) w ( B ′ ) ≤ w ( B ) , and ∣ B ′ ∖ W ∣ = ∣ B ∖ W ∣ − 1 |B'\setminus W|=|B\setminus W|-1 ∣ B ′ ∖ W ∣ = ∣ B ∖ W ∣ − 1 . Since B B B was optimal, B ′ B' B ′ is optimal as well. Repeating this exchange at most b b b times produces an optimum contained in W W W . This is an existence argument; the algorithm need not identify an optimum or enumerate its deficient hyperplanes when constructing W W W .
To search the core, enumerate all subsets of W W W of size at most b b b . For each candidate, test every subset of its vulnerable elements of size at most k k k as a failure, using greedy rank computations on the survivors. Return a cheapest feasible candidate, or report infeasibility if none exists. The exchange argument proves correctness in both cases.
(4) and r ≤ b r\le b r ≤ b imply
log ( ∣ W ∣ + 1 ) = O ( log b + r log t ) . \log(|W|+1)=O(\log b+r\log t). log ( ∣ W ∣ + 1 ) = O ( log b + r log t ) .
There are at most ( ∣ W ∣ + 1 ) b + 1 (|W|+1)^{b+1} ( ∣ W ∣ + 1 ) b + 1 candidates. Each has at most 2 b 2^b 2 b failure subsets, and each survivor rank can be computed with at most b b b independence queries. Since b ≥ 2 b \ge2 b ≥ 2 , these verification costs are absorbed in
2 O ( b log b + b r log t ) n O ( 1 ) . 2^{O(b\log b+br\log t)}n^{O(1)}. 2 O ( b l o g b + b r l o g t ) n O ( 1 ) .
For core construction, the query bound of Lemma 5 has parameter-dependent logarithm
O ( ( r + 1 ) ( log b + r log t ) ) . O((r+1)(\log b+r\log t)). O (( r + 1 ) ( log b + r log t )) .
This is within the same bound because r + 1 ≤ b r+1 \le b r + 1 ≤ b . Cost sorting and arithmetic contribute polynomial overhead under the computational conventions of Section 2. Finally, b ≤ ( r + k + 1 ) 2 b \le(r+k+1)^2 b ≤ ( r + k + 1 ) 2 and log t ≤ r + k \log t \le r+k log t ≤ r + k , yielding the stated quartic-exponent upper bound. □ \square □
Remark 2. The core in Theorem 3 is a subset of the original ground set and contains a minimum-cost feasible solution whenever one exists. In the pure independence-oracle model, this does not by itself provide a polynomial-bit kernel: encoding the restricted matroid as a standalone instance is a separate issue.
Linear representations
Section 3 constructs a bounded subset of the ground set that contains an optimum. With an explicit linear representation, we can instead process the elements one at a time and maintain a bounded family of partial selections. Taking or skipping the next element generates new candidates; compression then retains a small subfamily. The main question is what this subfamily must preserve so that an optimum remains reachable.
Throughout this section, M M M is represented over a field F \mathbb{F} F , its ground set is partitioned into safe elements S S S and vulnerable elements V V V , and costs are nonnegative. Retaining a basis of the row space lets us assume that the representing columns belong to F r \mathbb{F}^r F r , where r = rank ( M ) r=\operatorname{rank}(M) r = rank ( M ) . For rank zero, the empty set is optimal; for k = 0 k=0 k = 0 , a minimum-cost basis is optimal. The parameter estimates for the fault-tolerant algorithm therefore assume r , k ≥ 1 r,k \ge1 r , k ≥ 1 .
What compression must preserve
Fix an order e 1 , … , e n e_1,\ldots,e_n e 1 , … , e n of the ground set and a processed prefix E j = { e 1 , … , e j } E_j=\{e_1,\ldots,e_j\} E j = { e 1 , … , e j } . A partial selection is a set P ⊆ E j P\subseteq E_j P ⊆ E j , and a future completion is a set Z ⊆ E ∖ E j Z\subseteq E\setminus E_j Z ⊆ E ∖ E j . We call Z Z Z successful for P P P if P ∪ Z P\cup Z P ∪ Z is feasible, that is,
rank M ( ( P ∪ Z ) ∖ F ) = r for every F ⊆ ( P ∪ Z ) ∩ V with ∣ F ∣ ≤ k . \operatorname{rank}_M((P\cup Z)\setminus F)=r \quad\text{for every } F\subseteq(P\cup Z)\cap V \text{ with } |F|\le k. rank M (( P ∪ Z ) ∖ F ) = r for every F ⊆ ( P ∪ Z ) ∩ V with ∣ F ∣ ≤ k .
The algorithm will group partial selections by their numbers of safe and vulnerable elements. Replacing a selection within such a group preserves these counts, so the same completion still gives the same final counts.
Definition 2. Let P \mathcal{P} P be a family of subsets of E j E_j E j , all with the same numbers of safe and vulnerable elements. A subfamily P ^ ⊆ P \widehat{\mathcal{P}} \subseteq\mathcal{P} P ⊆ P is representative for common completions if, for every P ∈ P P \in\mathcal{P} P ∈ P and every Z ⊆ E ∖ E j Z \subseteq E \setminus E_j Z ⊆ E ∖ E j successful for P P P , there exists P ′ ∈ P ^ P' \in\widehat{\mathcal{P}} P ′ ∈ P such that
w ( P ′ ) ≤ w ( P ) and P ′ ∪ Z is feasible. w(P') \leq w(P) \qquad\text{and} \qquad P' \cup Z \text{ is feasible.} w ( P ′ ) ≤ w ( P ) and P ′ ∪ Z is feasible. When final safe and vulnerable counts are prescribed, we require this property only for completions Z Z Z meeting those counts.
Here P ′ P' P ′ may depend on P P P and Z Z Z , but it must be chosen before the failure occurs: one retained partial selection must work with the fixed set Z Z Z under every allowed failure of P ′ ∪ Z P' \cup Z P ′ ∪ Z . Preserving a separate representative for each failure is therefore insufficient. We also preserve the completion Z Z Z itself, rather than merely the existence of some completion. At the final prefix, Z = ∅ Z = \varnothing Z = ∅ , and the property ensures that an optimum has a retained feasible replacement of no greater cost.
We obtain this guarantee from a cost-ordered linear-basis construction. First we state the underlying linear-algebra lemma and illustrate how it preserves simultaneous spanning constraints. We then encode all allowed failures in one polynomial: substituting a fixed completion gives a nonzero polynomial exactly when that completion is successful. Applying the same linear-basis construction to coefficient vectors yields the required representatives. The resulting dynamic program is given in Theorem 4. Finally, Section 4.5 gives a simpler ground-set reduction for fixed finite fields.
Compression by linear representatives
To obtain the representatives of Definition 2, we will associate a vector v ( P ) v(P) v ( P ) with each partial selection P P P in a fixed group. A future completion Z Z Z will determine a linear map L Z L_Z L Z , common to the group, such that
L Z ( v ( P ) ) ≠ 0 ⟺ P ∪ Z is feasible. L_Z(v(P)) \ne0 \quad\Longleftrightarrow\quad P \cup Z \text{ is feasible.} L Z ( v ( P )) = 0 ⟺ P ∪ Z is feasible.
Constructing these vectors and maps is the main task in Section 4.3. Once they are available, a simple linear-basis selection provides the compression.
Process the partial selections in nondecreasing cost order and retain a selection only when its vector is independent of those already retained. A discarded vector is a linear combination of retained vectors of no greater cost. If a linear map is nonzero on the discarded vector, it must be nonzero on at least one vector in this combination. Applied to L Z L_Z L Z , this gives a retained selection that works with the same completion Z Z Z . The retained family is chosen once and has size at most the dimension of the vector space; the successful retained selection may depend on Z Z Z . The following lemma states this principle for arbitrary objects and linear maps.
Lemma 6. Let A A A be a finite family of objects, each with a cost c ( A ) c(A) c ( A ) and an associated vector v ( A ) v(A) v ( A ) in a finite-dimensional vector space U U U over F F F . Process the objects in nondecreasing order of costs, retaining an object exactly when
its vector does not belong to the span of the previously retained vectors. The resulting subfamily A ^ \widehat{\mathcal{A}} A has size at most dim U \dim U dim U . Moreover, for every F \mathbb{F} F -linear map L : U → W L: U \to W L : U → W and every A ∈ A A \in\mathcal{A} A ∈ A with L ( v ( A ) ) ≠ 0 L(v(A)) \ne0 L ( v ( A )) = 0 , there is an object A ′ ∈ A ^ A' \in\widehat{\mathcal{A}} A ′ ∈ A such that c ( A ′ ) ≤ c ( A ) c(A') \le c(A) c ( A ′ ) ≤ c ( A ) and L ( v ( A ′ ) ) ≠ 0 L(v(A')) \ne0 L ( v ( A ′ )) = 0 .
Proof. The retained vectors are linearly independent, so ∣ A ^ ∣ ≤ dim U |\widehat{\mathcal{A}}| \le\dim U ∣ A ∣ ≤ dim U . Fix an F \mathbb{F} F -linear map L : U → W L: U \to W L : U → W and an object A ∈ A A \in\mathcal{A} A ∈ A such that L ( v ( A ) ) ≠ 0 L(v(A)) \ne0 L ( v ( A )) = 0 . If A A A is retained, take A ′ = A A' = A A ′ = A . Otherwise, when A A A is processed, the vector v ( A ) v(A) v ( A ) lies in the span of the previously retained vectors. Thus
v ( A ) = ∑ j = 1 t α j v ( A j ) , α j ∈ F , (5) v(A) = \sum_{j=1}^{t} \alpha_j v(A_j), \qquad\alpha_j \in\mathbb{F}, \tag*{(5)} v ( A ) = j = 1 ∑ t α j v ( A j ) , α j ∈ F , (5)
where A 1 , … , A t A_1,\ldots,A_t A 1 , … , A t are previously retained objects. Since the objects are processed in nondecreasing order of cost, c ( A j ) ≤ c ( A ) c(A_j) \le c(A) c ( A j ) ≤ c ( A ) for every j ∈ [ t ] j \in[t] j ∈ [ t ] . Applying L L L to (5) gives
L ( v ( A ) ) = ∑ j = 1 t α j L ( v ( A j ) ) . L(v(A)) = \sum_{j=1}^{t} \alpha_j L(v(A_j)). L ( v ( A )) = j = 1 ∑ t α j L ( v ( A j )) .
Since the left-hand side is nonzero, L ( v ( A j ) ) ≠ 0 L(v(A_j)) \ne0 L ( v ( A j )) = 0 for some j ∈ [ t ] j \in[t] j ∈ [ t ] . Taking A ′ = A j A' = A_j A ′ = A j proves the claim. □ \square □
The target space W W W need not be finite-dimensional. In particular, it may be a polynomial ring over F \mathbb{F} F , viewed as an F \mathbb{F} F -vector space. In the fault-tolerant application, v ( P ) v(P) v ( P ) will be the coefficient vector of a polynomial G P G_P G P , and L Z L_Z L Z will apply the symbolic substitution associated with Z Z Z . Although this substitution replaces variables by polynomials, it is linear over F \mathbb{F} F : it preserves sums and multiplication by field scalars. Thus the lemma applies to the finite-dimensional coefficient space.
Here a nonzero output means a polynomial that is not identically zero ; we do not assign numerical values to its remaining indeterminates. This distinction matters over small finite fields, where a nonzero formal polynomial can vanish at every assignment of field elements. The representative selection uses exact linear algebra on coefficient vectors and requires no random evaluation.
Before constructing these polynomials, we illustrate the same principle with simultaneous spanning in several linear matroids. In that application, a tensor product combines the spanning tests into one linear functional, so one retained partial selection works with a fixed completion in every matroid. The resulting lemma will also be used for explicitly listed failure scenarios.
Lemma 7. Let M 1 , … , M m M_1,\ldots,M_m M 1 , … , M m be linear matroids on a common n n n -element ground set E E E , represented over the same field F \mathbb{F} F , with respective ranks r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m . Let w : E → Z ≥ 0 w: E \to\mathbb{Z}_{\ge0} w : E → Z ≥ 0 be a cost function and put R = ∑ i = 1 m r i R = \sum_{i=1}^{m} r_i R = ∑ i = 1 m r i . A minimum-cost set B ⊆ E B \subseteq E B ⊆ E satisfying rank M i ( B ) = r i \operatorname{rank}_{M_i}(B) = r_i rank M i ( B ) = r i for every i ∈ [ m ] i \in[m] i ∈ [ m ] can be found using 2 O ( R ) n O ( 1 ) 2^{O(R)}n^{O(1)} 2 O ( R ) n O ( 1 ) field operations after reading and reducing the representations. Including this preprocessing, the running time is 2 O ( R ) poly ( L i n ) 2^{O(R)}\operatorname{poly}(L_{\mathrm{in}}) 2 O ( R ) poly ( L in ) in the field-operation model, where L i n L_{\mathrm{in}} L in is the input encoding length.
Proof. Discard all rank-zero matroids, since every subset of E E E spans them. If no constraints remain, return the empty set. We may therefore assume that every r i r_i r i is positive and m ≤ R m \le R m ≤ R . For each i i i , retain r i r_i r i independent rows of its representing matrix, obtaining a matrix A i A_i A i representing the same matroid M i M_i M i . Fix a common ground-set order e 1 , … , e n e_1,\ldots,e_n e 1 , … , e n and write a i ( e ) ∈ F r i a_i(e) \in\mathbb{F}^{r_i} a i ( e ) ∈ F r i for the column of e e e in A i A_i A i .
For a partial set P P P selected from a processed prefix, let p ( P ) = ( p 1 , … , p m ) p(P) = (p_1,\ldots,p_m) p ( P ) = ( p 1 , … , p m ) , where p i = rank M i ( P ) p_i = \operatorname{rank}_{M_i}(P) p i = rank M i ( P ) , be its rank profile. We first compress an arbitrary family of partial sets with one fixed profile. The construction has three ingredients: a vector encoding each partial span, a linear test for completing that span, and a tensor product combining the tests for all matroids.
Encoding a partial span by its minors. For each i ∈ [ m ] i \in[m] i ∈ [ m ] , choose an ordered subset B i ( P ) = ( b i , 1 , … , b i , p i ) B_i(P) = (b_{i,1},\ldots,b_{i,p_i}) B i ( P ) = ( b i , 1 , … , b i , p i ) of P P P whose columns form a basis of its span in A i A_i A i . Define
v i ( P ) = a i ( b i , 1 ) ∧ ⋯ ∧ a i ( b i , p i ) ∈ U i : = ⋀ p i F r i . v_i(P) = a_i(b_{i,1}) \wedge\cdots\wedge a_i(b_{i,p_i}) \in U_i := \bigwedge^{p_i}\mathbb{F}^{r_i}. v i ( P ) = a i ( b i , 1 ) ∧ ⋯ ∧ a i ( b i , p i ) ∈ U i := ⋀ p i F r i .
Concretely, v i ( P ) v_i(P) v i ( P ) is a vector with one coordinate for each p i p_i p i -element subset of the rows: that coordinate is the corresponding p i × p i p_i \times p_i p i × p i minor of the chosen basis matrix. Thus dim U i = ( r i p i ) \dim U_i = \binom{r_i}{p_i} dim U i = ( p i r i ) . When p i = 0 p_i = 0 p i = 0 , we use v i ( P ) = 1 ∈ ⋀ 0 F r i = F v_i(P) = 1 \in\bigwedge^0 \mathbb{F}^{r_i} = \mathbb{F} v i ( P ) = 1 ∈ ⋀ 0 F r i = F . Changing the ordered basis of the same span multiplies all these coordinates by one nonzero scalar, which does not affect any of the nonvanishing tests below.
Testing a completion by a determinant. Fix a set Z Z Z of unprocessed elements such that P ∪ Z P \cup Z P ∪ Z spans every matroid. For each i i i , extend B i ( P ) B_i(P) B i ( P ) to a basis of M i M_i M i using an ordered subset Q i = ( z i , 1 , … , z i , r i − p i ) Q_i = (z_{i,1},\ldots,z_{i,r_i-p_i}) Q i = ( z i , 1 , … , z i , r i − p i ) of Z Z Z . The subsets Q i Q_i Q i may differ between matroids, but they are all taken from the same completion Z Z Z . Identifying the top exterior power ⋀ r i F r i \bigwedge^{r_i}\mathbb{F}^{r_i} ⋀ r i F r i with F \mathbb{F} F , define
λ i : U i ⟶ F , u ⟼ u ∧ a i ( z i , 1 ) ∧ ⋯ ∧ a i ( z i , r i − p i ) . \lambda_i : U_i \longrightarrow\mathbb{F}, \qquad u \longmapsto u \wedge a_i(z_{i,1}) \wedge\cdots\wedge a_i(z_{i,r_i-p_i}). λ i : U i ⟶ F , u ⟼ u ∧ a i ( z i , 1 ) ∧ ⋯ ∧ a i ( z i , r i − p i ) .
This is a linear functional. In coordinates, appending the fixed columns of Q i Q_i Q i gives a determinant that is a linear combination of the minors stored in u u u , by Laplace expansion. In particular,
λ i ( v i ( P ) ) = det [ a i ( b i , 1 ) ∣ ⋯ ∣ a i ( b i , p i ) ∣ a i ( z i , 1 ) ∣ ⋯ ∣ a i ( z i , r i − p i ) ] ≠ 0. \lambda_i(v_i(P)) = \det\left[ a_i(b_{i,1}) \mid\cdots\mid a_i(b_{i,p_i}) \mid a_i(z_{i,1}) \mid\cdots\mid a_i(z_{i,r_i-p_i}) \right] \ne0. λ i ( v i ( P )) = det [ a i ( b i , 1 ) ∣ ⋯ ∣ a i ( b i , p i ) ∣ a i ( z i , 1 ) ∣ ⋯ ∣ a i ( z i , r i − p i ) ] = 0.
If p i = r i p_i = r_i p i = r i , then Q i Q_i Q i is empty and λ i \lambda_i λ i is just the identification of the top exterior power with F \mathbb{F} F . For any other partial set P ′ P' P ′ with the same profile, λ i ( v i ( P ′ ) ) ≠ 0 \lambda_i(v_i(P')) \ne0 λ i ( v i ( P ′ )) = 0 implies that B i ( P ′ ) ∪ Q i B_i(P') \cup Q_i B i ( P ′ ) ∪ Q i is a basis, so P ′ ∪ Z P' \cup Z P ′ ∪ Z spans M i M_i M i . These witness subsets and functionals are used only to prove preservation; the compression procedure does not need to know Z Z Z .
Combining all spanning requirements. Applying the representative lemma separately in each U i U_i U i could produce different retained partial sets for different matroids. To obtain one partial set that passes all the tests, associate with P P P the tensor vector
Φ ( P ) = ⨂ i = 1 m v i ( P ) ∈ U P : = ⨂ i = 1 m U i , D P : = dim U P = ∏ i = 1 m ( r i p i ) . \Phi(P) = \bigotimes_{i=1}^{m} v_i(P) \in U_P := \bigotimes_{i=1}^{m} U_i,\qquad D_P := \dim U_P = \prod_{i=1}^{m} \binom{r_i}{p_i}. Φ ( P ) = i = 1 ⨂ m v i ( P ) ∈ U P := i = 1 ⨂ m U i , D P := dim U P = i = 1 ∏ m ( p i r i ) .
Its coordinates are all products formed by taking one coordinate from each v i ( P ) v_i(P) v i ( P ) . The tensor product of the functionals is a linear functional Λ = λ 1 ⊗ ⋯ ⊗ λ m : U p → F \Lambda= \lambda_1 \otimes\cdots\otimes\lambda_m : U_p \to\mathbb{F} Λ = λ 1 ⊗ ⋯ ⊗ λ m : U p → F satisfying
Λ ( Φ ( P ) ) = ∏ i = 1 m λ i ( v i ( P ) ) ≠ 0. \Lambda(\Phi(P)) = \prod_{i=1}^{m} \lambda_i(v_i(P)) \ne0. Λ ( Φ ( P )) = i = 1 ∏ m λ i ( v i ( P )) = 0.
A product of field elements is nonzero exactly when every factor is nonzero. Thus this single linear test enforces all the spanning requirements simultaneously.
For each rank profile, process the candidate partial sets in nondecreasing cost order and retain a set precisely when its tensor vector is independent of the previously retained vectors. This retains at most D p D_p D p sets. By Lemma 6, the nonzero value of Λ ( Φ ( P ) ) \Lambda(\Phi(P)) Λ ( Φ ( P )) guarantees a retained set P ′ P' P ′ with w ( P ′ ) ≤ w ( P ) w(P') \leq w(P) w ( P ′ ) ≤ w ( P ) and Λ ( Φ ( P ′ ) ) ≠ 0 \Lambda(\Phi(P')) \ne0 Λ ( Φ ( P ′ )) = 0 . Every factor λ i ( v i ( P ′ ) ) \lambda_i(v_i(P')) λ i ( v i ( P ′ )) is therefore nonzero, so B i ( P ′ ) B_i(P') B i ( P ′ ) together with Q i Q_i Q i forms a basis of M i M_i M i for every i i i . Consequently, the same retained set P ′ P' P ′ works with the same completion Z Z Z in all matroids. This proves the required compression guarantee within a fixed rank profile.
The dynamic program. We now use this compression procedure in a dynamic program that processes e 1 , … , e n e_1,\ldots,e_n e 1 , … , e n in order. After each processed prefix, we maintain a retained family of partial sets for every rank profile. Initially, only the empty set is retained, in profile ( 0 , … , 0 ) (0,\ldots,0) ( 0 , … , 0 ) . When processing the next element e e e , generate the two successors P P P and P ∪ { e } P \cup\{e\} P ∪ { e } from every retained partial set P P P . Compute the rank profile of each successor and group all successors with the same profile together. Apply the compression procedure to each group to obtain the retained families for the new prefix. After processing all elements, return a cheapest retained set with profile ( r 1 , … , r m ) (r_1,\ldots,r_m) ( r 1 , … , r m ) . Such a set exists because E E E spans every M i M_i M i and compression preserves successful completions.
Preserving an optimum. For correctness, we prove by induction on the processed prefix that whenever P ⊆ { e 1 , … , e j } P \subseteq\{e_1,\ldots,e_j\} P ⊆ { e 1 , … , e j } and Z ⊆ { e j + 1 , … , e n } Z \subseteq\{e_{j+1},\ldots,e_n\} Z ⊆ { e j + 1 , … , e n } satisfy that P ∪ Z P \cup Z P ∪ Z spans every matroid, some retained set P ′ P' P ′ has w ( P ′ ) ≤ w ( P ) w(P') \leq w(P) w ( P ′ ) ≤ w ( P ) and P ′ ∪ Z P' \cup Z P ′ ∪ Z spans every matroid. The profiles of P P P and P ′ P' P ′ need not agree. The claim holds for the empty prefix. Assume that it holds after processing j − 1 j-1 j − 1 elements and let e = e j e=e_j e = e j . If e ∉ P e \notin P e ∈ / P , apply the inductive hypothesis to P P P with completion Z Z Z . It gives a retained set P ^ \widehat{P} P of no greater cost whose skip successor has successful completion Z Z Z . If e ∈ P e \in P e ∈ P , apply the hypothesis to P ∖ { e } P \setminus\{e\} P ∖ { e } with completion Z ∪ { e } Z \cup\{e\} Z ∪ { e } . It gives a retained set P ^ \widehat{P} P with w ( P ^ ) ≤ w ( P ∖ { e } ) w(\widehat{P}) \leq w(P \setminus\{e\}) w ( P ) ≤ w ( P ∖ { e }) such that P ^ ∪ Z ∪ { e } \widehat{P} \cup Z \cup\{e\} P ∪ Z ∪ { e } spans every matroid. Its take successor P ^ ∪ { e } \widehat{P} \cup\{e\} P ∪ { e } has cost at most w ( P ) w(P) w ( P ) and successful completion Z Z Z . In either case, compression in the successor’s actual profile preserves a suitable set by the preceding argument. At the final prefix, applying the invariant to an optimum with Z = ∅ Z=\varnothing Z = ∅ proves optimality of the returned set.
Bounding the retained families and running time. The total number of retained sets at any prefix is at most
D p = ∑ p 1 = 0 r 1 ⋯ ∑ p m = 0 r m ( ∏ i = 1 m ( r i p i ) ) = ∏ i = 1 m ( ∑ p i = 0 r i ( r i p i ) ) = ∏ i = 1 m 2 r i = 2 R , as ∑ i = 1 m r i = R . D_p=\sum_{p_1=0}^{r_1}\cdots\sum_{p_m=0}^{r_m}\left(\prod_{i=1}^{m}\binom{r_i}{p_i}\right)
=\prod_{i=1}^{m}\left(\sum_{p_i=0}^{r_i}\binom{r_i}{p_i}\right)
=\prod_{i=1}^{m}2^{r_i}=2^R,\qquad\text{as }\sum_{i=1}^{m}r_i=R. D p = p 1 = 0 ∑ r 1 ⋯ p m = 0 ∑ r m ( i = 1 ∏ m ( p i r i ) ) = i = 1 ∏ m ( p i = 0 ∑ r i ( p i r i ) ) = i = 1 ∏ m 2 r i = 2 R , as i = 1 ∑ m r i = R .
Thus each prefix generates at most 2 R + 1 2^{R+1} 2 R + 1 candidates. A skip successor inherits its parent’s basis columns. For a take successor, append the new column in each matroid where it increases the rank. This gives the successor’s rank profile and basis columns in poly ( R ) \operatorname{poly}(R) poly ( R ) field operations. Each exterior coordinate is a minor of order at most R R R and each tensor coordinate is a product of at most R R R exterior coordinates. Since D p ≤ 2 R D_p\le2^R D p ≤ 2 R , forming the vectors and compressing the candidate families takes 2 O ( R ) 2^{O(R)} 2 O ( R ) field operations per prefix and 2 O ( R ) n O ( 1 ) 2^{O(R)}n^{O(1)} 2 O ( R ) n O ( 1 ) overall. Cost additions and comparisons use integers of polynomial binary length. The selected sets or predecessor information suffice to reconstruct an optimum. Reading and reducing the representations takes polynomial input time. □ \square □
A polynomial certificate for common completions
We now construct the vectors and linear maps promised in § 4.2 . For each partial selection P P P , we will build a polynomial G P G_P G P . A fixed future completion Z Z Z will determine a symbolic substitution ev Z \operatorname{ev}_Z ev Z , common to all partial selections in the same state, with the property
ev Z ( G P ) ≢ 0 ⟺ P ∪ Z survives every allowed failure. \operatorname{ev}_Z(G_P)\not\equiv0\Longleftrightarrow P\cup Z\text{ survives every allowed failure.} ev Z ( G P ) ≡ 0 ⟺ P ∪ Z survives every allowed failure.
The coefficient vector of G P G_P G P will then be the vector to which we apply Lemma 6. There can be many failure patterns. Instead of introducing a separate tensor factor for each test, we will express all tests in the same polynomial ring and multiply them. Multiplication increases the degree, but introduces no new variables. This is the source of the eventual dimension bound: the ring has only O ( r ( r + k ) ) O(r(r+k)) O ( r ( r + k )) variables, irrespective of the number of failure patterns. We first describe a completion by formal weighted sums of its columns, then filter out failed future columns, and finally test the surviving rank by a determinant. The product of these tests will enforce all failures together.
Fixing a state and its future slots. Fix a target solution size 0 ≤ s ≤ b = ( k + 1 ) r 0\le s\le b=(k+1)r 0 ≤ s ≤ b = ( k + 1 ) r and a target vulnerable count 0 ≤ s V ≤ s 0\le s_V\le s 0 ≤ s V ≤ s . A partial set P P P in the processed prefix has state ( a S , a V , p ) (a_S,a_V,p) ( a S , a V , p ) , where
a S = ∣ P ∩ S ∣ , a V = ∣ P ∩ V ∣ , p = rank M ( P ) . a_S=|P\cap S|,\qquad a_V=|P\cap V|,\qquad p=\operatorname{rank}_M(P). a S = ∣ P ∩ S ∣ , a V = ∣ P ∩ V ∣ , p = rank M ( P ) .
Its rank deficiency and the required numbers of future elements are
d = r − p , q S = s − s V − a S , q V = s V − a V , d=r-p,\qquad q_S=s-s_V-a_S,\qquad q_V=s_V-a_V, d = r − p , q S = s − s V − a S , q V = s V − a V ,
q = q S + q V = s − a S − a V . q=q_S+q_V=s-a_S-a_V. q = q S + q V = s − a S − a V .
We consider only states with q S , q V ≥ 0 q_S,q_V \ge0 q S , q V ≥ 0 . A completion Z Z Z consists of unprocessed elements with exactly q S q_S q S safe and q V q_V q V vulnerable elements.
To describe every such completion in the same variables, fix q q q future slots. The first q S q_S q S are safe and the remaining q V q_V q V are vulnerable; write [ q ] V = { q S + 1 , … , q } [q]_V = \{q_S + 1,\ldots,q\} [ q ] V = { q S + 1 , … , q } , interpreted as the empty set when q V = 0 q_V = 0 q V = 0 . Assign the safe elements of Z Z Z to the safe slots in ground-set order, and assign its vulnerable elements to the vulnerable slots in the same way. Let z j z_j z j occupy slot j j j . This assignment depends only on Z Z Z and the state counts, so it is identical for every partial set in the state. In particular, a fixed failed-slot set describes the same failed future elements when we compare different partial sets.
Representing a completion by shared moments. We use d + k d+k d + k vector variables to stand for weighted sums of future columns. This number is sufficient because a failure of at most k k k selected elements increases the current rank deficiency by at most k k k . Each future slot also receives a formal tag; these tags will allow us to remove precisely the slots that fail. The variables are shared by all failure patterns and by all partial sets in the state.
Introduce vector indeterminates X h = ( X h , 1 , … , X h , r ) T \mathbf{X}_h = (X_{h,1},\ldots,X_{h,r})^{\mathsf{T}} X h = ( X h , 1 , … , X h , r ) T for 0 ≤ h < d + k 0 \le h < d+k 0 ≤ h < d + k and scalar tag indeterminates T 1 , … , T q T_1,\ldots,T_q T 1 , … , T q . Let
R p , q = F [ X h , ℓ : 0 ≤ h < d + k , 1 ≤ ℓ ≤ r ] [ T 1 , … , T q ] . (6) R_{p,q} = \mathbb{F}[X_{h,\ell} : 0 \le h < d+k,\ 1 \le\ell\le r][T_1,\ldots,T_q]. \tag*{(6)} R p , q = F [ X h , ℓ : 0 ≤ h < d + k , 1 ≤ ℓ ≤ r ] [ T 1 , … , T q ] . (6)
This is the polynomial ring over F \mathbb{F} F in the moment coordinates and slot tags. In particular, X h \mathbf{X}_h X h is a vector in R p , q r \mathbb{R}_{p,q}^r R p , q r , rather than a scalar polynomial. All coordinates and tags are independent formal variables.
The polynomial certificate is constructed before the future columns are known. A completion is used only to interpret its variables through the following substitution. This is the linear map used in the preservation proof, not an operation that requires the algorithm to enumerate completions.
For a completion Z Z Z , introduce additional indeterminates u 1 , … , u q u_1,\ldots,u_q u 1 , … , u q and write a z j ∈ F r \mathbf{a}_{z_j} \in\mathbb{F}^r a z j ∈ F r for the column of z j z_j z j . Define the F \mathbb{F} F -algebra homomorphism
ev Z : R p , q ⟶ F [ T 1 , … , T q , u 1 , … , u q ] \operatorname{ev}_Z : R_{p,q} \longrightarrow\mathbb{F}[T_1,\ldots,T_q,u_1,\ldots,u_q] ev Z : R p , q ⟶ F [ T 1 , … , T q , u 1 , … , u q ]
by fixing each tag and substituting
ev Z ( X h , ℓ ) = ∑ j = 1 q u j T j h a z j , ℓ , 0 ≤ h < d + k , 1 ≤ ℓ ≤ r . (7) \operatorname{ev}_Z(X_{h,\ell}) = \sum_{j=1}^{q} u_j T_j^h a_{z_j,\ell}, \qquad0 \le h < d+k,\ 1 \le\ell\le r. \tag*{(7)} ev Z ( X h , ℓ ) = j = 1 ∑ q u j T j h a z j , ℓ , 0 ≤ h < d + k , 1 ≤ ℓ ≤ r . (7)
The map preserves field constants, addition and multiplication. Applied coordinatewise, it sends X h \mathbf{X}_h X h to ∑ j = 1 q u j T j h a z j \sum_{j=1}^{q} u_jT_j^h\mathbf{a}_{z_j} ∑ j = 1 q u j T j h a z j . These weighted sums are the moments of the completion. The variables u j u_j u j are used only in this interpretation and do not belong to R p , q R_{p,q} R p , q . We write G ∣ Z = ev Z ( G ) G|_Z = \operatorname{ev}_Z(G) G ∣ Z = ev Z ( G ) for a polynomial or polynomial vector G G G . If q = 0 q = 0 q = 0 , each moment coordinate is sent to zero. All nonvanishing statements below concern formal polynomials after substitution.
Filtering out failed future columns. Fix the future slots that fail. We want to remove their contributions from every weighted sum without introducing new variables. A polynomial vanishing at exactly their formal tags provides the required filter: multiplying the contribution of slot j j j by its value at T j T_j T j kills a failed slot and leaves a nonzero formal weight on every survivor.
For a set J ⊆ [ q ] V J \subseteq[q]_V J ⊆ [ q ] V of failed future slots, define the filter polynomial and filtered moments by
Fltr J ( t ) = ∏ j ∈ J ( t − T j ) = ∑ ν = 0 ∣ J ∣ c J , ν t ν , (8) \operatorname{Fltr}_J(t)=\prod_{j\in J}(t-T_j)=\sum_{\nu=0}^{|J|}c_{J,\nu}t^\nu, \tag*{(8)} Fltr J ( t ) = j ∈ J ∏ ( t − T j ) = ν = 0 ∑ ∣ J ∣ c J , ν t ν , (8)
Y J , h = ∑ ν = 0 ∣ J ∣ c J , ν X h + ν , 0 ≤ h ≤ d + k − ∣ J ∣ − 1. (9) Y_{J,h}=\sum_{\nu=0}^{|J|}c_{J,\nu}X_{h+\nu},\qquad0\le h\le d+k-|J|-1. \tag*{(9)} Y J , h = ν = 0 ∑ ∣ J ∣ c J , ν X h + ν , 0 ≤ h ≤ d + k − ∣ J ∣ − 1. (9)
Here c J , ν ∈ F [ T 1 , … , T q ] c_{J,\nu}\in\mathbb{F}[T_1,\ldots,T_q] c J , ν ∈ F [ T 1 , … , T q ] and each Y J , h Y_{J,h} Y J , h belongs to R p , q r \mathcal{R}_{p,q}^r R p , q r . When J = ∅ J=\emptyset J = ∅ , the filter is 1 1 1 and Y ∅ , h = X h Y_{\emptyset,h}=X_h Y ∅ , h = X h . Substituting (7) into (9) gives
Y J , h ∣ Z = ∑ j = 1 q u j T j h ( ∑ ν = 0 ∣ J ∣ c J , ν T j ν ) a z j = ∑ j ∈ [ q ] ∖ J u j T j h Fltr J ( T j ) a z j . (10) \left.Y_{J,h}\right|_Z=\sum_{j=1}^{q}u_jT_j^h\left(\sum_{\nu=0}^{|J|}c_{J,\nu}T_j^\nu\right)a_{z_j}=\sum_{j\in[q]\setminus J}u_jT_j^h\operatorname{Fltr}_J(T_j)a_{z_j}. \tag*{(10)} Y J , h ∣ Z = j = 1 ∑ q u j T j h ν = 0 ∑ ∣ J ∣ c J , ν T j ν a z j = j ∈ [ q ] ∖ J ∑ u j T j h Fltr J ( T j ) a z j . (10)
The failed terms vanish because Fltr J ( T j ) = 0 \operatorname{Fltr}_J(T_j)=0 Fltr J ( T j ) = 0 for j ∈ J j\in J j ∈ J . For j ∉ J j\notin J j ∈ / J , the polynomial Fltr J ( T j ) = ∏ v ∈ J ( T j − T v ) \operatorname{Fltr}_J(T_j)=\prod_{v\in J}(T_j-T_v) Fltr J ( T j ) = ∏ v ∈ J ( T j − T v ) is nonzero. Thus the filter removes failed future columns while preserving a formal contribution from every survivor.
For example, take r = 2 r=2 r = 2 and k = 1 k=1 k = 1 and let the partial solution consist of one nonzero column a a a , so d = 1 d=1 d = 1 and the available moments are X 0 , X 1 X_0,X_1 X 0 , X 1 . Suppose that both future slots are vulnerable and the first fails. Then Fltr { 1 } ( t ) = t − T 1 \operatorname{Fltr}_{\{1\}}(t)=t-T_1 Fltr { 1 } ( t ) = t − T 1 and Y { 1 } , 0 = X 1 − T 1 X 0 Y_{\{1\},0}=X_1-T_1X_0 Y { 1 } , 0 = X 1 − T 1 X 0 . Consequently, Y { 1 } , 0 ∣ Z = u 2 ( T 2 − T 1 ) a z 2 \left.Y_{\{1\},0}\right|_Z=u_2(T_2-T_1)a_{z_2} Y { 1 } , 0 Z = u 2 ( T 2 − T 1 ) a z 2 and
det [ a ∣ Y { 1 } , 0 ] ∣ Z = u 2 ( T 2 − T 1 ) det [ a ∣ a z 2 ] . (11) \det[a\mid Y_{\{1\},0}]\big|_Z=u_2(T_2-T_1)\det[a\mid a_{z_2}]. \tag*{(11)} det [ a ∣ Y { 1 } , 0 ] Z = u 2 ( T 2 − T 1 ) det [ a ∣ a z 2 ] . (11)
This polynomial is nonzero exactly when the surviving future column completes the past span. The factor T 2 − T 1 T_2-T_1 T 2 − T 1 remains nonzero over F 2 \mathbb{F}_2 F 2 because the tags are distinct indeterminates.
We now define the rank test for a single failure pattern. Fix a partial set P P P in the state and let I ⊆ P ∩ V I\subseteq P\cap V I ⊆ P ∩ V and J ⊆ [ q ] V J\subseteq[q]_V J ⊆ [ q ] V satisfy ∣ I ∣ + ∣ J ∣ ≤ k |I|+|J|\le k ∣ I ∣ + ∣ J ∣ ≤ k . Choose an ordered basis of the span of P ∖ I P\setminus I P ∖ I from its input columns and let A I A_I A I be the resulting matrix. Put δ I = r − rank M ( P ∖ I ) \delta_I=r-\operatorname{rank}_M(P\setminus I) δ I = r − rank M ( P ∖ I ) , so A I A_I A I has r − δ I r-\delta_I r − δ I columns. Since deleting ∣ I ∣ |I| ∣ I ∣ elements decreases rank by at most ∣ I ∣ |I| ∣ I ∣ , we have δ I ≤ d + ∣ I ∣ \delta_I\le d+|I| δ I ≤ d + ∣ I ∣ . Define
Δ P , I , J = { det [ A I ∣ Y J , 0 ∣ ⋯ ∣ Y J , δ I − 1 ] if δ I > 0 , 1 if δ I = 0. (12) \Delta_{P,I,J}=
\begin{cases}
\det[A_I\mid Y_{J,0}\mid\cdots\mid Y_{J,\delta_I-1}] & \text{if }\delta_I>0,\\
1 & \text{if }\delta_I=0.
\end{cases} \tag*{(12)} Δ P , I , J = { det [ A I ∣ Y J , 0 ∣ ⋯ ∣ Y J , δ I − 1 ] 1 if δ I > 0 , if δ I = 0. (12)
The determinant has exactly r r r columns. All moments it needs are available, because its largest moment index is δ I − 1 + ∣ J ∣ ≤ d + ∣ I ∣ + ∣ J ∣ − 1 ≤ d + k − 1 \delta_I-1+|J|\le d+|I|+|J|-1\le d+k-1 δ I − 1 + ∣ J ∣ ≤ d + ∣ I ∣ + ∣ J ∣ − 1 ≤ d + k − 1 . For δ I = 0 \delta_I=0 δ I = 0 , the surviving past set already spans the matroid. Changing the ordered basis matrix A I A_I A I multiplies a determinant with δ I > 0 \delta_I>0 δ I > 0 by a nonzero field scalar, preserving its vanishing under every completion substitution.
Lemma 8. Fix a partial set P P P and a completion Z = ( z 1 , … , z q ) Z=(z_1,\ldots,z_q) Z = ( z 1 , … , z q ) occupying the prescribed slots. For every failure set F ⊆ ( P ∪ Z ) ∩ V F\subseteq(P\cup Z)\cap V F ⊆ ( P ∪ Z ) ∩ V with ∣ F ∣ ≤ k |F|\le k ∣ F ∣ ≤ k , let I = F ∩ P I=F\cap P I = F ∩ P and J = { j ∈ [ q ] V : z j ∈ F } J=\{j\in[q]_V:z_j\in F\} J = { j ∈ [ q ] V : z j ∈ F } , so F = I ∪ { z j : j ∈ J } F=I\cup\{z_j:j\in J\} F = I ∪ { z j : j ∈ J } . Then
Δ P , I , J ∣ Z ≢ 0 ⟺ rank M ( ( P ∖ I ) ∪ ( Z ∖ J ) ) = r , (13) \Delta_{P,I,J}\mid Z\not\equiv0\Longleftrightarrow\operatorname{rank}_{M}\bigl((P\setminus I)\cup(Z\setminus J)\bigr)=r, \tag*{(13)} Δ P , I , J ∣ Z ≡ 0 ⟺ rank M ( ( P ∖ I ) ∪ ( Z ∖ J ) ) = r , (13) where Z ∖ J Z\setminus J Z ∖ J denotes deletion of the elements occupying slots in J J J .
Proof. If δ I = 0 \delta_I=0 δ I = 0 , both sides hold. Assume that δ = δ I > 0 \delta=\delta_I>0 δ = δ I > 0 and write K = [ q ] ∖ J K=[q]\setminus J K = [ q ] ∖ J . By (10), each substituted filtered column is a linear combination of columns indexed by K K K . If the surviving past and future columns have rank less than r r r , every r × r r\times r r × r determinant formed from their span vanishes, so Δ P , I , J ∣ Z = 0 \Delta_{P,I,J}\mid Z=0 Δ P , I , J ∣ Z = 0 . In particular, if fewer than δ \delta δ future columns survive, they cannot fill the rank deficiency, and the determinant vanishes. This includes an empty completion when the surviving past set does not span.
For the converse, group the multilinear determinant expansion by the δ \delta δ distinct future columns it uses. Equivalently, apply the Cauchy–Binet identity to the filtered-column matrix. For L = { ℓ 1 < ⋯ < ℓ δ } ⊆ K L=\{\ell_1<\cdots<\ell_\delta\}\subseteq K L = { ℓ 1 < ⋯ < ℓ δ } ⊆ K , the expansion is
Δ P , I , J ∣ Z = ∑ L ⊆ K ∣ L ∣ = δ det [ A I ∣ a z ℓ 1 ∣ ⋯ ∣ a z ℓ δ ] ( ∏ j ∈ L u j Fltr J ( T j ) ) ∏ 1 ≤ a < b ≤ δ ( T ℓ b − T ℓ a ) . (14) \Delta_{P,I,J}\mid Z=
\sum_{\substack{L\subseteq K\\|L|=\delta}}
\det[A_I\mid a_{z_{\ell_1}}\mid\cdots\mid a_{z_{\ell_\delta}}]
\left(\prod_{j\in L}u_j\operatorname{Fltr}_J(T_j)\right)
\prod_{1\le a<b\le\delta}(T_{\ell_b}-T_{\ell_a}). \tag*{(14)} Δ P , I , J ∣ Z = L ⊆ K ∣ L ∣ = δ ∑ det [ A I ∣ a z ℓ 1 ∣ ⋯ ∣ a z ℓ δ ] j ∈ L ∏ u j Fltr J ( T j ) 1 ≤ a < b ≤ δ ∏ ( T ℓ b − T ℓ a ) . (14) The last product is the Vandermonde determinant det [ T ℓ a h ] 1 ≤ a ≤ δ , 0 ≤ h < δ \det[T_{\ell_a}^{h}]_{1\le a\le\delta,0\le h<\delta} det [ T ℓ a h ] 1 ≤ a ≤ δ , 0 ≤ h < δ . If the survivors have rank r r r , some subset L L L extends the basis columns of A I A_I A I to a full basis, making its input-column determinant nonzero. Every filter factor and Vandermonde factor in that term is also a nonzero polynomial. Moreover, distinct subsets L L L have distinct monomials ∏ j ∈ L u j \prod_{j\in L}u_j ∏ j ∈ L u j , so these terms cannot cancel. The expansion is therefore nonzero, proving the equivalence over every field. □ \square □
To require robustness against all allowed failures with one common completion, multiply the tests in the same polynomial ring:
G P = ∏ I ⊆ P ∩ V , J ⊆ [ q ] V ∣ I ∣ + ∣ J ∣ ≤ k Δ P , I , J ∈ R p , q . (15) G_P=\prod_{\substack{I\subseteq P\cap V,\ J\subseteq[q]_V\\|I|+|J|\le k}}\Delta_{P,I,J}\in\mathcal{R}_{p,q}. \tag*{(15)} G P = I ⊆ P ∩ V , J ⊆ [ q ] V ∣ I ∣ + ∣ J ∣ ≤ k ∏ Δ P , I , J ∈ R p , q . (15)
Sharing the moment and tag variables ensures that every factor is interpreted using the same completion substitution.
Lemma 9. For every future completion Z Z Z with the prescribed safe and vulnerable counts, G P ∣ Z ≢ 0 G_P\mid Z\not\equiv0 G P ∣ Z ≡ 0 if and only if P ∪ Z P\cup Z P ∪ Z survives every allowed failure of size at most k k k .
Proof. The sets P P P and Z Z Z lie in disjoint processed and unprocessed portions of the ground set. Each allowed failure therefore decomposes uniquely into failed
past elements I ⊆ P ∩ V I \subseteq P \cap V I ⊆ P ∩ V and failed future slots J ⊆ [ q ] V J \subseteq[q]_V J ⊆ [ q ] V with ∣ I ∣ + ∣ J ∣ ≤ k |I| + |J| \leq k ∣ I ∣ + ∣ J ∣ ≤ k . Conversely, every pair in (15) defines such a failure. Since ev Z \operatorname{ev}_Z ev Z is an algebra homomorphism, G P ∣ Z = ∏ I , J ( Δ P , I , J ∣ Z ) G_P|_Z = \prod_{I,J}(\Delta_{P,I,J}|_Z) G P ∣ Z = ∏ I , J ( Δ P , I , J ∣ Z ) over these pairs. The target polynomial ring is an integral domain, so this product is nonzero exactly when every factor is nonzero. Lemma 8 identifies this condition with full rank after every allowed failure. □ \square □
The basis witnessing full rank may depend on the failure pattern, but the completion set Z Z Z is common to all patterns. This is the condition needed to compress partial solutions: choosing separate representatives for separate failures would not guarantee a single retained partial solution that works with Z Z Z throughout.
Lemma 10. Fix target counts ( s , s V ) (s,s_V) ( s , s V ) and a state ( a S , a V , p ) (a_S,a_V,p) ( a S , a V , p ) . Let P \mathcal{P} P be a finite family of partial sets in that state. Express their polynomials G P G_P G P in a common monomial basis and retain a cost-ordered linear basis of the coefficient vectors. The resulting subfamily P ^ \widehat{\mathcal{P}} P has size at most the dimension of the coefficient space. For every P ∈ P P \in\mathcal{P} P ∈ P and every future completion Z Z Z with the prescribed counts, if P ∪ Z P \cup Z P ∪ Z is feasible, then some P ′ ∈ P ^ P' \in\widehat{\mathcal{P}} P ′ ∈ P satisfies w ( P ′ ) ≤ w ( P ) w(P') \leq w(P) w ( P ′ ) ≤ w ( P ) and P ′ ∪ Z P' \cup Z P ′ ∪ Z is feasible.
Proof. All partial sets in the state use the same ring R p , q \mathcal{R}_{p,q} R p , q . Choose a finite monomial basis containing every monomial in their polynomials and identify each polynomial with its coefficient vector. Fix a completion Z Z Z for which P ∪ Z P \cup Z P ∪ Z is feasible. Its slot assignment is common to the state, so ev Z \operatorname{ev}_Z ev Z defines one F \mathbb{F} F -linear map from this coefficient space to the target polynomial ring, viewed as an F \mathbb{F} F -vector space. By Lemma 9 , this map is nonzero on the vector of G P G_P G P . Lemma 6 gives a retained set P ′ P' P ′ with w ( P ′ ) ≤ w ( P ) w(P') \leq w(P) w ( P ′ ) ≤ w ( P ) and G P ′ ∣ Z ≢ 0 G_{P'}|_Z \not\equiv0 G P ′ ∣ Z ≡ 0 . Lemma 9 then gives feasibility of P ′ ∪ Z P' \cup Z P ′ ∪ Z . The size bound follows from linear independence of the retained vectors. □ \square □
We can now process the ground set while applying this compression after each transition. The degree bound on the obstruction polynomials controls the number of retained partial sets.
Dynamic program and running time
The coefficient representatives let us compress after each take-or-skip transition. We first describe the algorithm and show that it preserves a cheapest partial selection for every successful completion. We then bound the number of shared variables, the degree of the certificates, and the resulting coefficient dimension. These bounds control both the number of retained selections and the work needed to compute them.
Theorem 4. Weighted Nonuniform Fault-Tolerant Basis on an explicitly represented rank-r r r linear matroid is solvable deterministically in 2 O ( k ( r + k ) log ( r + 1 ) ) n O ( 1 ) 2^{O(k(r+k)\log(r+1))n^{O(1)}} 2 O ( k ( r + k ) l o g ( r + 1 )) n O ( 1 ) field operations, apart from polynomial-time processing of the input representation. Over standard finite-field encodings and over the rationals, the algorithm has f ( r , k ) poly ( L i n ) f(r,k)\operatorname{poly}(L_{\mathrm{in}}) f ( r , k ) poly ( L in ) bit complexity for a computable function f f f .
Proof. For r = 0 r = 0 r = 0 , return the empty set. For k = 0 k = 0 k = 0 , compute a minimum-cost basis by the weighted matroid greedy algorithm. Assume henceforth that r , k ≥ 1 r, k \ge1 r , k ≥ 1 . By Lemma 1, every feasible instance has an optimum of size at most b = ( k + 1 ) r b = (k + 1)r b = ( k + 1 ) r .
States and initialization. Enumerate all target pairs ( s , s V ) (s, s_V) ( s , s V ) with 0 ≤ s V ≤ s ≤ b 0 \le s_V \le s \le b 0 ≤ s V ≤ s ≤ b . For a fixed pair, process a ground-set order e 1 , … , e n e_1,\ldots,e_n e 1 , … , e n , maintaining a retained family in every state ( a S , a V , p ) (a_S, a_V, p) ( a S , a V , p ) with 0 ≤ a S ≤ s − s V 0 \le a_S \le s - s_V 0 ≤ a S ≤ s − s V , 0 ≤ a V ≤ s V 0 \le a_V \le s_V 0 ≤ a V ≤ s V and 0 ≤ p ≤ r 0 \le p \le r 0 ≤ p ≤ r . A retained set in state ( a S , a V , p ) (a_S, a_V, p) ( a S , a V , p ) contains exactly a S a_S a S safe and a V a_V a V vulnerable elements and has rank p p p . The remaining safe and vulnerable counts determine its future slots, as in § 4.3 . Initially, retain only ∅ \varnothing ∅ in state ( 0 , 0 , 0 ) (0, 0, 0) ( 0 , 0 , 0 ) .
Transitions and compression. When processing an element e e e , generate the skip successor P P P from each retained set P P P . Also generate P ∪ { e } P \cup\{e\} P ∪ { e } if its type counts respect the target: a safe element may be taken if a S < s − s V a_S < s - s_V a S < s − s V and a vulnerable element if a V < s V a_V < s_V a V < s V . Compute each successor’s actual rank, place it in the corresponding state and compress every candidate family by Lemma 10 . Within a compression, all coefficient vectors use the same variables and monomial basis.
Terminal test and output. At the final prefix, inspect the states with ( a S , a V ) = ( s − s V , s V ) (a_S, a_V) = (s - s_V, s_V) ( a S , a V ) = ( s − s V , s V ) and accept a retained set exactly when it survives every vulnerable failure of size at most k k k . This is checked by enumerating the failures and computing survivor ranks. Equivalently, these states have q = 0 q = 0 q = 0 , so the only completion is ∅ \varnothing ∅ and its substitution sends all moment coordinates to zero. By Lemma 9 , acceptance is therefore equivalent to G P ( 0 ) ≠ 0 G_P(0) \ne0 G P ( 0 ) = 0 ; formal nonvanishing of G P G_P G P alone is insufficient. Return a cheapest accepted set over all target pairs, or report infeasibility if none is accepted. The selected sets or suitable predecessor information allow reconstruction of the solution.
Correctness invariant. Fix a target pair ( s , s V ) (s, s_V) ( s , s V ) . For every processed prefix E j = { e 1 , … , e j } E_j = \{e_1,\ldots,e_j\} E j = { e 1 , … , e j } , we maintain the following property. If P ⊆ E j P \subseteq E_j P ⊆ E j and Z ⊆ E ∖ E j Z \subseteq E \setminus E_j Z ⊆ E ∖ E j meet the target counts,
∣ P ∩ S ∣ + ∣ Z ∩ S ∣ = s − s V , ∣ P ∩ V ∣ + ∣ Z ∩ V ∣ = s V , (16) |P \cap S| + |Z \cap S| = s - s_V, \qquad|P \cap V| + |Z \cap V| = s_V, \tag*{(16)} ∣ P ∩ S ∣ + ∣ Z ∩ S ∣ = s − s V , ∣ P ∩ V ∣ + ∣ Z ∩ V ∣ = s V , (16)
and P ∪ Z P \cup Z P ∪ Z is feasible, then there is a retained set P ′ ⊆ E j P' \subseteq E_j P ′ ⊆ E j such that
∣ P ′ ∩ S ∣ = ∣ P ∩ S ∣ , ∣ P ′ ∩ V ∣ = ∣ P ∩ V ∣ , |P' \cap S| = |P \cap S|, \qquad|P' \cap V| = |P \cap V|, ∣ P ′ ∩ S ∣ = ∣ P ∩ S ∣ , ∣ P ′ ∩ V ∣ = ∣ P ∩ V ∣ ,
w ( P ′ ) ≤ w ( P ) , P ′ ∪ Z is feasible . w(P') \le w(P), \qquad P' \cup Z \text{ is feasible}. w ( P ′ ) ≤ w ( P ) , P ′ ∪ Z is feasible .
The ranks of P P P and P ′ P' P ′ need not agree. Rank is used to group candidates for each individual compression. The invariant across transitions preserves counts, cost, and the successful completion. This distinction lets us place each successor in its actual rank state, without assuming that adding the next element changes the ranks of two partial sets in the same way.
The invariant holds at the empty prefix. Suppose that it holds before processing e = e j e = e_j e = e j , and fix P , Z P, Z P , Z for the new prefix.
Skip case. If e ∉ P e \notin P e ∈ / P , apply the previous invariant to P P P and Z Z Z . It yields a retained set P ^ \widehat{P} P of the same safe and vulnerable counts, of cost at most w ( P ) w(P) w ( P ) , for which P ^ ∪ Z \widehat{P}\cup Z P ∪ Z is feasible. Its skip successor is a candidate with the required counts and successful completion Z Z Z .
Take case. If e ∈ P e\in P e ∈ P , apply the previous invariant to P ∖ { e } P\setminus\{e\} P ∖ { e } and completion Z ∪ { e } Z\cup\{e\} Z ∪ { e } . This gives a retained set P ^ \widehat{P} P with the same counts as P ∖ { e } P\setminus\{e\} P ∖ { e } , with w ( P ^ ) ≤ w ( P ∖ { e } ) w(\widehat{P})\leq w(P\setminus\{e\}) w ( P ) ≤ w ( P ∖ { e }) , and with P ^ ∪ Z ∪ { e } \widehat{P}\cup Z\cup\{e\} P ∪ Z ∪ { e } feasible. Taking e e e is permitted because the resulting counts equal those of P P P . The take successor P ^ ∪ { e } \widehat{P}\cup\{e\} P ∪ { e } has cost at most w ( P ) w(P) w ( P ) and successful completion Z Z Z .
In either case, the candidate is assigned to its actual rank state. Lemma 10 then preserves a candidate in that state of no greater cost that works with the same Z Z Z . Its safe and vulnerable counts are unchanged. This proves the invariant.
At the final prefix, apply the invariant to an optimum with the fixed target counts and Z = ∅ Z=\varnothing Z = ∅ . It gives a retained feasible set of no greater cost, which the terminal test accepts. Only feasible sets are accepted. By Lemma 1, some enumerated target pair contains a global optimum, so choosing the cheapest accepted set over all pairs proves optimality. If no set is accepted, no feasible solution exists.
Bounding the coefficient dimension. We track three quantities: the number N N N of variables, an upper bound D D D on the total degree, and the dimension H H H of the polynomials of degree at most D D D . The last quantity bounds the size of every retained family within a state.
Number of variables. For a state with d = r − p d=r-p d = r − p and q = s − a S − a V q=s-a_S-a_V q = s − a S − a V , the shared ring contains d + k d+k d + k moment vectors, each with r r r coordinates, and q q q slot tags. Thus
N = r ( d + k ) + q ≤ r ( r + k ) + ( k + 1 ) r = O ( r ( r + k ) ) . N=r(d+k)+q\leq r(r+k)+(k+1)r=O(r(r+k)). N = r ( d + k ) + q ≤ r ( r + k ) + ( k + 1 ) r = O ( r ( r + k )) .
The auxiliary variables u j u_j u j are used only after substituting a completion, so they do not contribute to the certificate’s coefficient dimension.
Degree of the product. We first bound the number of determinant factors and then the degree of each factor. Each failure pair selects at most k k k positions among the a V + q V = s V ≤ b a_V+q_V=s_V\leq b a V + q V = s V ≤ b vulnerable past elements and future slots. Hence the number of factors in G P G_P G P is at most
∑ j = 0 k ( s V j ) ≤ N f a i l : = ∑ j = 0 k ( b j ) ≤ ( 2 e r ) k . (17) \sum_{j=0}^{k}\binom{s_V}{j}\leq N_{\mathrm{fail}}:=\sum_{j=0}^{k}\binom{b}{j}\leq(2er)^k. \tag*{(17)} j = 0 ∑ k ( j s V ) ≤ N fail := j = 0 ∑ k ( j b ) ≤ ( 2 er ) k . (17)
For the last inequality, put t = k / b ≤ 1 t=k/b\leq1 t = k / b ≤ 1 . Since t j ≥ t k t^j\geq t^k t j ≥ t k for 0 ≤ j ≤ k 0\leq j\leq k 0 ≤ j ≤ k , the binomial theorem gives
∑ j = 0 k ( b j ) ≤ t − k ( 1 + t ) b ≤ ( e b / k ) k ≤ ( 2 e r ) k , (18) \sum_{j=0}^{k}\binom{b}{j}\leq t^{-k}(1+t)^b\leq(eb/k)^k\leq(2er)^k, \tag*{(18)} j = 0 ∑ k ( j b ) ≤ t − k ( 1 + t ) b ≤ ( e b / k ) k ≤ ( 2 er ) k , (18)
using ( 1 + t ) b ≤ e b t = e k (1+t)^b\leq e^{bt}=e^k ( 1 + t ) b ≤ e b t = e k and b / k ≤ 2 r b/k\leq2r b / k ≤ 2 r .
The coefficient c J , ν c_{J,\nu} c J , ν has tag degree ∣ J ∣ − ν |J|-\nu ∣ J ∣ − ν , so an entry of Y J , h Y_{J,h} Y J , h has total degree at most ∣ J ∣ + 1 |J|+1 ∣ J ∣ + 1 . A determinant factor has δ I \delta_I δ I filtered columns and constant past-basis columns. Its degree is at most δ I ( ∣ J ∣ + 1 ) ≤ r ( k + 1 ) \delta_I(|J|+1)\leq r(k+1) δ I ( ∣ J ∣ + 1 ) ≤ r ( k + 1 ) . Consequently, G P G_P G P has total degree at most D = r ( k + 1 ) N f a i l D=r(k+1)N_{\mathrm{fail}} D = r ( k + 1 ) N fail .
Dimension of the coefficient space. Use one fixed ordering of all monomials in the state’s N N N variables of total degree at most D D D . Every certificate in the state has its coefficient vector in this space, whose dimension is
H = ( N + D N ) ≤ ( D + 1 ) N , log H = O ( k r ( r + k ) log ( r + 1 ) ) . (19) H = \binom{N + D}{N} \le(D + 1)^N,\qquad\log H = \mathcal{O}(kr(r + k)\log(r + 1)). \tag*{(19)} H = ( N N + D ) ≤ ( D + 1 ) N , log H = O ( k r ( r + k ) log ( r + 1 )) . (19)
The inequality holds because each of the N N N exponents lies between 0 0 0 and D D D . Moreover, D ≤ r ( k + 1 ) ( 2 e r ) k D \le r(k + 1)(2er)^k D ≤ r ( k + 1 ) ( 2 er ) k , and hence
log ( D + 1 ) = O ( log r + log ( k + 1 ) + k log ( r + 1 ) ) = O ( k log ( r + 1 ) ) , \log(D + 1) = \mathcal{O}\bigl(\log r + \log(k + 1) + k\log(r + 1)\bigr) = \mathcal{O}\bigl(k\log(r + 1)\bigr), log ( D + 1 ) = O ( log r + log ( k + 1 ) + k log ( r + 1 ) ) = O ( k log ( r + 1 ) ) ,
using r , k ≥ 1 r, k \ge1 r , k ≥ 1 . Multiplying by the bound on N N N proves the stated bound on log H \log H log H . For the overall running time, use the maximum of these dimension bounds over all states.
Constructing and compressing the certificates. For each candidate P P P , enumerate its at most N f a i l N_{\mathrm{fail}} N fail failure pairs. Obtain each required A I A_I A I by exact linear algebra on the at most b b b input columns of P ∖ I P \setminus I P ∖ I . Compute the filter coefficients by multiplying the linear factors, form the filtered moments and construct the determinant factors. Store polynomials as dense coefficient vectors in a fixed ordering of the H H H monomials, including zeros for absent monomials. Every partial product has total degree at most D D D . Naive polynomial multiplication uses H O ( 1 ) H^{\mathcal{O}(1)} H O ( 1 ) field operations, and each determinant has at most r ! r! r ! permutation terms. Constructing G P G_P G P therefore uses N f a i l r ! poly ( b , r , k ) H O ( 1 ) N_{\mathrm{fail}}r!\,\operatorname{poly}(b,r,k)H^{\mathcal{O}(1)} N fail r ! poly ( b , r , k ) H O ( 1 ) field operations, with all coefficients computed exactly.
Total field-operation count. There are O ( b 2 ) \mathcal{O}(b^2) O ( b 2 ) target pairs and O ( b 2 r ) \mathcal{O}(b^{2r}) O ( b 2 r ) states per pair. Each state retains at most H H H sets, each generating at most two successors. Thus the number of candidates per prefix is polynomial in b b b , r r r , H H H . Cost sorting and Gaussian elimination on their coefficient vectors have polynomial overhead in these quantities. Terminal verification uses at most N f a i l N_{\mathrm{fail}} N fail rank tests per candidate. All factors, including N f a i l N_{\mathrm{fail}} N fail and r ! r! r ! , are absorbed by 2 O ( k r ( r + k ) log ( r + 1 ) ) 2^{\mathcal{O}(kr(r+k)\log(r+1))} 2 O ( k r ( r + k ) l o g ( r + 1 )) . Processing the n n n prefixes gives the claimed field-operation bound.
Exact cost additions, comparisons and sorting have polynomial overhead in the cost encoding and the number of candidates.
Bit complexity. It remains to justify the bit-complexity claim. Over Q \mathbb{Q} Q , retain independent original rows and choose every A I A_I A I from original columns. Suppose the resulting input entries have at most L L L bits. A partial set contains at most b b b columns and hence at most r b rb r b entries. The product of their denominators gives a common denominator with O ( r b L ) \mathcal{O}(rbL) O ( r b L ) bits. Each determinant factor has degree at most r r r in the input entries. Since G P G_P G P has at most N f a i l N_{\mathrm{fail}} N fail factors, every coefficient has a denominator dividing the r N f a i l rN_{\mathrm{fail}} r N fail th power of this common denominator, whose bit length is O ( r 2 b N f a i l L ) \mathcal{O}(r^2bN_{\mathrm{fail}}L) O ( r 2 b N fail L ) . The number of terms contributing to a coefficient, their degrees in the input entries and the integer coefficients introduced by the filters are bounded by functions of r , k r,k r , k . Both numerator and denominator lengths are therefore at most f 1 ( r , k ) ( L + 1 ) f_1(r,k)(L+1) f 1 ( r , k ) ( L + 1 ) for a computable function f 1 f_1 f 1 .
Clear denominators in each coefficient vector before cost-ordered basis selection. Scaling a vector by a nonzero scalar preserves every dependence test. The elimination matrices have at most H H H columns, so standard determinant bounds show that fraction-free Gaussian elimination has intermediate bit lengths bounded by a parameter-dependent multiple of L + 1 L+1 L + 1 . Input rank computations and cost comparisons also admit exact polynomial-time implementations. Together with the operation bound, this gives f ( r , k ) poly ( L i n ) f(r,k)\operatorname{poly}(L_{\mathrm{in}}) f ( r , k ) poly ( L in ) bit complexity over Q \mathbb{Q} Q . For a finite field in a standard exact encoding, each field operation has polynomial bit complexity in the field encoding length, giving the same conclusion. No bit-complexity claim is made for an unspecified black-box field representation.
Fixed finite fields
Over a fixed finite field F Q \mathbb{F}_Q F Q , the number of possible column directions is bounded in terms of the rank. This gives a simpler way to obtain a small ground set: within each direction, we retain only a few inexpensive elements. We can then search this reduced set using the small-solution bound from § 3 .
Two nonloop elements are parallel if their columns are nonzero scalar multiples of one another. A parallel class therefore represents one one-dimensional subspace of F Q r \mathbb{F}_Q^r F Q r , which we call its direction . For spanning, the contribution of a class depends only on whether at least one of its selected elements survives. One selected safe element guarantees this; if all selected elements in the class are vulnerable, then k + 1 k+1 k + 1 selected elements suffice to guarantee a survivor under every allowed failure. Selecting more cannot provide further protection.
Accordingly, we retain a cheapest safe element and up to k + 1 k+1 k + 1 cheapest vulnerable elements per class. These are available choices, not elements that every solution must select. In particular, a solution may select fewer vulnerable elements from a class and rely on other directions if all of them fail. We keep both safety types because their costs may differ, and we do not know which choice an optimum makes.
Theorem 5. Let M M M be a rank-r r r matroid represented over F Q \mathbb{F}_Q F Q , where Q Q Q is the field size. Weighted Nonuniform Fault-Tolerant Basis can be reduced, without changing the optimum, to at most ( k + 2 ) ( Q r − 1 ) / ( Q − 1 ) (k+2)(Q^r-1)/(Q-1) ( k + 2 ) ( Q r − 1 ) / ( Q − 1 ) nonloop elements. Consequently, for every fixed Q Q Q , the problem is solvable in 2 O ( k r 2 + k r log ( k + 2 ) ) n O ( 1 ) 2^{O(kr^2+kr\log(k+2))}n^{O(1)} 2 O ( k r 2 + k r l o g ( k + 2 )) n O ( 1 ) time.
Proof. Constructing the reduced ground set. Delete all loops, since they contribute nothing to spanning and removing them cannot increase the cost. Retain r r r independent original rows of the representation. Divide each nonzero column by its first nonzero coordinate and group identical normalized columns into parallel classes. In every class, retain a cheapest safe element if one exists and the k + 1 k+1 k + 1 cheapest vulnerable elements, or all vulnerable elements if fewer are present. Let W W W be the union of these retained elements. We show that every feasible set can be replaced by a feasible subset of W W W of no greater cost.
A class with a selected safe element. First consider a class containing a selected safe element. Keep one such element and delete all other selected elements in the class. Under every allowed failure, the retained safe element survives and spans the direction of all deleted columns. Moreover, every allowed failure of the resulting set is also allowed for the original set. Thus deletion preserves the survivor span and feasibility, and nonnegative costs prevent any cost increase. Replace the remaining safe element by a cheapest safe element in the class. The replacement is safe and has the same direction, so it again preserves every survivor span without increasing cost.
A class with only selected vulnerable elements. Now consider a class with no selected safe element. If more than k + 1 k + 1 k + 1 vulnerable elements are selected, keep any k + 1 k + 1 k + 1 and delete the others. Every allowed failure leaves at least one retained element in the class, so its direction remains present in the survivor span. Deleting the remaining columns therefore preserves feasibility and cannot increase cost. Let t ≤ k + 1 t \le k + 1 t ≤ k + 1 be the number of selected elements left in the class. Replace them by the t t t cheapest vulnerable elements of the class, all belonging to W W W . Fix a bijection between the old and new selected elements in this class and leave selected elements outside it fixed. The bijection preserves vulnerability and direction. Pulling back any allowed failure of the new set gives an allowed failure of the old set of the same cardinality, and the corresponding survivors span the same directions. Hence the replacement preserves feasibility and does not increase cost.
Applying these operations to all classes yields a feasible subset of W W W of no greater cost. The construction retains at least one element of every nonloop parallel class, so W W W spans the original matroid and rank ( M ∣ W ) = r \operatorname{rank}(M|W) = r rank ( M ∣ W ) = r . Thus restricting the ground set to W W W preserves the target rank. Conversely, every feasible set in the restriction is feasible in the original instance, since its columns, costs, safety types, and target rank are unchanged. The optimum, including infeasibility, is therefore preserved.
Bounding the number of retained elements. There are Q r − 1 Q^r - 1 Q r − 1 nonzero vectors in F Q \mathbb{F}_Q F Q , and each one-dimensional subspace contains exactly Q − 1 Q - 1 Q − 1 of them. Hence there are ( Q r − 1 ) / ( Q − 1 ) (Q^r - 1)/(Q - 1) ( Q r − 1 ) / ( Q − 1 ) possible directions. Since at most one safe element and k + 1 k + 1 k + 1 vulnerable elements are retained per direction,
∣ W ∣ ≤ ( k + 2 ) Q r − 1 Q − 1 . |W| \le(k + 2)\frac{Q^r - 1}{Q - 1}. ∣ W ∣ ≤ ( k + 2 ) Q − 1 Q r − 1 .
This reduction is valid for every finite field. Fixing Q Q Q makes the number of directions single-exponential in r r r , which yields the running-time bound below.
Searching the reduced ground set. For r = 0 r = 0 r = 0 , return the empty set; for k = 0 k = 0 k = 0 , compute a minimum-cost basis. Assume henceforth that r , k ≥ 1 r, k \ge1 r , k ≥ 1 . By the earlier sparsification lemma, a feasible reduced instance has an optimum of size at most b = ( k + 1 ) r b = (k + 1)r b = ( k + 1 ) r . Enumerate all subsets B ⊆ W B \subseteq W B ⊆ W with ∣ B ∣ ≤ b |B| \le b ∣ B ∣ ≤ b . For each, enumerate all F ⊆ B ∩ V F \subseteq B \cap V F ⊆ B ∩ V with ∣ F ∣ ≤ k |F| \le k ∣ F ∣ ≤ k and test whether rank M ( B ∖ F ) = r \operatorname{rank}_M(B \setminus F) = r rank M ( B ∖ F ) = r . Return a cheapest feasible candidate, or report infeasibility if none exists.
Running time. For fixed Q Q Q , we have log ( ∣ W ∣ + 1 ) = O ( r + log ( k + 2 ) ) \log(|W| + 1) = O(r + \log(k + 2)) log ( ∣ W ∣ + 1 ) = O ( r + log ( k + 2 )) . The number of candidates is at most
∑ j = 0 b ( ∣ W ∣ j ) ≤ ∑ j = 0 b ∣ W ∣ j ≤ ( ∣ W ∣ + 1 ) b + 1 . (20) \sum_{j=0}^{b} \binom{|W|}{j} \le\sum_{j=0}^{b} |W|^j \le(|W| + 1)^{b+1}. \tag*{(20)} j = 0 ∑ b ( j ∣ W ∣ ) ≤ j = 0 ∑ b ∣ W ∣ j ≤ ( ∣ W ∣ + 1 ) b + 1 . (20)
Each candidate has at most N f a i l ≤ ( 2 e r ) k N_{\mathrm{fail}} \le(2er)^k N fail ≤ ( 2 er ) k failure sets, by (17) , and each survivor rank requires a polynomial number of field operations in b , r b,r b , r . Since b ≤ 2 k r b \le2kr b ≤ 2 k r , the logarithm of the candidate bound is
O ( ( b + 1 ) log ( ∣ W ∣ + 1 ) ) = O ( k r 2 + k r log ( k + 2 ) ) . O((b + 1)\log(|W| + 1)) = O(kr^2 + kr\log(k + 2)). O (( b + 1 ) log ( ∣ W ∣ + 1 )) = O ( k r 2 + k r log ( k + 2 )) .
The failure tests contribute at most O ( k log ( r + 1 ) ) O(k\log(r + 1)) O ( k log ( r + 1 )) to the exponent, which is absorbed by this bound. We therefore obtain 2 O ( k r 2 + k r log ( k + 2 ) ) n O ( 1 ) 2^{O(kr^2+kr\log(k+2))}n^{O(1)} 2 O ( k r 2 + k r l o g ( k + 2 )) n O ( 1 ) time for fixed Q Q Q . The constants may depend on Q Q Q . Normalizing and grouping columns and sorting elements by cost take polynomially many operations. Reading the encoded input and accounting for the bit lengths of costs add polynomial overhead under the conventions of § 2 . □ \square □
In particular, every fixed failure budget gives a quadratic exponent in the rank; the two-failure case is one such specialization.
Corollary 2. For every fixed finite field and every fixed failure budget k ≥ 0 k \ge0 k ≥ 0 , Weighted Nonuniform Fault-Tolerant Basis is solvable in 2 O ( r 2 ) n O ( 1 ) 2^{O(r^2)}n^{O(1)} 2 O ( r 2 ) n O ( 1 ) operations.
Proof. For r , k ≥ 1 r,k \ge1 r , k ≥ 1 with k k k fixed, Theorem 5 has exponent O ( k r 2 + k r log ( k + 2 ) ) = O ( r 2 ) O(kr^2+kr\log(k+2)) = O(r^2) O ( k r 2 + k r log ( k + 2 )) = O ( r 2 ) . The hidden constant may depend on the field and on k k k . For rank zero, the empty set is optimal; for k = 0 k = 0 k = 0 , a minimum-cost basis is optimal and can be found in polynomially many operations. □ \square □
Explicit scenarios: a parameterization boundary
The failure model now changes. Instead of requiring survival after every deletion of at most k k k vulnerable elements, we are given an explicit list of scenarios F 1 , … , F m ⊆ E F_1,\ldots,F_m \subseteq E F 1 , … , F m ⊆ E . A selected set must span after each listed scenario is applied separately. The list specifies the required failures; we do not additionally require survival after unions of scenarios. This is the bulk-robust spanning model.
Two different measures of the list lead to different parameterized complexity results. The maximum scenario size measures how many elements can fail in any one listed event; the list length m m m measures how many such events must be considered. We prove hardness for rank plus maximum scenario size, even when every scenario has size two. In contrast, rank plus list length yields an FPT algorithm for oracle matroids and a 2 O ( r m ) n O ( 1 ) 2^{O(rm)}n^{O(1)} 2 O ( r m ) n O ( 1 ) field-operation algorithm for represented matroids when m ≥ 1 m \ge1 m ≥ 1 . The positive results will reuse the flat-avoidance representatives of § 3 and the simultaneous-spanning lemma of § 4.2 .
Weighted Explicit-Scenario Fault-Tolerant Basis. Given a rank-r r r matroid M M M on E E E , nonnegative integer costs w w w and scenarios F 1 , … , F m ⊆ E F_1,\ldots,F_m \subseteq E F 1 , … , F m ⊆ E , find a minimum-cost B ⊆ E B \subseteq E B ⊆ E with rank M ( B ) = r \operatorname{rank}_M(B)=r rank M ( B ) = r and rank M ( B ∖ F i ) = r \operatorname{rank}_M(B\setminus F_i)=r rank M ( B ∖ F i ) = r for all i ∈ [ m ] i\in[m] i ∈ [ m ] , or report infeasibility.
Explicit-Scenario Size-Budget Decision. Given M M M , the scenarios and a size budget β \beta β , decide whether a set satisfying the same rank conditions has size at most β \beta β .
The no-failure constraint can equivalently be viewed as the implicit scenario F 0 = ∅ F_0=\varnothing F 0 = ∅ , which we do not count in m m m . When m ≥ 1 m\ge1 m ≥ 1 , it already follows from any listed scenario constraint by rank monotonicity. When m = 0 m=0 m = 0 , the problem is minimum-weight spanning and is solved by a minimum-weight basis. Scenarios may contain elements outside the selected set; such elements have no effect on its surviving rank. The size-budget formulation is the decision version with unit costs: it asks whether the optimum cardinality is at most β \beta β . We use this restricted formulation for the hardness result and allow arbitrary nonnegative costs in the algorithms.
Hardness for two-element scenarios
The reduction encodes an independent set using failures that are graph edges. In a uniform matroid of rank r r r , a selected set of size r + 1 r+1 r + 1 tolerates a two-element scenario exactly when the scenario contains at most one selected element. Requiring this for every edge is precisely the independent-set condition.
We set r = ℓ − 1 r=\ell-1 r = ℓ − 1 , where ℓ \ell ℓ is the desired independent-set size, and impose the budget r + 1 = ℓ r+1=\ell r + 1 = ℓ . To force a feasible set within this budget to have exactly r + 1 r+1 r + 1 elements, we add a universal vertex. The resulting graph has no isolated vertices, so any selection of only r r r elements loses rank under some edge scenario. An independent set of size ℓ ≥ 2 \ell\ge2 ℓ ≥ 2 cannot use the universal vertex, so the correspondence with the original graph is preserved. The proof below treats the small exceptional instances explicitly.
Theorem 6. The explicit-scenario size-budget problem is W [ 1 ] W[1] W [ 1 ] -hard parameterized by
r + max i ∣ F i ∣ , r+\max_i |F_i|, r + i max ∣ F i ∣ , even on uniform matroids, when every listed scenario has size exactly two and the solution budget is r + 1 r+1 r + 1 .
Proof. We give a parameterized reduction from Independent Set, parameterized by the required independent-set size ℓ \ell ℓ , which is W [ 1 ] W[1] W [ 1 ] -hard [6 ] .
Exceptional instances. For ℓ = 0 \ell=0 ℓ = 0 , the source instance is a yes-instance. For ℓ = 1 \ell=1 ℓ = 1 , it is a yes-instance exactly when V ( G ) ≠ ∅ V(G)\ne\varnothing V ( G ) = ∅ . These cases can therefore be decided directly and mapped to the fixed instances below. For a yes-instance, output the uniform matroid U 1 , { a , b , c } U_{1,\{a,b,c\}} U 1 , { a , b , c } with scenarios { a , b } \{a,b\} { a , b } and { b , c } \{b,c\} { b , c } and budget two. The set { a , c } \{a,c\} { a , c } is feasible, since it retains one element after either scenario. For a no-instance, output the uniform matroid U 1 , { a , b } U_{1,\{a,b\}} U 1 , { a , b } with the single scenario { a , b } \{a,b\} { a , b } and budget two. This instance has no feasible solution, since the scenario deletes the entire ground set. Both output instances have rank one, two-element scenarios and budget r + 1 = 2 r+1=2 r + 1 = 2 .
Instances with ℓ > ∣ V ( G ) ∣ \ell>|V(G)| ℓ > ∣ V ( G ) ∣ are no-instances and are mapped to the same fixed no-instance. Henceforth, assume 2 ≤ ℓ ≤ ∣ V ( G ) ∣ 2\leq\ell\leq|V(G)| 2 ≤ ℓ ≤ ∣ V ( G ) ∣ .
The construction. Let G + G^{+} G + be obtained from G G G by adding a new vertex z z z adjacent to every vertex of G G G . Define
M = U ℓ − 1 , V ( G + ) , r = ℓ − 1. M=U_{\ell-1,V(G^{+})},\qquad r=\ell-1. M = U ℓ − 1 , V ( G + ) , r = ℓ − 1.
Thus, a set spans M M M if and only if it contains at least r r r elements. For each edge u v ∈ E ( G + ) uv\in E(G^{+}) uv ∈ E ( G + ) , include the scenario { u , v } \{u,v\} { u , v } and set the solution budget to r + 1 = ℓ r+1=\ell r + 1 = ℓ . We prove that ( G , ℓ ) (G,\ell) ( G , ℓ ) is a yes-instance if and only if the resulting instance admits a feasible solution.
An independent set gives a feasible selection. Suppose first that G G G contains an independent set I I I of size ℓ \ell ℓ . Since ∣ I ∣ = r + 1 |I|=r+1 ∣ I ∣ = r + 1 , the set I I I spans M M M and satisfies the budget. Moreover, I I I is independent in G + G^{+} G + , so every listed scenario F F F contains at most one element of I I I . Consequently,
∣ I ∖ F ∣ ≥ ∣ I ∣ − 1 = r , |I\setminus F|\geq|I|-1=r, ∣ I ∖ F ∣ ≥ ∣ I ∣ − 1 = r ,
and hence I ∖ F I\setminus F I ∖ F spans M M M . Thus I I I is feasible.
A feasible selection gives an independent set. Conversely, let S S S be a feasible solution with ∣ S ∣ ≤ r + 1 |S|\leq r+1 ∣ S ∣ ≤ r + 1 . We first show that ∣ S ∣ = r + 1 |S|=r+1 ∣ S ∣ = r + 1 . Feasibility implies that S S S spans M M M , so ∣ S ∣ ≥ r |S|\geq r ∣ S ∣ ≥ r . If ∣ S ∣ = r |S|=r ∣ S ∣ = r , choose any x ∈ S x\in S x ∈ S , which is possible because r ≥ 1 r\geq1 r ≥ 1 . The graph G + G^{+} G + has no isolated vertices: every original vertex is adjacent to z z z , and z z z has a neighbor because ∣ V ( G ) ∣ ≥ ℓ ≥ 2 |V(G)|\geq\ell\geq2 ∣ V ( G ) ∣ ≥ ℓ ≥ 2 . Hence some listed scenario F F F contains x x x . Then
∣ S ∖ F ∣ ≤ r − 1 , |S\setminus F|\leq r-1, ∣ S ∖ F ∣ ≤ r − 1 ,
contradicting the requirement that S ∖ F S\setminus F S ∖ F span M M M . Therefore ∣ S ∣ = r + 1 = ℓ |S|=r+1=\ell ∣ S ∣ = r + 1 = ℓ .
Next, no listed scenario can be contained in S S S : if F ⊆ S F\subseteq S F ⊆ S , then
∣ S ∖ F ∣ = ∣ S ∣ − 2 = r − 1 , |S\setminus F|=|S|-2=r-1, ∣ S ∖ F ∣ = ∣ S ∣ − 2 = r − 1 ,
again contradicting feasibility. Since the listed scenarios are precisely the edges of G + G^{+} G + , the set S S S is independent in G + G^{+} G + . As z z z is adjacent to every other vertex and ∣ S ∣ = ℓ ≥ 2 |S|=\ell\geq2 ∣ S ∣ = ℓ ≥ 2 , we have z ∉ S z\notin S z ∈ / S . Hence S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) is an independent set of G G G of size ℓ \ell ℓ .
Parameter bound. The construction takes polynomial time and every scenario has size exactly two. For 2 ≤ ℓ ≤ ∣ V ( G ) ∣ 2\leq\ell\leq|V(G)| 2 ≤ ℓ ≤ ∣ V ( G ) ∣ , the output parameter is
r + max i ∣ F i ∣ = ( ℓ − 1 ) + 2 = ℓ + 1. r+\max_i |F_i|=(\ell-1)+2=\ell+1. r + i max ∣ F i ∣ = ( ℓ − 1 ) + 2 = ℓ + 1.
In the exceptional cases, the output parameter is three. Thus the reduction is parameterized and the claimed W[1 ] -hardness follows. □ \square □
An algorithm for a bounded number of scenarios
The hardness reduction uses one scenario per edge, so the list can be long even when every scenario has size two. We now bound the number m m m of scenarios together with the rank r r r , without bounding the size of an individual scenario.
The two representation models admit different algorithms. For oracle matroids, we group elements according to which scenarios delete them and apply the flat-avoidance lemma within each group. For represented matroids, we turn each scenario into a separate linear matroid and apply the simultaneous-spanning algorithm. Both constructions preserve the cost of an optimum.
Theorem 7. On independence-oracle matroids, the weighted explicit-scenario problem is fixed-parameter tractable parameterized by r + m r+m r + m . On represented linear matroids it is solvable in 2 O ( r m ) n O ( 1 ) 2^{O(rm)}n^{O(1)} 2 O ( r m ) n O ( 1 ) field operations after polynomial preprocessing of the input representation. The case m = 0 m=0 m = 0 is polynomial-time solvable.
Proof. Boundary cases and feasibility. The case r = 0 r=0 r = 0 has the empty optimum, and the case m = 0 m=0 m = 0 is minimum-weight spanning, so assume r , m ≥ 1 r,m \ge1 r , m ≥ 1 . Delete loops and compute rank M ( E ∖ F i ) \operatorname{rank}_{M}(E \setminus F_i) rank M ( E ∖ F i ) for each scenario. If one of these ranks is below r r r , even the whole ground set is infeasible, so reject. If every test succeeds, E E E itself is feasible. Thus these tests decide feasibility; the remaining task is to find a minimum-cost feasible selection. We give an oracle algorithm and then a faster algorithm for an explicit linear representation.
A small optimum for the oracle algorithm. A feasible selection contains a surviving basis for each listed scenario. Taking the union of one such basis per scenario gives a small feasible subset; nonnegative costs then give the same size bound for some optimum. To bound the size of an optimum, let B B B be a feasible set. For every i ∈ [ m ] i \in[m] i ∈ [ m ] , choose a basis I i ⊆ B ∖ F i I_i \subseteq B \setminus F_i I i ⊆ B ∖ F i of M M M , and put C = ⋃ i = 1 m I i C = \bigcup_{i=1}^{m} I_i C = ⋃ i = 1 m I i . Then C ⊆ B C \subseteq B C ⊆ B with ∣ C ∣ ≤ m r |C| \le mr ∣ C ∣ ≤ m r , and C ∖ F i C \setminus F_i C ∖ F i contains the full basis I i I_i I i for every i i i . Thus C C C is feasible. Nonnegative costs imply w ( C ) ≤ w ( B ) w(C) \le w(B) w ( C ) ≤ w ( B ) , so there is an optimum with at most
selected elements.
Grouping elements by failure signatures. In the safe/vulnerable model, an exchange preserves the safety type of the replaced element. Here we preserve its membership in every listed scenario. This ensures that the old and new elements either both fail or both survive under each scenario. For oracle matroids, define the failure signature of e ∈ E e \in E e ∈ E by
σ ( e ) = ( [ 1 ∈ F 1 ] , … , [ 1 ∈ F m ] ) ∈ { 0 , 1 } m , \sigma(e) = \bigl([1 \in F_1],\ldots,[1 \in F_m]\bigr) \in\{0,1\}^{m}, σ ( e ) = ( [ 1 ∈ F 1 ] , … , [ 1 ∈ F m ] ) ∈ { 0 , 1 } m ,
that is, for each i ∈ [ m ] i \in[m] i ∈ [ m ] ,
σ i ( e ) = { 1 if e ∈ F i , 0 if e ∉ F i . \sigma_i(e) =
\begin{cases}
1 & \text{if } e \in F_i,\\
0 & \text{if } e \notin F_i.
\end{cases} σ i ( e ) = { 1 0 if e ∈ F i , if e ∈ / F i .
A signature class consists of all elements with a fixed vector σ ( e ) \sigma(e) σ ( e ) ; there are at most 2 m 2^m 2 m such classes. For each nonempty class A A A , apply Lemma 5 to the subset A A A of the ambient matroid M M M , with t = m t=m t = m and reserve b = m r b=mr b = m r . The value t = m t=m t = m will cover all deficient survivor hyperplanes arising from the listed scenarios. The reserve ensures that a replacement can be chosen outside the other at most b − 1 b-1 b − 1 selected elements. Let W W W be the union of the resulting cores. Since there are at most 2 m 2^m 2 m signature classes,
∣ W ∣ ≤ 2 m m r ∑ j = 0 r − 1 m j . (21) |W| \le2^m mr \sum_{j=0}^{r-1} m^j. \tag*{(21)} ∣ W ∣ ≤ 2 m m r j = 0 ∑ r − 1 m j . (21)
In particular, this size depends only on r + m r+m r + m .
Exchanging an element into the core. We show that W W W contains an optimum. Let B B B be an optimum with ∣ B ∣ ≤ b |B| \le b ∣ B ∣ ≤ b , choose x ∈ B ∖ W x \in B \setminus W x ∈ B ∖ W , and put Y = B ∖ { x } Y=B\setminus\{x\} Y = B ∖ { x } . For each scenario with x ∉ F i x \notin F_i x ∈ / F i and rank ( Y ∖ F i ) < r \operatorname{rank}(Y\setminus F_i)<r rank ( Y ∖ F i ) < r , feasibility of B B B implies
rank ( Y ∖ F i ) = r − 1 , x ∉ H i : = cl M ( Y ∖ F i ) . \operatorname{rank}(Y\setminus F_i)=r-1,\qquad x\notin H_i:=\operatorname{cl}_M(Y\setminus F_i). rank ( Y ∖ F i ) = r − 1 , x ∈ / H i := cl M ( Y ∖ F i ) .
Thus the distinct deficient hyperplanes form a family of size at most m m m , and every member avoids x x x . Since ∣ Y ∣ ≤ b − 1 |Y|\le b-1 ∣ Y ∣ ≤ b − 1 , Lemma 5 applies within the signature class of x x x , with forbidden set Y Y Y . It returns y ∈ W ∖ Y y\in W\setminus Y y ∈ W ∖ Y of the same signature, with w ( y ) ≤ w ( x ) w(y)\le w(x) w ( y ) ≤ w ( x ) , outside every hyperplane in this family. The lemma also covers the case when the family is empty. Put B ′ = Y ∪ { y } B'=Y\cup\{y\} B ′ = Y ∪ { y } .
Preserving every scenario. Fix a scenario F i F_i F i . Since σ ( y ) = σ ( x ) \sigma(y)=\sigma(x) σ ( y ) = σ ( x ) , either both x x x and y y y belong to F i F_i F i or neither does. If x ∈ F i x\in F_i x ∈ F i , then B ′ ∖ F i = B ∖ F i B'\setminus F_i=B\setminus F_i B ′ ∖ F i = B ∖ F i , which spans by feasibility of B B B . Suppose now that x ∉ F i x\notin F_i x ∈ / F i . Since B ∖ F i = ( Y ∖ F i ) ∪ { x } B\setminus F_i=(Y\setminus F_i)\cup\{x\} B ∖ F i = ( Y ∖ F i ) ∪ { x } spans and adding one element increases rank by at most one, Y ∖ F i Y\setminus F_i Y ∖ F i has rank either r r r or r − 1 r-1 r − 1 . In the former case, it already spans. In the latter case, its closure is one of the deficient hyperplanes H i H_i H i constructed above. The replacement element y y y was chosen outside all these hyperplanes, so adding y y y increases the rank to r r r . As y ∉ F i y\notin F_i y ∈ / F i , we conclude that B ′ ∖ F i = ( Y ∖ F i ) ∪ { y } B'\setminus F_i=(Y\setminus F_i)\cup\{y\} B ′ ∖ F i = ( Y ∖ F i ) ∪ { y } spans in both cases. Thus B ′ B' B ′ is feasible. Moreover, w ( y ) ≤ w ( x ) w(y)\le w(x) w ( y ) ≤ w ( x ) gives w ( B ′ ) ≤ w ( B ) w(B')\le w(B) w ( B ′ ) ≤ w ( B ) , and replacing x ∉ W x\notin W x ∈ / W by y ∈ W ∖ Y y\in W\setminus Y y ∈ W ∖ Y reduces the number of selected elements outside W W W by exactly one. After at most b b b such exchanges there is an optimum entirely inside W W W .
Searching the core. Enumerate all subsets of W W W of size at most b b b , test their rank after each listed scenario, and choose a cheapest feasible candidate. The size bound (21) , the construction bound in Lemma 5, and greedy rank computation give f ( r , m ) n O ( 1 ) f(r,m)n^{O(1)} f ( r , m ) n O ( 1 ) independence queries and elementary operations for a computable function f f f .
Linear representations: simultaneous spanning. With a linear representation, we can encode each listed scenario as a spanning constraint on the same selected set. Zeroing a failed column makes it a loop while keeping its ground-set label. This preserves a common ground set and a common cost function across all scenarios. For a represented linear matroid, take each scenario F i F_i F i in turn and replace its columns in the input representation by zero columns, obtaining a represented matroid M i M_i M i on the same ground set. For every B ⊆ E B \subseteq E B ⊆ E ,
rank M i ( B ) = rank M ( B ∖ F i ) . \operatorname{rank}_{M_i}(B)=\operatorname{rank}_{M}(B \setminus F_i). rank M i ( B ) = rank M ( B ∖ F i ) .
The initial feasibility test ensures that every M i M_i M i has rank r r r . All M i M_i M i are represented over the same field, so Lemma 7 applies with R = m r R = mr R = m r . It finds a minimum-cost set spanning every M i M_i M i in 2 O ( r m ) n O ( 1 ) 2^{O(rm)}n^{O(1)} 2 O ( r m ) n O ( 1 ) field operations. By the rank equality above, this set is optimal for the scenario instance. For m ≥ 1 m \ge1 m ≥ 1 , satisfying these spanning constraints also implies the no-failure constraint by rank monotonicity, so no additional matroid for F 0 = ∅ F_0 = \emptyset F 0 = ∅ is needed. □ \square □
Transversal matroids and gammoids: one-failure hardness
We return to the failure-budget model. In this section all ground elements are vulnerable, and a selected set must span after deletion of any one of its elements. Even this one-failure case is hard on explicitly presented transversal matroids and on a restricted class of gammoids.
The parameter here is different from those in the preceding sections. If β \beta β is the solution-size budget and r r r is the matroid rank, the excess budget β − r \beta-r β − r counts how many elements beyond a basis may be selected. We will obtain W[2 ] -hardness for this parameter. This is compatible with fixed-parameter tractability in r + k r+k r + k : the reduction keeps k = 1 k=1 k = 1 and controls β − r \beta-r β − r , but allows r r r to grow with the source instance.
A transversal matroid is specified by a bipartite graph with ground elements on one side and targets on the other. A subset of ground elements is independent if a matching covers all its elements. Thus spanning a rank-r r r transversal matroid means that the selected elements admit a matching of size r r r .
The following NP-hardness construction is due to Adjiashvili, Bindewald, and Michaels in their study of robust assignments with vulnerable nodes [1 Section 4.1] . We include the proof to express it in matroid language, record its direct gammoid interpretation, and make explicit the parameterized consequence for the solution budget above rank. The NP-hardness and the underlying Set Cover gadget are not new claims here.
The construction has two kinds of ground elements. A pair of baseline elements for each universe element is forced into every robust selection. Additional elements correspond to input sets, and they repair a failed baseline element exactly when the selected sets cover the corresponding universe element. This gives an exact relation between the two optima, from which the excess-budget consequence follows.
Theorem 8. The size-budget decision version of Fault-Tolerant Basis is NP-complete on explicitly presented transversal matroids already for k = 1 k=1 k = 1 [1 ] . The same holds for gammoids whose representing digraph contains only one pair of arcs from source vertices to ground-set vertices. Moreover, the same construction gives W[2 ] -hardness parameterized by solution budget minus rank, already with k = 1 k=1 k = 1 .
Proof. The Set Cover construction. We give the construction of [1 ] and its parameter accounting. Consider a Set Cover instance with universe U = { u 1 , … , u m } U = \{u_1,\ldots,u_m\} U = { u 1 , … , u m } , sets A 1 , … , A s ⊆ U A_1,\ldots,A_s \subseteq U A 1 , … , A s ⊆ U and budget q q q . We may assume m ≥ 1 m \ge1 m ≥ 1 . Introduce two targets u i , g i u_i,g_i u i , g i for every i ∈ [ m ] i \in[m] i ∈ [ m ] , two ground elements a i , d i a_i,d_i a i , d i for every such i i i , and one ground element c j c_j c j for every input set A j A_j A j . The neighborhoods of the ground elements are
N ( a i ) = { u i , g i } , N ( d i ) = { g i } , N ( c j ) = { u ∈ U : u ∈ A j } . N(a_i)=\{u_i,g_i\}, \qquad N(d_i)=\{g_i\}, \qquad N(c_j)=\{u\in U:u\in A_j\}. N ( a i ) = { u i , g i } , N ( d i ) = { g i } , N ( c j ) = { u ∈ U : u ∈ A j } .
All ground elements are vulnerable. Set k = 1 k=1 k = 1 and the solution-size budget β = 2 m + q \beta=2m+q β = 2 m + q . The matroid has rank exactly 2 m 2m 2 m : there are 2 m 2m 2 m targets, and matching a i a_i a i to u i u_i u i and d i d_i d i to g i g_i g i for all i i i saturates them all. We call this the baseline matching.
Every baseline element is mandatory. Let B B B be one-fault tolerant. Since B B B spans before failures, it contains at least one of a i , d i a_i,d_i a i , d i : these are the only neighbors of g i g_i g i , and a size-2 m 2m 2 m matching must cover every target. If exactly one were selected, deleting that element would leave g i g_i g i with no selected neighbor. Hence both a i a_i a i and d i d_i d i belong to B B B for every i i i .
The additional elements encode a cover. The selected set-elements must also form a cover. Let C = { j : c j ∈ B } C=\{j:c_j\in B\} C = { j : c j ∈ B } . Delete a i a_i a i . Any surviving size-2 m 2m 2 m matching must match g i g_i g i to d i d_i d i . It must also cover u i u_i u i , whose only remaining possible selected neighbors are set-elements c j c_j c j with u i ∈ A j u_i\in A_j u i ∈ A j . Therefore such an index j ∈ C j\in C j ∈ C exists for every i i i , so the sets indexed by C C C cover U U U .
A cover repairs every single failure. Conversely, let C C C index a set cover and select all baseline elements together with the corresponding c j c_j c j . The baseline matching proves spanning without failures.
There are three possible types of a failed selected element. A set-element c j c_j c j fails. Deleting a selected c j c_j c j leaves the baseline matching intact.
A baseline element a i a_i a i fails. Retain every baseline pair at indices different from i i i , match d i d_i d i to g i g_i g i , and match a selected covering c j c_j c j to u i u_i u i .
A baseline element d i d_i d i fails. Retain every baseline pair at indices different from i i i , match a i a_i a i to g i g_i g i , and match a selected covering c j c_j c j to u i u_i u i . In the last two cases the covering element c j c_j c j survives, because the unique failure is a baseline element. The modified edges form a matching: the baseline matching uses no set-elements, and the unchanged edges cover only targets at other indices. Each repair therefore gives a matching of size 2 m 2m 2 m . Different failures may use different matchings; only one failure must be repaired at a time. Figure 2 illustrates the local repair.
Figure 2. The local part of the robust-assignment construction. After deleting d i d_i d i , match a i a_i a i to g i g_i g i and c j c_j c j to u i u_i u i . All baseline edges at other indices remain unchanged. Only one failure is repaired at a time.
Optimum identity and excess-budget hardness. It follows that there is a robust set of size at most 2 m + q 2m+q 2 m + q if and only if the source instance has a set cover of size at most q q q . Equivalently, on feasible instances,
OPT F T B = 2 m + OPT S e t C o v e r . \operatorname{OPT}_{\mathrm{FTB}} = 2m + \operatorname{OPT}_{\mathrm{SetCover}} . OPT FTB = 2 m + OPT SetCover .
The construction has polynomial size. The 2 m 2m 2 m forced baseline elements account for the rank, and every additional selected element corresponds to one input set. Thus the output parameter is exactly
β − r = ( 2 m + q ) − 2 m = q . \beta-r=(2m+q)-2m=q. β − r = ( 2 m + q ) − 2 m = q .
The W[2 ] -hardness of Set Cover parameterized by its budget [6 ] therefore gives the asserted parameterized consequence.
The same construction as a gammoid. For the gammoid presentation, use the convention that a gammoid is represented by a digraph, a set of sources, and a ground set of terminal vertices; independence means that vertex-disjoint paths link distinct sources to the chosen ground elements. Direct every edge of the bipartite presentation from its target to its ground element, and take all targets as sources. Every source-to-ground path has one edge, so a linkage is exactly a matching in the transversal presentation. This gives the claimed restricted gammoid instances. Under the equivalent convention of paths from ground elements to sinks, reverse all arcs.
Membership in NP. It remains to show membership in NP. For k = 1 k=1 k = 1 , a proposed selected set can be checked by computing its rank and its rank after deletion of each selected element. In a transversal presentation these are polynomial-time matching computations; in a gammoid presentation they are polynomial-time vertex-capacitated flow computations. There are at most ∣ B ∣ + 1 |B|+1 ∣ B ∣ + 1 checks, each polynomial in the explicit presentation size. This proves NP membership and completes the theorem. □
Conclusion
We developed two forms of compression for minimum-cost fault-tolerant spanning with safe and vulnerable elements. For independence-oracle matroids, a bounded set of original elements contains an optimum. The proof combines weighted flat-avoidance representatives with a bound on small cocircuits through a prescribed element. For represented linear matroids, we compress families of partial selections: every successful future completion remains successful for a retained selection of no greater cost. Shared-variable polynomial certificates ensure that one retained selection works with the same completion under all allowed failures. Over fixed finite fields, a simpler reduction retains a bounded number of inexpensive elements in each parallel class.
For explicitly listed failures, the two measures of the scenario list lead to different complexity results. Rank together with the number of scenarios yields fixed-parameter algorithms, using either failure signatures or simultaneous spanning. Rank together with the maximum scenario size gives W [ 1 ] \mathrm{W}[1] W [ 1 ] -hardness, even for uniform matroids and two-element scenarios. We also expressed the robust-assignment construction of Adjiashvili, Bindewald, and Michaels [1 ] in matroid language and derived its W [ 2 ] \mathrm{W}[2] W [ 2 ] -hardness consequence for solution budget minus rank on transversal matroids and restricted gammoids, already for one failure.
The main algorithmic question left by our results is whether the parameter dependence of common-completion compression can be improved over arbitrary fields. Our algorithm retains a basis of coefficient vectors in the space of all monomials up to the certificate’s degree bound. Can the structure of these certificates yield a smaller space, or a way to select representatives without expanding their full coefficient vectors, while preserving the same deterministic guarantee and optimal cost?
Acknowledgments. ChatGPT was used to assist with language editing, organization, and clarity of exposition during manuscript preparation. AI was not used to develop scientific results or mathematical proofs, except for the W [ 1 ] \mathrm{W}[1] W [ 1 ] -hardness result for explicit failure scenarios, which was developed with AI assistance. The authors independently examined and verified all mathematical statements, proofs, and arguments, including the AI-assisted hardness result. The authors take full responsibility for the correctness, originality, and scientific content of the manuscript.