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.
2
-
3$\begingroup$ Did you look in Schrijver's book on combinatorial optimization? $\endgroup$– Chandra ChekuriCommented May 19, 2012 at 16:29
-
$\begingroup$ 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 :-( $\endgroup$– jianCommented May 20, 2012 at 9:19
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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$.
-
$\begingroup$ 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. $\endgroup$ Commented May 22, 2012 at 2:18
-
$\begingroup$ No worries; it happens to all of us. =) $\endgroup$ Commented May 22, 2012 at 8:01
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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. $\endgroup$– jianCommented May 22, 2012 at 0:46
$\begingroup$
$\endgroup$
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.
