CS Paper Radar

When Elements Fail: Weighted Fault-Tolerant Matroid Bases

Madhumita Kundu, Soumi Nandi, Saket Saurabh

cs.DS cs.DM ·submitted 2026-11-12 05:56 UTC · v1

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}

Closest papers

Nearest neighbours by meaning across the whole index.

Sensitivity Oracles for Matroid Packing, Matroid Covering, and Matching Problems with Applications

cs.DS ·2026-09-01 ·Keerti Choudhary, Amit Kumar, Lakshay Saggi
theory similarity 0.72
Abstract · 65 pages, 3 figures

Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $α$-factor, with perfect matching as the case $α=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $σ$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^ω)$ query time and $O(fσ^2)$ space. We also prove a matching $Ω(\min\{σ^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.

0.27

Weighted Equitability and Matroid-Constrained Discrepancy

cs.DS ·2026-08-14 ·Kristóf Bérczi, Siyue Liu, Victor Reis, Jakub Tarnawski
theory similarity 0.72
Abstract

We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. Then $E$ has a partition into $k$ bases such that the weights of any two bases differ by at most the largest element weight. We present two proofs based on the localized exchange theorem of Akrami, Liu, Raj, and Végh. The first is existential, while the second is constructive and leads to a strongly polynomial-time algorithm. As applications, we obtain an additive guarantee for matroid-constrained makespan minimization for identical machines and a strongly polynomial-time algorithm for finding an EF1 allocation under a matroid constraint and identical additive valuations. We further generalize the Beck--Fiala framework in discrepancy theory to settings with matroid constraints. Given a nonnegative matrix of column sparsity $Δ$, we show that a fractional basis can be rounded to a basis of no larger cost while preserving every row sum within additive error $2Δ$ times the largest matrix entry. Motivated by the $2$-sparse prefix Beck--Fiala conjecture, we formulate a conjecture on prefix-constrained matroid bases and prove a discrepancy bound $O(\log n)$. Finally, we give a counterexample to the weighted carpooling conjecture, thereby also disproving a conjecture by Morell and Skutella on single-source unsplittable flows with two-sided discrepancy bounds.

0.04

From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids

cs.DS ·2026-10-26 ·Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
similarity 0.67
Abstract

We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function $f: 2^{N} \rightarrow \mathbb{R}^+$ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal is to find the independent set $S \in I$ maximizing the objective function, i.e., $f(S) = \max_{I \in I} f(I)$. In the fully dynamic setting, the active ground set $N \subseteq N$ evolves through element insertions and deletions. The goal is to maintain a solution $S \subseteq N$ with $S \in I$ and $f(S) = \max_{I \subseteq N,, I \in I} f(I)$ after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a $(4+ε)$-approximation algorithm with an expected amortized update time of $O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr)$, and Banihashem et al. achieved a similar approximation with a better update time $O\!\bigl(k \log k \log^3 \frac{k}ε\bigr)$. However, these methods both become inefficient when the rank $k$ of the matroid is large (e.g., when $k = n^{o(1)}$). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a $(4+ε)$-approximate solution with expected amortized update time $poly(\log n, ε^{-1})$, where $n = |N|$. In particular, the update time is independent of the matroid rank $k$, thereby eliminating the dependence on $k$ and settling the open problem.

0.29

Cogirth-Strength Ratios and Matroid Rank Reduction

cs.DS ·2026-11-14 ·Yu Cong, Chao Xu, Yajie Zhao
similarity 0.67
Abstract

In the rank-$p$ reduction problem, we are given a matroid with nonnegative element weights and seek a minimum-weight set of elements whose deletion lowers the rank by at least $p$. For graphic matroids, this is the minimum $(p+1)$-cut problem. Chekuri, Quanrud, and Xu developed a tree-packing algorithm for minimum $k$-cut, which relies on the fact that the minimum cut of a graph is at most twice its strength, the value of a maximum fractional packing of spanning trees. We generalize this approach from graphs to matroids. The matroid analogue of the minimum cut is the cogirth, the minimum weight of a cocircuit, and the analogue of graph strength is matroid strength, the value of a maximum fractional packing of bases. We show that if every matroid in a deletion-closed class has cogirth at most $d$ times its strength, then for every $p$, the natural linear programming relaxation of rank-$p$ reduction is within a factor of $d$ of the optimum. As a result, repeatedly deleting a minimum-weight cocircuit gives a $d$-approximation, and an optimal solution can be found deterministically in $n^{(2d-1)p+O(1)}$ time on $n$ elements. For graphs, $d=2$ and our framework specializes to the tree-packing approach. As applications, we bound the cogirth-strength ratio for two broad classes, and both bounds are tight. For quasi-graphic matroids, which include graphic, bicircular, frame, and lifted-graphic matroids, the ratio is at most $2$ for all weights, giving a $2$-approximation and an exact $n^{3p+O(1)}$-time algorithm. For $(k,\ell)$-count matroids of hypergraphs with $0\le \ell\le k$ and edge size at most $s$, the ratio is at most $ks$ under unit weights. This gives a $ks$-approximation and an exact $n^{(2ks-1)p+O(1)}$-time algorithm for unweighted rank-$p$ reduction.

0.27

Algorithms for Robust Dedicated Actuator Placement

eess.SY ·2026-11-11 ·Qichao Wang, Daoyu Dong
similarity 0.67
Abstract · 13 pages, 1 figure. Source code and verification scripts available on GitHub

We study dedicated actuators installed at distinct states of a structured linear system. Failures remove actuators but preserve states and state arcs. For unit costs and one failure, an exact source-quota relaxation followed by maximum matching in a \emph{common-repair graph} yields a $3/2$-approximation on arbitrary directed state graphs using $O(n^3)$ elementary graph operations. The analysis combines fundamental cocircuit unions with the Tutte--Berge formula. For multiple failures, we give an exact algorithm fixed-parameter tractable in the maximum-matching deficiency and failure budget, independently of the number of source strongly connected components. The underlying result solves resilient matroid spanning with an arbitrary number of disjoint unit-cost quota constraints. We also establish an exact weighted spanning algorithm for safe and vulnerable elements in the independence-oracle model, with an application to strongly connected state graphs.

0.29

Tight Approximation Results for Matroid Optimization with a Linear Constraint

cs.DS ·2026-09-23 ·Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
similarity 0.67
Abstract

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum $v(S)$ subject to $w(S)\ge L$. Our main result is a unified EPTAS for all nontrivial P-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed $ε>0$, we present an algorithm running in time $|E|^{O(1)} (1/{ε^2})^{O(1/ε)}$ that outputs a feasible solution S whose value is at most $(1+ε)OPT$ for minimization variants and at least $(1-ε)OPT$ for maximization variants. This resolves the complexity status of all members of P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting.

0.14

Graphic Matroid Secretary without the Graph

cs.DS ·2026-08-11 ·Paul Dütting, Renato Paes Leme, Martin Pál, Neel Patel
similarity 0.66
Abstract

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

0.42

Stronger Hardness for Submodular Maximization Subject to a Matroid Constraint

cs.DS ·2026-10-05 ·Moran Feldman, Alan Kuhnle
similarity 0.65
Abstract · 13 pages. This version adds a remark about the relationship between this work and the results of arXiv:2610.00545

Maximizing a submodular function subject to a matroid constraint is a cornerstone problem in combinatorial optimization. The state-of-the-art algorithm for this problem obtains $0.401$-approximation~\cite{buchbinder2024constrained}, and the state-of-the-art hardness result shows that no polynomial time algorithm can obtain better than $0.478$-approximation for this problem~\cite{oveisgharan2011submodular}. In this work, we present the first improvement in $15$ years for the hardness result, showing that no polynomial time algorithm in the value-oracle model can obtain better than $8/17 \approx 0.471$-approximation, even for the special case of a cardinality or (simplified) partition matroid constraint.

0.40