6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Such a set is also called a vertex cover of the matroid/simplicial complex. $\endgroup$
    – Thomas Kahle
    Commented Jun 7, 2012 at 9:11

2 Answers 2

Reset to default
9
$\begingroup$

The problem is hard in general. Note that a minimal set that intersects every base of a matroid $M$ is a dependent set in the dual matroid $M^{*}$. Such sets are called cocircuits. So, you are looking for the shortest cocircuit of a matroid.

The shortest cocircuit problem (equivalently shortest circuit problem) is NP-complete in general (even for binary matroids). See this Matroid Union post for more information on finding shortest circuits in binary matroids.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I have an additional question: Is there anything known about the complexity of computing the shorest circuit/cocircuit problem on transversal matroids or Gammoids? Thanks. (BTW: should I make this a Quesion instead of a comment?) $\endgroup$
    – lapordge
    Commented May 23, 2012 at 1:29
  • $\begingroup$ Hmmm...I'm not sure about transversal matroids or Gammoids, but my guess is that it's still hard. Probably you should post this as a separate question so that it is more visible to others. It's also good etiquette to link questions that are posted at multiple sites. Cheers. $\endgroup$
    – Tony Huynh
    Commented May 24, 2012 at 2:06
1
$\begingroup$

A set intersects every base of a matroid $M$ iff it includes the complement of some hyperplane. In more detail: $X$ intersects every base iff $M-X$ includes no base iff $M-X$ fails to span $M$ iff $M-X$ is included in some hyperplane $H$ iff $X$ includes the complement of some hyperplane $H$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .