Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Did you look in Schrijver's book on combinatorial optimization? –  Chandra Chekuri May 19 '12 at 16:29
    
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 May 20 '12 at 9:19
add comment

3 Answers

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

share|improve this answer
    
Thanks a lot... –  jian May 22 '12 at 0:46
    
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 May 22 '12 at 2:18
    
No worries; it happens to all of us. =) –  Tony Huynh May 22 '12 at 8:01
add comment

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.

share|improve this answer
    
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 May 22 '12 at 0:46
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.