Subset-Constrained Inverse Matroid Optimization

Abstract

In inverse optimization, the goal is to find a minimum perturbation of weights that makes a prescribed feasible solution optimal. For matroids, the classical inverse problem fixes a target basis. We replace this fixed target by a subset constraint: given a matroid $M=(S,\mathcal{I})$, weights $w$, and a subset $S_0\subseteq S$, we specify how the family of maximum-weight bases relates to the bases contained in $S_0$. We study six natural variants. The positive variants require, respectively, that at least one basis contained in $S_0$ be optimal, that every basis contained in $S_0$ be optimal, or that the optimal bases be exactly the bases contained in $S_0$; we also study the three corresponding negated requirements. This framework captures partial inverse requirements such as forced or forbidden elements, as well as settings where undesirable optimal bases should be excluded. We give a complete classification of these subset-constrained inverse matroid problems under the ${\ell }_{\infty }$- and ${\ell }_1$-norms. Under the ${\ell }_{\infty }$-norm, all six variants admit polynomial-time combinatorial algorithms (interpreting the variants with strict inequalities in the natural integral-weight setting). The algorithms are based on matroid exchange, uniform perturbations, and the connected-component structure of the restriction $M|S_0$. Under the ${\ell }_1$-norm, the picture changes sharply: the variant requiring at least one optimal basis contained in $S_0$ is strongly $\mathsf{NP}$-hard even for graphic matroids, whereas the remaining variants considered here admit polynomial-time algorithms. Thus the subset-constrained setting separates the two norms already for matroids, and even for spanning trees.