arXiv preprint ·
When Elements Fail: Weighted Fault-Tolerant Matroid Bases
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given a rank-\(r\) matroid on \(n\) 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 \(k\) 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 \(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 \(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}
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs
Additive cubes are avoidable over $\{0,1,2,3\}$, $\{0,1,4\}$ and $\{0,2,5\}$
Improved Lower Bounds for Mutually Orthogonal Latin Squares (MOLS) at 33 Orders
Color Refinement Distinguishes Connected Rooted Outerplanar Graphs
Matroid Parity Meets Vertex Splitting
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.