Bounded degree matroid basis

Definitions and mathematical statement

Let $M$ be a matroid on a finite set $V$, given by an independence oracle: on a queried subset it reports whether that subset is independent. Independent sets are closed under taking subsets and satisfy the exchange axiom; their maximal members are bases. Let $\mathcal H$ be an explicitly listed family of subsets of $V$, and set \[ \Delta=\max_{v\in V}|\{H\in\mathcal H:v\in H\}|\ge1. \] Assign rational costs $c_v$ and integer bounds $\ell_H\le u_H$. Assume at least one basis satisfies every bound, and let $\mathrm{OPT}$ be the least cost of such a basis, with $c(B)=\sum_{v\in B}c_v$.

Is there an algorithm using polynomially many oracle calls and polynomial time in the input encoding that returns a basis $B$ satisfying \[ c(B)\le\mathrm{OPT},\qquad \ell_H-\Delta+1\le |B\cap H|\le u_H+\Delta-1 \quad(H\in\mathcal H)? \] Both lower and upper bounds must be handled simultaneously. The output may violate the original degree constraints, but only by the displayed additive amount; its cost is compared with the optimum under the original constraints. The number $\Delta$ counts constraints involving one ground element, not the largest size of a constraint set. The empty-family case reduces to ordinary minimum-cost basis computation and needs no relaxation.

Short English statement

Can one find a basis costing no more than the constrained optimum while violating every lower and upper degree bound by at most $\Delta-1$?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000008 (AMR-029-0008), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Bounded degree matroid basis. Original source indexed by AMR-029-0008. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Bounded degree matroid basis. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Bounded_degree_matroid_basis.