<p>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. </p>

<p>See <a href="https://mathoverflow.net/questions/97517/a-minimum-set-hitting-every-base-of-a-matroid">here</a>.  </p>

<p>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 <em>all</em> $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$. </p>

CC BY-SA 3.0
2012-05-22T02:18:31.640Z
Thanks, it was my mistake in thinking that the primal is integral due to total dual integrality but I got the signs mixed up it seems.
Chandra Chekuri
CC BY-SA 3.0
2012-05-22T08:01:11.030Z
No worries; it happens to all of us. =)
Tony Huynh
CC BY-SA 3.0
2012-05-21T22:55:25.653Z
2012-07-05T07:13:56.053Z
2017-04-13T12:57:54.777Z
Tony Huynh
<blockquote>
  <p><strong>Update</strong>: 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.</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2012-05-22T00:46:28.633Z
Thanks, Chandra. The dual is indeed a relaxation of the base packing problem which seems also in P. But the LP is not integral, as Tony said.
jian
CC BY-SA 3.0
2012-05-21T14:35:05.417Z
2012-11-11T18:10:29.103Z
2012-11-11T18:10:29.103Z
Chandra Chekuri
<p>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 <em>Implicit Hitting Set</em> problems. See <a href="http://arxiv.org/abs/1102.1472" rel="nofollow">the following paper</a> for algorithms and discussions. </p>

CC BY-SA 3.0
2012-11-11T10:28:20.840Z
2012-11-11T10:28:20.840Z
Dan
<p>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.</p>

CC BY-SA 3.0
2012-05-19T16:29:56.347Z
Did you look in Schrijver's book on combinatorial optimization?
Chandra Chekuri
CC BY-SA 3.0
2012-05-20T09:19:14.737Z
I checked Schrijver's book but didn't find anything directly related..It may be a simple corollary of some result in the book. However, I didn't find it :-(
jian
<co.combinatorics><approximation-algorithms><optimization>
min hitting set of every base of a matroid
jian
# min hitting set of every base of a matroid

(Asked by: username_0 on 2012-05-19)

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.

**Tags:** co.combinatorics, approximation-algorithms, optimization

> **Comments:**
> **username_1**: Did you look in Schrijver's book on combinatorial optimization?  
> **username_0**: I checked Schrijver's book but didn't find anything directly related..It may be a simple corollary of some result in the book. However, I didn't find it :-(  

---

## 3 answers

### Answer by username_2 on 2012-05-21. Score: 11

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](https://mathoverflow.net/questions/97517/a-minimum-set-hitting-every-base-of-a-matroid).

To avoid a contradiction with username_1'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$.

> **Comments:**
> **username_1**: Thanks, it was my mistake in thinking that the primal is integral due to total dual integrality but I got the signs mixed up it seems.  
> **username_2**: No worries; it happens to all of us. =)  

---

### Answer by username_1 on 2012-05-21. Score: 3

> **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.

> **Comments:**
> **username_0**: Thanks, Chandra. The dual is indeed a relaxation of the base packing problem which seems also in P. But the LP is not integral, as Tony said.  

---

### Answer by username_3 on 2012-11-11. Score: 0

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](http://arxiv.org/abs/1102.1472) for algorithms and discussions.


---

