Skip to main content
MathOverflow

Return to Question

replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

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

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.

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.

added 126 characters in body; edited tags
Source Link
Tony Huynh
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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.

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.

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.

Source Link
lapordge
lapordge
  • 115
  • 3

A minimum set hitting every base of a matroid

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.