betaFeedback

WorksComputer Science

When Elements Fail: Weighted Fault-Tolerant Matroid Bases

Abstract

Given a rank-rr matroid on nn elements with nonnegative costs and a partition into safe and vulnerable elements, we seek a minimum-cost set that spans after every deletion of at most kk selected vulnerable elements. We resolve several open questions posed by Bentert, Fomin, Golovach, and Morelle (ESA 2025) concerning weighted costs, nonuniform failures, and explicitly specified failure scenarios. To this end, we develop two compression methods. For matroids given by an independence oracle, weighted flat-avoidance representatives yield a bounded subset of the ground set containing an optimal solution and a 2O((r+k)4)nO(1)2^{\mathcal{O}((r+k)^4)}n^{\mathcal{O}(1)}-time algorithm. This establishes fixed-parameter tractability for weighted costs and nonuniform failures simultaneously. For explicitly represented linear matroids, polynomial certificates allow us to compress families of partial solutions while preserving successful completions under all allowed failures. This yields a deterministic algorithm using 2O(kr(r+k)log⁡(r+1))nO(1)2^{\mathcal{O}(kr(r+k)\log(r+1))}n^{\mathcal{O}(1)} field operations over arbitrary fields. Over fixed finite fields, a simpler reduction uses parallel classes. For explicitly listed failure scenarios, we obtain fixed-parameter algorithms parameterized by rank and the number of scenarios. In contrast, the size-budget decision version is W[1]-hard parameterized by rank and maximum scenario size, even on uniform matroids with two-element scenarios. \keywords{Matroids \and Fault tolerance \and Fixed-parameter algorithms \and Representative families}

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 MM and a nonnegative integer kk, the Fault-Tolerant Basis problem asks for a smallest set B⊆E(M)B \subseteq E(M) such that B∖FB \setminus F spans MM for every F⊆BF \subseteq B with ∣F∣≤k|F| \leq k, or a report that no such set exists. For k=0k = 0, this is the ordinary basis problem; for k≥1k \geq1, 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 (kr)O(kr4)nO(1)(kr)^{O(kr^4)}n^{O(1)} time for rank-rr matroids on nn elements given by an independence oracle, where kk is the number of failures to be tolerated. Thus, the problem is fixed-parameter tractable when parameterized by r+kr + k.

They left open the following questions:

  • Weighted costs. Does fixed-parameter tractability in r+kr + 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-rr matroid M=(E,I)M = (E, \mathcal{I}), nonnegative integer costs w:E→Z≥0w : E \to\mathbb{Z}_{\geq0}, a partition E=S∪˙VE = S \mathbin{\dot\cup} V into safe and vulnerable elements, and a failure budget k≥0k \geq0. The task is to find a minimum-cost set B⊆EB \subseteq E satisfying

rank⁡M(B∖F)=rfor 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,

or report that no such set exists. The ordinary weighted model is the special case S=∅S = \varnothing. The surviving selected elements must span the original matroid; the target rank does not change when a failure occurs.

Throughout, n=∣E∣n = |E| and costs are encoded in binary. The cases r=0r = 0 and k=0k = 0 are polynomial-time solvable; the exponential bounds below concern r,k≥1r, k \geq1. 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-rr matroids given by independence oracles is solvable in

2O(blog⁡b+brlog⁡(r+k−1k))nO(1),2^{O\left(b\log b+br\log\binom{r+k-1}{k}\right)}n^{O(1)},

where b=(k+1)rb=(k+1)r.

In particular, the problem is solvable in 2O((r+k)4)nO(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 rr and kk 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 rr and kk. 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

2O(kr(r+k)log⁡(r+1))nO(1)2^{O(kr(r+k)\log(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-rr representation has a number of nonloop parallel classes bounded in terms of rr 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 FQ\mathbb{F}_Q, Weighted Nonuniform Fault-Tolerant Basis is solvable in

2O(kr2+krlog⁡(k+2))nO(1).2^{O(kr^2+kr\log(k+2))}n^{O(1)}.

In particular, for every fixed failure budget kk, the running time is 2O(r2)nO(1)2^{O(r^2)}n^{O(1)}.

The oracle and algebraic algorithms offer different advantages. When k=rk = r, their running-time exponents are O(r4)O(r^4) and O(r3log⁡(r+1))O(r^3 \log(r + 1)), respectively. For fixed r≥2r \ge2 and growing kk, the oracle bound has exponent O(klog⁡(k+1))O(k \log(k+1)), whereas the algebraic bound has exponent O(k2)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)rb = (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 bb elements takes nO(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.

Flowchart comparing the oracle and linear algorithms. It contains the labels “Small-solution lemma”, “Some optimum has at most $b=(k+1)r$ elements.”, “Oracle algorithm”, “Process elements by cost; retain a bounded core separately for each safety type.”, “Linear algorithm”, “Fix final size and vulnerable count; start with the empty partial selection.”, “Enumerate subsets of the core of size at most $b$.”, “For each input element, generate skip/take successors; group by safe/vulnerable counts and rank.”, “For each candidate, test spanning after every allowed failure.”, “Build common-completion certificates; keep a cost-ordered basis of coefficient vectors.”, “Return a cheapest feasible selection, or report infeasibility. For the linear algorithm, check completed selections and compare all target counts.”, and “next element”.

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 WW with the following replacement property. For every feasible selection BB of size at most bb and every x∈B∖Wx \in B \setminus W, there is an element y∈W∖By \in W \setminus B of the same safety type as xx, with w(y)≤w(x)w(y) \le w(x), such that (B∖{x})∪{y}(B \setminus\{x\}) \cup\{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 bb, repeated replacements therefore produce an optimum contained in WW. The challenge is to construct a bounded set WW 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 BB and an element x∈Bx \in B, and write Y=B∖{x}Y = B \setminus\{x\}. Consider a failure set F⊆Y∩VF \subseteq Y \cap V with ∣F∣≤k\lvert F\rvert\le k. If Y∖FY \setminus F already spans, no replacement is needed for this failure. Otherwise, feasibility of BB implies that adding xx restores full rank, so Y∖FY \setminus F has rank r−1r-1. Its closure is therefore a hyperplane, and a replacement yy restores spanning exactly when it lies outside that hyperplane. Thus, one element outside all these hyperplanes works for every failure in which yy survives. If yy itself fails, feasibility follows from the corresponding failure of xx in BB.

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∣BM\vert B is a cocircuit containing xx and contained in F∪{x}F \cup\{x\}, so it has size at most k+1k+1. A deletion–contraction argument bounds the number of these cocircuits by (r+k−1k)\binom{r+k-1}{k}. Each obstructing hyperplane is the closure of a subset of BB, so its intersection with BB determines it; distinct hyperplanes therefore give distinct cocircuits in M∣BM\vert 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 PP, we construct a polynomial GPG_P. A future completion ZZ determines a symbolic substitution ev⁡Z\operatorname{ev}_Z, common to all partial selections in the state, such that

ev⁡Z(GP)≠0⟺P∪Z survives every allowed failure.\operatorname{ev}_Z(G_P) \ne0 \quad\Longleftrightarrow\quad P \cup Z\text{ 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 ZZ, 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 GPG_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,

GP=∑iαiGPi,ev⁡Z(GP)≠0⟹ev⁡Z(GPi)≠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.

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 kk vulnerable elements to fail, the input supplies a family F={F1,…,Fm}\mathcal{F} = \{F_1, \ldots, F_m\} of failure scenarios. The task is to find a minimum-cost spanning set BB such that B∖FiB \setminus F_i spans the matroid for every i∈[m]i \in[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 rr and the number mm of scenarios, the problem is fixed-parameter tractable on independence-oracle matroids. For explicitly represented linear matroids, we obtain an algorithm using 2O(rm)nO(1)2^{O(rm)}n^{O(1)} field operations when m≥1m \ge1. 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≥0a \ge0, write [a]={1,…,a}[a] = \{1,\ldots,a\}, with [0]=∅[0] = \emptyset. Throughout, n=∣E∣n = |E| and costs are nonnegative integers given in binary. For X⊆EX \subseteq E, write w(X)=∑e∈Xw(e)w(X) = \sum_{e \in X} w(e). A selected set need not be independent as fault tolerance may require selecting more elements than the matroid rank. We write LinL_{\mathrm{in}} for the total input encoding length; this is distinct from the ground-set size nn.

Matroid terminology. A matroid M=(E,I)M = (E,\mathcal{I}) consists of a ground set EE and a nonempty family I\mathcal{I} of independent sets satisfying:

  • ∅∈I\emptyset\in\mathcal{I},

  • if A⊆B⊆EA \subseteq B \subseteq E and B∈IB \in\mathcal{I} then A∈IA \in\mathcal{I} and

  • if A,B∈IA, B \in\mathcal{I} with ∣A∣<∣B∣|A| < |B|, some e∈B∖Ae \in B \setminus A satisfies A∪{e}∈IA \cup\{e\} \in\mathcal{I}.

For X⊆EX \subseteq 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}\}. Write r=rank⁡M(E)r = \operatorname{rank}_{M}(E). A basis of XX is a maximal independent subset of XX; it has size rank⁡M(X)\operatorname{rank}_{M}(X). A set XX spans MM if rank⁡M(X)=r\operatorname{rank}_{M}(X) = r. Adding or deleting one element changes rank by at most one. The closure of XX 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)\}.

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).

Closure is monotone: if X⊆YX \subseteq Y, then cl⁡M(X)⊆cl⁡M(Y)\operatorname{cl}_{M}(X) \subseteq\operatorname{cl}_{M}(Y). A flat is a set equal to its closure. For r≥1r \ge1, a hyperplane is a flat of rank r−1r-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 ee is a loop if {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 MM when the matroid is clear.

The restriction M∣XM|X has ground set XX and independent sets {I∈I:I⊆X}\{I \in\mathcal{I}: I \subseteq X\}. Deletion is restriction to the remaining elements: M∖e=M∣(E∖{e})M \setminus e = M|(E \setminus\{e\}). Contraction by ee, denoted M/eM/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\}).

For X⊆B⊆EX \subseteq B \subseteq E, closure in the restriction satisfies

References

  1. [1]Adjashvili, D., Bindewald, V., Michaels, D.: Robust assignments with vulnerable nodes. arXiv:1703.06074 (2017), https://arxiv.org/abs/1703.06074
  2. [2]Adjashvili, D., Stiller, S., Zenklusen, R.: Bulk-robust combinatorial optimization. Mathematical Programming 149, 361–390 (2015). https://doi.org/10.1007/s10107-014-0760-6
  3. [3]Bentert, M., Fomin, F.V., Golovach, P.A., Morelle, L.: Fault-tolerant matroid bases. In: 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol. 351, pp. 83:1–83:14 (2025). https://doi.org/10.4230/LIPIcs.ESA.2025.83, full version: arXiv:2506.22010
  4. [4]van Bevern, R., Tsidulko, O.Y., Zschoche, P.: Representative families for matroid intersections, with applications to location, packing, and covering problems. Discrete Applied Mathematics 298, 110–128 (2021). https://doi.org/10.1016/j.dam.2021.03.014
  5. [5]Chekuri, C., Jain, R.: Approximation algorithms for network design in non-uniform fault models. In: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPICs), vol. 261, pp. 36:1–36:20 (2023). https://doi.org/10.4230/LIPIcs.ICALP.2023.36
  6. [6]Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshтанov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)DOI
  7. [7]Dey, D., Kavitha, T.: Low-cost arborescence under edge faults. arXiv:2605.13800 (2026), https://arxiv.org/abs/2605.13800
  8. [8]Dimakis, A.G., Godfrey, P.B., Wu, Y., Wainwright, M.J., Ramchandran, K.: Network coding for distributed storage systems. IEEE Transactions on Information Theory 56(9), 4539–4551 (2010). https://doi.org/10.1109/TIT.2010.2054295
  9. [9]Fomin, F.V., Lokштанov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM 63(4), 29:1–29:60 (2016). https://doi.org/10.1145/2886094
  10. [10]Fomin, F.V., Lokштанov, D., Meesum, S.M., Saurabh, S., Zehavi, M.: Matrix rigidity from the viewpoint of parameterized complexity. SIAM Journal on Discrete Mathematics 32(2), 966–985 (2018). https://doi.org/10.1137/17M112258X
  11. [11]Hommelsheim, F., Mühlenthaler, M., Schaudt, O.: How to secure matchings against edge failures. SIAM Journal on Discrete Mathematics 35(3), 2265–2292 (2021). https://doi.org/10.1137/20M1336229
  12. [12]Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y., Okamoto, Y.: A parameterized view to the robust recoverable base problem of matroids under structural uncertainty. Operations Research Letters 50(3), 370–375 (2022)DOI

Paper details

vlnc:W_nhznxm7p
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT, AI

View statement
Looking for related papers…
Contents