arXiv:2611.16333 · v1

When Elements Fail: Weighted Fault-Tolerant Matroid Bases

首次提交 2026-11-12 13:56

版本更新 2026-11-12 13:56

雷达观测 2026-11-13 14:16

摘要

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}