min hitting set of every base of a matroid

Question

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.

Answer 1

I meant to leave this as a comment, but I don't have the reputation to do so yet. This question was crossposted over at Mathoverflow, where I mention that the problem is NP-complete.

See here.

To avoid a contradiction with Chandra Chekuri's answer, I do not believe that the LP given in his answer is integral. To see this consider the uniform matroids $U_{k,n}$, where the bases are all $k$-subsets of a $n$-set. Note that the vector $(1/k, 1/k, \dots, 1/k)$ is a feasible solution to the LP. Thus, if $c$ is identically 1, then the minimum value of the LP is at most $n/k$. On the other hand, a minimum hitting for $U_{k,n}$ has size $n-k+1$.

Answer 2

Update: The argument is incorrect as pointed out. The mistake is in the last line where I thought that one gets total dual integrality but the primal is covering LP and it doesn't work.

Let's write an LP for the problem with variable $x(e)$ for each element $e$. We want to $\min \sum_e c(e) x(e)$ such that $\sum_{e \in B} x(e) \ge 1$ for all bases $B$ and $x(e) \ge 0$ for all $e$. First observation is that this LP can be solved in polynomial time because the separation oracle for the LP is simply the problem of finding a minimum-weight basis of the given matroid. We want to claim that this polytope is integral. If you look at the dual it corresponds to packing bases of the matroid in the capacity vector given by $c$. Schrijver Chapter 42 shows that when $c$ is integral the dual is integral. This implies that the primal is integral.

Answer 3

As long as you can, in polynomial time in number of elements, check whether a set H of elements is a hitting set and if not, find one base that is not hit, then the problem falls into the realm of the Implicit Hitting Set problems. See the following paper for algorithms and discussions.