Skip to main content
3 of 3
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/

A minimum set hitting every base of a matroid

We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, in a spanning tree matroid, the minimum hitting set should be a minimum cut. Thanks.

Crossposted at CSTheory.